CS스터디

[CS스터디] Array와 LinkedList

by VICENTE97P4

March 11, 2022, 4:16 p.m.

Array와 Linked List의 차이

1. 접근

Array는 Random Access를 지원합니다. 요소들을 인덱스를 통해 직접 접근할 수 있습니다.

따라서 특정 요소에 접근하는 시간복잡도는 O(1)입니다.

이에 반해 Linked List는 Sequential Access를 지원합니다. 어떤 요소를 접근할 때 순차적으로 검색하며 찾아야 합니다. 시간복잡도는 O(N)입니다.

- Random Access: 어떤 요소에 바로 접근하는 것

- Sequential Access: 어떤 요소에 접근할 때, 처음부터 차례차례 접근하는 것

따라서 특정 요소에 접근할 때 시간복잡도는 O(N)입니다.

2. 삽입과 삭제

배열에서 삽입과 삭제는 O(N)이 소요되지만, Linked List에서 삽입과 삭제는 O(1)이 소요됩니다.

그런데 사실 배열도 O(1)에 삭제하는 듯한 효과를 줄 수 있습니다.

삭제할 자리에 데이터가 없음을 의미하는 값을 넣어주면 됩니다.

visited = [0,1,2,3,4,5,6,7]

이런 배열이 있다고 할 때 index=4인 원소를 지우고 싶으면

visited[4] = None

이렇게 None이나 null 값을 넣어주면 됩니다.

하지만 이럴 경우에는 삭제의 의미가 많이 퇴색됩니다.

데이터를 삭제했음에도 불구하고 메모리를 차지하고 있고, 배열을 순회할 때도 삭제한 데이터까지 봐야 하기 때문입니다.

그래서 array는 삭제 때는 오른쪽에 있는 값들을 삭제한 위치까지 왼쪽으로 한 칸씩 밀어줘야 하고,

삽입 때는 해당 칸이 비어있다면 바로 삽입하면 되기 때문에 O(1)이 소요됩니다.

만일 칸이 차있다면, 삽입한 위치 오른쪽에 있는 값들을 오른쪽으로 한 칸씩 밀어줘야 하기 때문에 O(N)이 걸립니다.

그래서 삽입과 삭제에는 array보다는 linked list가 더 유리한 측면이 있습니다.

3. 메모리 할당 위치

배열은 컴파일 타임에 메모리가 할당됩니.(정적 메모리 할당)

반면 Linked List는 새로운 요소가 추가될 때 런타임에 메모리를 할당합니다.(동적 메모리 할당)

따라서 배열은 stack 영역에 메모리 할당이 이루어지고, Linked List는 Heap 영역에 메모리 할당이 이루어집니다.

array는 요소들이 인접한 메모리 위치에 연이어 저장됩니다. 그래서 길이가 고정되어 있죠.

반면 Linked List는 새로운 요소에 할당된 메모리 주소가 Linked List의 이전 요소에 저장됩니다.

그래서 요소들이 인접한 메모리 위치에 연이어 저장되지 않습니다.(작은 확률로 그럴 수도 있겠죠..)

그래서 spacial locality 측면에서 봤을 때 array가 linked list보다 좋습니다.

Linked List

자, 그럼 linked list를 봅시다.

linked list를 array로 구현하면 어떨까요?

이는 비효율적입니다.

일단, 배열은 최대 크기가 정해져있습니다. 그래서 크기 이상의 node를 저장할 수 없는데, 이는 linked list의 개념과 맞지 않습니다.

그리고 삽입과 삭제에도 성능이 떨어집니다.

O(N)이 걸리기 때문이죠.

N개의 연속적인 insert를 한다고 하면 O(N^2)이 걸리게 됩니다.

이는 spacial locality로 인한 득보다 실이 더 크게 됩니다.

그래서 메모리 상에서 연속하지 않더라도 이전 node에 현재 node의 주소값을 저장해서 이어지게 하는 방식을 사용합니다.

위 그림에서는 A1만 알면 A2, A3, A4, A5까지 모두 탐색할 수 있죠.

(A1, A2,,, A5의 메모리 주소가 연속하지 않음도 나타나있죠)

Doubly Linked List

그런데 이러한 단방향 연결은 이전 노드를 참조하고 싶을 때 다시 처음 노드부터 참조해야 한다는 단점이 있습니다.(물론 변수를 두 개 둬서 이전 노드도 저장하고 다닐 수도 있습니다^^)

그래서 앞 뒤 노드 모두를 연결하는 doubly linked list가 나왔습니다.

insert와 delete에는 앞 뒤 노드 모두와 연결을 재설정해야 하기 때문에 약간 시간이 더 걸리지만 역시 O(1)밖에 걸리지 않습니다.

위 그림은 insert 개념도입니다. delete도 비슷하고 쉬우므로 생략하도록 하겠습니다.

doubly linked list는 상황에 따라 탐색의 방향이 바뀌는 경우에 효율적이다는 장점이 있습니다.

이전 node의 주소값을 저장하는 메모리가 추가적으로 필요하고 구현이 조금 더 복잡해진다는 단점이 있습니다.

Circular Linked List

맨 마지막 node로 가면 끝이 아니라 다시 처음으로 돌아와 순환하는 형태인 circularly linked list도 있습니다.

circular linked list의 장점은 원하는 순서의 node를 탐색할 때 n/2의 시간이 걸린다는 것입니다.

절반보다 뒤쪽에 있으면 꼬리 방향으로 탐색을 하면 되니까요.

그에 따른 노드의 추가, 삭제에도 doubly linked list보다 장점이 있습니다.

단점은 doubly linked list와 동일하게 메모리가 추가적으로 들고 구현이 복잡해진다는 것입니다.

사용 사례

- 네트워크 메시지 전달: 메시지는 패킷으로 나뉘고 각 패킷에는 다음 키가 있으므로 수신자 쪽에서 쉽게 클럽을 만들 수 있습니다.

- 브라우저 캐시(앞, 뒤로 버튼)

Vector와 Array

자바에는 Vector 클래스와 Array 클래스가 있습니다.

Vector class

- 예전 자바에서 제공했던 레거시 클래스입니다.

- 필요에 따라 크기를 동적으로 조절할 수 있는 동적배열입니다.

- 동기화(Thread safe) 되어있으며 하나의 스레드만 벡터의 메소드를 호출할 수 있습니다.

- 배열 크기를 증가시킬 때 2배로 증가시킨다.

- load factor: 1

ArrayList

- 동적배열입니다.

- load factor: 1

- 1.5배로 증가시킨다.

배열의 크기를 늘릴 때 새로운 배열을 만들고 원소를 옮깁니다.

이 과정에서 걸리는 시간은 N인데, 그래도 평균적인 시간은 O(1)이라서 삽입에 O(1)이 걸린다고 생각하면 됩니다.

Vector는 동기화되어있기 때문에 ArrayList보다 느립니다.

배열의 크기를 증가시킬 때 Vector는 2배, ArrayList는 1.5배 증가합니다.

멀티스레드 환경이 아닌 경우 ArrayList를 사용하는 것이 바람직합니다.

sequential search, binary search, insert 시간복잡도

자료구조 26 view 1264