[자료구조] Array와 List

Array, List를 학습하기 전에

일반적으로 '선형 자료구조'를 떠올리면, Array(배열)와 List(리스트)가 있다. 컴퓨터공학의 자료구조 과목에서 가장 먼저 배우는 자료구조 두 가지가 바로 '배열'과 '링크드 리스트' 이기도 한데, Array와 List는 어떻게 다른지 명확하게 이해하는 것은 실제 개발하는 데 있어 중요하다고 생각한다. Java나 Kotlin을 사용해 개발하다 보면 Array, ArrayList나 LinkedList 등 다양한 형태의 Array와 List를 마주하기 때문이다. 우리는 주어진 상황에서 어떤 자료구조를 선택해야 가장 효율적인지 이해하고 사용할 수 있는 개발자가 되어야 한다.

 

Array (배열)

Array는 인덱스와, 인덱스에 대응하는 데이터들로 이루어진 자료구조이다. 중요한 포인트는, '메모리 상에서 연속적으로 데이터가 저장된다' 는 것이다.

Array

메모리 상에서 연속적으로 데이터가 저장된다는 말은, Array의 시작 주소와 Array가 담는 데이터의 타입(데이터의 크기), 그리고 인덱스만을 활용해 특정 인덱스의 데이터가 있는 주소값을 바로 알아낼 수 있다는 Array의 장점과 연결된다.

 

Int는 32bit, 즉 4Byte의 크기를 갖는 데이터 타입이다. 만일 Int형 Array의 시작 주소가 0이라고 가정해보자. 그렇다면 이 Array의 0번 인덱스의 데이터는 어느 주소에 있을까 ? 바로 0의 주소값부터 3의 주소값까지 4바이트를 읽어오면 Array의 0번 인덱스의 데이터를 가져올 수 있다. 그렇다면 인덱스 2의 데이터는 어느 주소에 있을까 ? 바로 Array의 시작 주소(0) + Array가 담는 데이터의 타입(4) * 인덱스(2)에 해당하는 8의 주소값부터 11의 주소값까지 4바이트를 읽어오면 Array의 2번 인덱스의 데이터를 가져올 수 있다.

 

단순히 선형 자료구조이다 ~ 라는 것에서 그치는 것이 아니라, 메모리 상에서 연속적으로 데이터가 저장된다는 사실이 Array의 가장 큰 특징이다. 이런 특징으로 인해 Array는 인덱스만으로 데이터에 접근하는 속도가 매우 빨라 인덱스를 통한 접근이 용이하다는 장점이 있다. 이와 더불어, 인덱스를 통한 Array의 데이터 접근에는 O(1)이 소요된다는 것 또한 알 수 있다. 위에서 봤듯이, 인덱스를 통해 데이터에 접근할 때는 '[ 배열의 시작 주소 + 배열이 담는 데이터의 크기 * 인덱스, 배열의 시작 주소 + 배열이 담는 데이터의 크기 * (인덱스 + 1) )' 의 형태로 해당 인덱스의 데이터가 위치한 주소를 바로 알아올 수 있기 때문이다.

 

하지만 메모리 상에서 연속적으로 데이터를 저장한다는 것은 장점이자 단점이 될 수 있다 ...

 

Linked List (링크드 리스트)

그렇다면 Array는 인덱스를 활용해 매우 빠르게 데이터를 가져올 수 있다는 장점이 있는 것인데, 왜 List라는 자료구조가 존재하는 것일까 ? (일반적으로 나는 이 세상에 존재하는 대부분의 기술에는 그 기술이 생겨난 근거가 있다고 생각하는 편이고, 그 근거를 이해하고 개발한다면 더욱 합리적인 코드를 작성할 수 있지 않을까 ... 하는 생각에 원리가 중요하다고 생각을 한다)

 

Array는 메모리 상에서 연속적으로 데이터를 저장한다고 했다. 이는 앞서 본 바에 따르면 장점이지만, 특정 상황에서는 단점으로 작용할 수 있다. 아래와 같은 상황을 보자.

Array의 한계 1

정수를 담는 Array가 있다. 우리는 배열이 기존에 가지고 있던 값을 유지하면서, 인덱스 2에 35라는 값을 삽입하고 싶다. 하지만 인덱스 2의 위치에는 56이라는 값이 이미 존재한다. 그렇다면 35를 삽입하기 위해서, 56을 한 칸 뒤로 밀어내야 한다. 그런데 56을 한 칸 뒤로 밀어내려고 보니, 한 칸 뒤인 인덱스 3에는 이미 15라는 값이 존재한다. 그럼 56을 한 칸 뒤로 밀어내기 위해 15를 한 칸 뒤로 밀어내야 한다. 그런데 15를 한 칸 뒤로 밀어내려고 보니, 한 칸 뒤인 인덱스 4에는 이미 36이라는 값이 존재한다. 그럼 56을 한 칸 뒤로 밀어내기 위해 15를 한 칸 뒤로 밀어내기 위해 36을 한 칸 뒤로 밀어 ... 

 

