Array와 LinkedList

Array

연속된 메모리에 같은 타입의 값들을 순서대로 저장하는 자료구조이다. 연속된 메모리에 값이 할당되기 때문에 arr[0]과 arr[1]은 메모리 상에서도 옆에 위치해있다.

메모리에 저장하고자 하는 크기의 연속된 공간이 없다면 어떡할까?

그것은 Virtual Address를 통해 해결한다. OS는 페이지 단위로 매핑하므로, 물리적으로 불연속이어도 가상 주소가 연속이면 배열처럼 쓸 수 있다. C/C++의 malloc/mmap, 파이썬 리스트, 자바 배열 모두 “가상 주소상 연속”을 요구한다. 그럼 다시 말을 정리하자면 "가상 주소상에서 연속된 공간"에 저장하는 것이 Array다.

왜 같은 타입만 저장 가능할까?

연속된 메모리에 동일 크기의 원소이어야 인덱싱이 각 원소의 크기(int = 4byte 등등)를 계산하여 임의의 원소에 접근하는 것이 O(1)로 이루어질 수 있기 때문이다. 따라서 특정 인덱스에 접근할 때 앞에서부터 순차적으로 탐색하지 않고 원하는 인덱스만을 직접 엑세스할 수 있다. 이것을 Random Access라고 한다.

addr(i) = base + i * element_size

Static Array(정적 배열) VS Dynamic/Resizable Array(동적 배열)

Static Array는 생성시 크기가 고정되어 변경할 수 없는 배열이다. 사실 일반적인 프로그래밍이나 알고리즘 문제를 풀이할 땐 거의 사용할 일이 없다.

Dynamic Array은 크기를 지정하여 생성하지만 배열이 꽉 차면 더 큰 배열로 재할당하는 배열이다. 대부분의 언어에서 배열은 동적 배열로 구현되어있다. 리사이즈(확장)가 일어난다면 새로운 메모리 블록으로 이동한다. 모든 원소를 새로운 주소에 복사하므로 리사이즈가 일어나면 O(n)의 시간 복잡도를 가진다. 보통은 1.5배나 2배 크기의 새로운 메모리를 할당한다.

시간 복잡도 - 동적 배열

인덱스 조회/갱신: O(1)

-> 위에서 말한 것처럼 각 원소의 Random Access가 가능하기 때문에 O(1)이다.

 

맨 끝 삽입/삭제: 평균 O(1)-> 리사이즈가 일어나는 경우엔 O(n)

-> 평균 O(1)인 이유는 리사이즈가 일어난다고 가정해보자. 크기가 n인 배열에 n개를 삽입하는데 걸리는 시간 O(n)과 그 이후 다음 삽입에 리사이즈 하는데 걸리는 시간은 O(n)이다. 따라서 평균적으로 (O(n) + O(n)) / (n+1) ≈ O(1) 의 시간 복잡도라고 말할 수 있다. 이것을 분할 상환 분석(Amortized) 라고 한다.

 

중간(혹은 맨 앞) 삽입/삭제: O(n)

-> 중간(혹은 맨 앞)에 삽입/삭제하는 경우는 원소의 이동(shift)이 일어나기 때문에 O(n)의 시간복잡도를 가진다. 원소를 추가하는 경우에는 해당 자리에 공간을 만들기 위해 원소를 한 칸씩 이동해야하고, 삭제가 일어난다면 비어있는 공간으로 이동해야 한다. 만약 삭제한 경우에 원소를 이동하지 않는다면 빈 공간이 생길 것이고 Array의 특성이 깨지게 된다.

번외

Python의 List

파이썬의 List에 대해서 얘기해보자. 사실 파이썬의 List는 동적 배열 기반의 자료구조이다. 이름은 List라서 뭔가 LinkedList를 기반으로 만든 자료구조일 것 같지만 실은 그냥 동적 배열이다. 하지만 특이한 점으로는 위에서 배열은 같은 타입만 저장 가능하다고 하지만 파이썬의 List는 다른 타입도 저장이 가능하다는 것이다. 그 이유는 파이썬은 값이 아니라 객체에 대한 참조(주소)를 저장하는 구조이기 때문에 가능하다. c언어 포인터의 배열과 같은 구조라고 할 수 있다. 

Java의 ArrayList

자바의 ArrayList도 동적 배열 기반의 자료구조이다. 원시형만 저장할 수 있는 Array와 다르게 참조타입도 저장할 수 있다. add로 원시형 값을 넣을 땐 Auto-Boxing되고, 제네릭도 사용 가능하다.

 

LinkedList

Node(노드)들이 포인터(참조)로 서로 이어진 선형 자료구조이다. Array와는 다르게 연속된 메모리에 저장하지 않고 흩어진 노드들을 노드의 참조를 이용하여 연결한다. 한 덩어리의 큰 메모리가 필요하지 않고 메모리의 파편을 효율적으로 사용할 수 있고 삽입/삭제 연산에 다른 원소들을 이동하지 않아도 된다는 장점이 있다. 따라서 Array와는 다르게 특정 인덱스에 접근할 때 처음부터 순차적으로 탐색해야 한다. 이것을 Sequential Access라고 한다.

Singly LinkedList

LinkedList는 일반적으로 Singly LinkedList를 말한다. 각 노드는 데이터와 다음(혹은 이전)노드 참조를 가진다. 보통 첫 번째 노드인 Head의 포인터를 저장하도록 구현하고 노드의 참조만 수정해주면 되기 때문에 맨 앞 삽입/삭제 연산을 O(1)에 할 수 있다. 또한 구현에 따라 next를 가질지 prev를 가질지 나누어지는데, 어떤 노드의 참조를 알고 있는 경우에도 구현에 따라 앞/뒤 삽입/삭제 연산이 차이가 난다. 만약 next를 가지고 있는 경우에 뒤에 삽입한다면 O(1)이겠지만 앞에 삽입한다면 해당 노드의 앞 노드를 다시 찾아야하기 때문에 O(n)이 걸린다.

