오늘은 지난번에 다뤘던 스택과 큐, 덱과 같은 선형 자료구조인 배열과 연결리스트에 대해서 알아보겠습니다.
배열 (Array)
아마 자료구조 중 가장 흔하고 익숙한 이름일것이라고 생각되는 배열은 여러개의 데이터를 저장하며 연속적인 메모리를 사용하는 자료구조입니다.
각 요소는 데이터만 가지고 있으므로 뒤에서 다룰 연결 리스트에 비해 메모리를 적게 사용합니다.
배열에서 데이터를 삽입하거나 삭제 할 때는 빈 자리를 만들거나 채우기 위해 정렬과정이 이루어지는데
이는 성능을 악화시키는 원인이 될 수 있으므로 만약 삽입과 삭제가 잦은 환경이라면 배열이 아닌 다른 자료구조를 고려해볼 필요가 있습니다.
또한, 랜덤 액세스(인덱스로 요소에 바로 접근)를 통해 탐색의 시간복잡도를 O(1)로 낮출 수 있습니다.
다만, 인덱스를 사용하지 않고 요소를 탐색 할 경우 O(n)의 시간복잡도를 가지며
삽입 및 삭제시에도 정렬과정으로 인해 O(n)의 시간복잡도를 가집니다.
배열은 정적 자료구조로 여기에서 말하는 정적과 동적은 메모리 할당에 대한 부분을 말합니다.
정적 자료구조는 최초 선언시에 크기를 명시해야 하며 이는 메모리를 아래와 같은 형태로 점유하기 때문에 크기 변경시 다른 데이터와 충돌할 수 있어 선언 이후에는 크기를 변경할 수 없습니다.
따라서 배열을 사용할 때는 데이터의 상한선을 염두에 두고 크기를 정해야 하는데
배열의 크기에 비해 요소가 적다면 메모리 낭비를 유발할 수 있고
반대로 배열의 크기보다 요소의 수가 많아진다면 사이즈를 변경할 수 없으므로 더 큰 크기의 배열을 새로 선언해 요소를 모두 옮겨야하는 불편함이 있습니다.
예를 들어, 위 사진처럼 배열의 크기를 3으로 선언했는데 이보다 더 많은 요소를 저장해야 한다면 새로운 배열을 선언한 후 요소들을 옮겨주어야 합니다.
배열의 장단점
장점
- 랜덤 액세스를 통해 O(1)의 시간복잡도로 요소에 접근할 수 있다.
- 각 요소는 데이터만 가지고 있기 때문에 뒤에서 다룰 연결리스트에 비해 메모리를 적게 사용한다.
단점
- 연속적인 메모리 사용으로 인해 확장이 불가하다.
- 사이즈가 고정적이기 때문에 메모리 낭비를 유발할 수 있다.
- 데이터의 삽입 및 삭제 시 요소를 정렬해주는 연산이 수행되므로 이러한 작업이 잦다면 성능에 악영향을 줄 수 있다.
JS의 배열과 자료구조의 배열은 같을까?
다릅니다.
JS의 배열은 크기가 유동적으로 변하기때문에 동적 배열이라고 부르며
자료구조의 배열은 크기가 고정적이므로 정적 배열이라고 부릅니다.
연결 리스트 (Linked List)
연결리스트는 데이터와 포인터를 가진 여러개의 노드로 구성되어 있으며 정적 자료구조인 배열의 단점을 보완한 동적 자료구조입니다.
메모리카드의 파일시스템에 자주 사용되는 FAT가 연결리스트의 대표적인 예입니다.
노드의 구성 요소인 포인터는 다른 노드의 주소를 저장하고 있어 이를 통해 요소들을 순차적으로 탐색할 수 있습니다.
노드의 종류로는 가장 앞에 위치한 헤드노드, 가장 마지막에 위치한 테일노드가 있고
테일노드의 포인터는 null을 가르키게 됩니다.
따라서 탐색 중 null을 만나게 되면 마지막 요소까지 모두 탐색했다는 뜻이므로 작업을 멈추게 됩니다.
배열과 비교해 연결리스트는 삽입과 삭제가 간편한데 그 이유는 포인터가 저장한 주소만 변경해주면 되기 때문입니다.
연결 리스트는 동적 자료구조로서 배열과 달리 크기를 늘리고 줄이는게 자유롭습니다.
인덱스를 이용하는 배열과 달리 포인터를 통해 다음 노드에 접근하기 때문에 메모리상에서 데이터가 흩어져 있더라도 접근이 가능하며 필요한만큼의 메모리만 사용하기 때문에 메모리를 낭비하지 않는다는 장점이 있습니다.
다만, 배열과 달리 노드에 포인터가 추가되므로 각 노드가 배열의 요소보다 더 많은 메모리를 사용하며 랜덤 액세스가 불가능하므로 탐색의 시간복잡도는 O(n)이 됩니다.
또한, 포인터가 한개라도 잘못된다면 그 이후의 데이터를 모두 잃어버릴 수 있기 때문에 불안정한 자료구조에 속합니다.
연결 리스트는 3가지의 종류를 가지고 있고 방금 설명한 연결리스트를 단일 연결리스트(= Singly Linked List, 단순 연결리스트)라고 합니다.
이 외에도 이중 연결 리스트, 원형 연결리스트가 있습니다.
연결리스트의 장단점
장점
- 삽입 및 삭제시 정렬 과정이 없어 배열에 비해 작업이 빠르다.
- 동적 자료구조로서 필요한만큼의 메모리만 사용한다.
단점
- 랜덤 액세스가 불가능하기 때문에 탐색 및 접근에 O(n)의 시간복잡도를 가진다.
- 만약 한개의 포인터라도 끊어지게 되면 이후의 데이터들을 모두 잃어버릴 수 있다.
이중연결리스트 (Doubly Linked List)
이중연결리스트는 각 노드가 이전과 다음 노드에 접근할 수 있도록 노드 당 포인터를 2개씩 가집니다.
이는 만약 포인터 한개가 끊어지더라도 나머지 포인터를 통해 다시 복구가 가능하기 떄문에 단일 연결리스트의 단점을 보완하는 더 안정적인 자료구조 입니다.
다만, 삽입과 정렬 시 늘어난 포인터로 인해 작업량이 더 많고 메모리또한 더 많이 사용합니다.
원형연결리스트 (Circular Linked List)
테일노드가 null이 아닌 헤드노드를 가르켜 순환할 수 있도록 한 자료구조로 주로 큐를 구현할 때 많이 사용됩니다.
정리
| 배열 | 연결리스트 | |
|---|---|---|
| 메모리 할당 | 정적 (연속적, 컴파일 시 결정됨) | 동적 (비연속적, 런타임 시 결정됨) |
| 메모리 사용량 | 작다 | 크다 |
| 단점 | - 사이즈가 고정되어 있어 메모리 낭비를 유발할 수 있고 확장을 위해 새로운 배열을 선언해야 함 - 데이터의 삽입 삭제시 요소에 대한 정렬과정 필요 | - 랜덤 액세스가 불가하여 탐색의 시간복잡도가 O(n) - 포인터로 인해 각 요소의 메모리 사용량이 배열보다 크다. |