정말 번거로운 상황이 아닐 수 없다. 이는 실제로, Array의 한계로 지적되는 부분이다. 특정 데이터를 어떤 인덱스 위치에 끼워넣기 위해서는, 그 인덱스부터 맨 마지막 데이터까지 모두 한 칸씩 뒤로 밀어내야 한다. 즉, Array에 N개의 데이터가 존재하고, 이 Array의 0번 인덱스에 새로운 값을 끼워넣는다면 N개의 데이터를 모두 뒤로 밀어내야 하는 것이다. 그래서 Array에 어떤 데이터를 중간에 삽입하는 것은 O(N)의 시간 복잡도를 가진다.

 

이 뿐만이 아니다. Array는 크기를 변경시킬 수 없다.

Array의 한계 2

Array는 메모리 상에서 연속적으로 데이터를 저장하기 때문에, 특정 메모리 공간을 '할당'받아 사용해야 한다. 즉, 어떤 주소값 A부터 어떤 주소값 B까지([A, B))는 Array의 주소 공간이라는 것이다. 단순히 시작 주소만 있는 것이 아닌 끝 주소가 있다는 것이 중요하다. 끝 주소를 지나친 주소 공간은 더 이상 Array의 공간이 아니다. 위 그림에서는 Array에 5개의 데이터를 넣었고, 시작 주소는 4800이다. 그런데 만일 필요에 의해 Array에 5개가 아닌, 6개의 데이터를 넣고싶다면 어떻게 해야 할까 ? 이런 상황에서는 새로운 Array를 만들어서, 기존 Array에 있던 값을 하나하나 옮겨줘야 한다. 참 번거롭기 그지없다. Array의 크기를 변경시킬 수 있다면 얼마나 좋을까 ? 하지만 이런 상상은 앞서 말한 것처럼, Array는 연속된 주소 공간을 할당받아 사용하는 것이기 때문에 Array가 차지한 주소 영역 바로 다음 영역이 비어있다는 보장도 없고, 그래서 새로운 배열을 생성해 복사 붙여넣기 하는 수 밖에 없는 것이다.

 

Linked List는 Array가 가진 이러한 한계를 극복하기 위해 등장했다. Array는 메모리 상에서 데이터를 연속적으로 저장하기 때문에 데이터를 중간에 끼워넣는다던가, 크기를 변경시키는 데 큰 비용(시간)이 든다는 것을 확인했다. 그렇다면 Linked List는 이런 문제를 어떻게 해결하느냐, 바로 데이터를 메모리 상에서 불연속적으로 저장하는 방법을 통해 해결한다.

Linked List

Linked List는 Node라는 개념을 활용해 데이터를 관리하고 저장한다. Node는 크게 2가지 내용물로 구성된다. Data와 Pointer다. Data는 Array에서처럼, 자료구조에 저장할 데이터에 해당한다. Pointer는 다음, 혹은 다음과 이전 노드의 주소값이다. 다음 노드의 주소만 가지는 경우를 Singly Linked List라고 하고, 다음 노드와 이전 노드의 주소 둘 다 가지고 있는 경우를 Doubly Linked List라고 한다.

 

Linked List는 데이터를 연속된 주소 공간에 저장하는 것이 아니라, 메모리 주소 공간 여기저기에 노드를 생성하고 이를 흩뿌려둔다. 노드가 메모리 주소 어느 위치에 생성되든 상관하지 않는 것이다. 대신 해당 노드의 주소값을 다른 노드의 Pointer에 저장해두는 방식으로 노드와 노드 간의 연결 관계를 정의한다. A 노드의 다음 노드는 B 노드이다. 그렇다면 A 노드의 Pointer(Next)에는 B 노드의 주소값을 저장하는 방식으로 연결 관계를 정의하는 것이다.

 

따라서 Linked List에서의 인덱스는 Array에서처럼 강력한 기능을 발휘하지 못한다. Array에서는 데이터를 연속된 주소 공간에 담는 방식이었기 때문에 인덱스만을 활용해 해당 데이터의 주소값을 곧바로 알아낼 수 있었지만, Linked List에서는 해당 인덱스까지 노드를 타고 타며 탐색해야 하기 때문이다. 그래서 Linked List에서는 데이터의 접근에 최대 O(N)의 시간 복잡도가 소요된다.

 