데이터와 next를 가지고 있는 LinkedList

맨 앞 삽입/삭제: O(1)

-> 노드를 추가하고 참조를 수정해주기만 하면 된다.

맨 위 삽입/삭제: O(n)

-> 맨 뒤까지 찾아가는데 걸리는 시간이 O(n)

Doubly LinkedList

각 노드가 다음 노드와 이전 노드를 모두 가르키고 있는 LinkedList이다. 보통 첫 번째 노드인 Head와 마지막 노드인 tail의 포인터를 함께 저장하도록 구현하기 때문에 맨 앞/뒤 삽입/삭제 연산이 O(1)이다. 또한 특정 노드의 포인터를 알고있다면 해당 노드의 앞, 뒤에 새로운 노드를 삽입하는데 걸리는 시간이 항상 O(1)이다. 또한 새로운 노드를 삽입할 때 새로운 노드의 참조를 먼저 추가하고 next 노드의 prev 참조를 새로운 노드를 참조하도록 바꾼 후 prev 노드의 next 참조를 새로운 노드로 옮겨야 한다. prev 노드의 next 참조를 먼저 새로운 노드로 옮겨버리면 더 이상 next 노드에 접근할 수 있는 방법이 사라지기 때문이다. 노드를 삭제하는 경우에는 prev 노드의 next 참조를 삭제하는 노드 다음 노드를 가르키도록 수정하고, next 노드의 prev 참조를 삭제하려는 노드 이전 노드를 가르키도록 수정하면 된다.

Doubly LinkedList

맨 앞/뒤 삽입/삭제: O(1)

Circular LinkedList

끝 노드가 다시 시작 노드를 가르키고 있는 LinkedList이다. 이것도 노드의 참조에 따라 Singly와 Doubly로 나누어진다. 시작이 곧 끝이므로 맨 앞/뒤에 삽입/삭제하는 연산이 O(1)이다.

Circular Singly LinkedList

Circular Doubly LinkedList

맨 앞/뒤 삽입/삭제: O(1)

공통 시간 복잡도

배열처럼 Contiguous하지 않기 때문에 리사이즈가 생길 일이 없다. 단지 O(1) 삽입의 전제는 해당 자리를 가리키는 참조(선행 노드)를 이미 가지고 있는가?이다.

 

인덱스 접근: O(n)

-> 처음 위치부터 원하는 순서의 데이터가 나올 때까지 순회해야 하기 때문이다.

 

중간 삽입/삭제: O(n)

-> 삽입/삭제 연산 자체는 O(1)이지만 해당 인덱스를 찾아가는데 걸리는 시간이 O(n)이 든다. 하지만 이중 연결 리스트는 Head와 Tail 중 더 가까운 곳에서 탐색을 시작하기 때문에 상수 인자를 절약할 수 있다.

번외

자바의 LinkedList

자바의 LinkedList는 Doubly LinkedList로 구현되어있다. 따라서 끝쪽 연산(맨 앞/뒤)를 O(1)로 할 수 있고, Iterator로 순회 중 add/remove하는 경우 중간 수정이 효율적이다. (해당 노드의 포인터를 알고 있기 때문에 O(1))

 

Cache(Spatial Locality)

뜬금없이 왜 cache가 나오나 싶지만 밀접하게 연관되어있다. Array는 연속된 메모리 상에 저장된다. CPU는 메모리(RAM)에서 데이터를 가져올 때, 한 번에 1개만 가져오는 게 아니라 보통 한 덩어리(캐시 라인; 64B)를 가져와 캐시에 저장한다. 따라서 Array은 바로 옆에 있는 원소도 이미 캐시에 있을 확률이 높으므로 공간 지역성이 높아 캐시 적중률이 높다. 하지만 LinkedList는 각 노드가 메모리 여기저기 흩러져 있기 때문에 다음 노드가 다른 캐시 라인/페이지에 있을 가능성 크다. 따라서 노드당 캐시 미스로 악화되어 계속 메모리에 접근하는 추가적인 오버헤드가 발생할 수 있다.

 

추가적으로 JAVA에서 int[], long[] 같은 원시형 배열은 값들이 진짜로 연속이라 캐시 친화적이지만 ArrayList<Integer>나 Integer[]는 연속인 건 참조(포인터) 이고, 실제 객체는 힙 여기저기 흩어져 지역성이 떨어질 수 있다. 파이썬의 List나 원소로 참조를 가지는 값들은 모두 해당된다.

 

Array VS Linked List

LinkedList는 삽입/삭제 연산이 O(1)이지만 연산을 시도하려는 이전(혹은 이후) 노드의 주소를 알고 있는 경우에만 O(1)이 가능하다.  Doubly LinkedList는 원하는 노드를 가까운 쪽(min(Head, Tail))으로부터 탐색하기 때문에 O(n/2)의 시간 복잡도가 소요된다. 하지만 Array는 삽입/삭제 연산이 원소들을 이동하고 리사이즈가 일어날 수 있다.

 

따라서 정리해보자면 다음과 같다.

삽입/삭제 연산이 자주 일어나는 경우는 LinkedList

접근(Access)이 자주 일어나는 경우는 Array 라고 생각할 수 있겠다.

 

참고

https://www.geeksforgeeks.org/dsa/linked-list-data-structure/

Linked List Data Structure - GeeksforGeeks