하지만, Linked List는 불연속적인 주소 공간을 활용하되 이를 연결지어 놓은 방식이기 때문에 중간 위치에 데이터를 삽입한다거나, 혹은 미리 정해둔 사이즈를 초과해 데이터를 삽입한다고 할지라도 O(1)의 시간 복잡도만에 수행할 수 있다. 단순히 노드를 하나 생성하고, 이 노드를 기존에 있던 노드들과 연결지어 놓으면 끝나기 때문이다(물론 특정 위치까지 찾아가는 데에는 O(N)의 시간 복잡도가 들겠지만, 이는 제외하고 단순히 삽입하는 과정만을 이야기한 것).

 

즉, Linked List는 배열이 가진 장점, 인덱스를 버린 대신 데이터를 노드 형태로 나누고, 이를 포인터를 통해 연결지음으로써 빈틈없이 데이터를 적재할 수 있고 유연해졌다는 Linked List만의 장점을 갖게 되었다.

 

ArrayList (어레이 리스트)

지금까지 내용들을 정리해보면, Array와 Linked List는 이런 장단점이 있음을 알 수 있다.

 

Array - (장점) 인덱스를 통한 접근이 O(1)의 시간 복잡도로 용이하다 / (단점) 크기를 변경시킬 수 없고, 중간에 특정 데이터를 삽입하는 데 O(N)의 시간 복잡도가 소요된다.

Linked List - (장점) 빈틈없이 데이터를 적재할 수 있고, 데이터를 중간에 삽입하거나 List 크기를 변경시키는 작업이 Array보다 유연하다 / (단점) 인덱스를 통한 빠른 접근이 불가능하다

 

서로의 장단점은 어찌 보면 대칭적이다. 당연하게도, Array의 단점을 보완하는 Linked List인 만큼 Array의 장점을 버린 것이고, Linked List의 단점을 보완하는 Array인 만큼 Linked List의 장점을 버린 것이다(이를 Trade-Off라는 멋드러진 말로 표현할 수 있다).

 

Array와 Linked List의 중간 단계에 있는 자료구조는 없을까 ? 이 글을 읽으면서, 대충 ... 인덱스의 장점을 취하면서도, 크기를 변경시킬 수 있다면 참 좋을 것 같다는 생각이 들지 않는가 ? 똑똑한 선배 개발자들도 이런 생각을 했다. 그래서 Array와 Linked List를 적당히 섞어놓은, ArrayList라는 자료구조를 만들게 된다.

 

ArrayList는 Array를 기반으로 만든 List이다. Array는 빠른 탐색을 보장하지만 길이를 변경시킬 수 없고, Linked List는 길이를 자유롭게 변경시키고 연결 관계만 건드려준다면 이리 저리 중간에서의 삽입, 삭제를 빈틈없게끔 해내는 데 능숙하지만 특정 n번째 데이터에 접근하는 데 너무 오래 걸린다. 그래서 Java에서는 Array를 기반으로 List를 만들어 이 둘을 혼합시켰다(당연히 Kotlin에도 존재한다).

 

ArrayList는 어떻게 인덱스를 적극적으로 활용하면서, 크기를 가변적으로 조정할 수 있게 했을까 ? 어떻게 보면 단순한데, ArrayList는 이를 위해 size라는 개념 이외에도, capacity라는 개념을 추가했다. size는 지금 ArrayList에 몇 개의 데이터가 들어있는지를 나타낸다면, capacity는 이 ArrayList에 최대 몇 개까지 넣을 수 있는지를 의미한다. 만일 capacity 이상으로 데이터를 삽입하고자 한다면, ArrayList 내부적으로 사용하는 Array의 크기를 늘린 것처럼 만든다. 즉, 새로운 배열을 생성하고, 기존 배열의 값을 읽어와서 새로운 배열에 붙여넣는 것이다. 이 때 새로운 배열의 크기는 기존 배열의 1.5배로 증가시키는 전략을 취했다.

 

Array, List를 학습하고 나서

Array와 LinkedList, ArrayList에 대해 알아보았다. 고정된 크기만 필요로 한다면 Array가, 데이터의 추가와 삭제가 빈번하게 이뤄진다면 LinkedList가, 가변 크기를 필요로 하면서도 인덱스를 이용해 데이터를 가져오는 작업이 자주 일어난다면 ArrayList를 사용하는 것이 유리한 이유 역시 알아보았다. 어떤 상황에서든 가장 효과적인 자료구조를 사용하는, 혹은 필요하다면 기존의 것에서 창의성을 좀 덧붙여 만들어낼 수 있는 개발자가 되기 위해 노력해야겠다.

 

(생각보다 이 정도 분량의 글을 쓰는데도 기빨린다)