[선형 구조] 리스트

리스트란?
추상적 자료형으로 순서를 가지고 일렬로 항목들을 나열한 구조를 말합니다.
데이터가 순차적으로 저장되어 한 줄로 연결된 형태를 띄기 때문에 선형 구조라고 합니다.
중복된 데이터의 저장이 가능합니다.
리스트는 구현 방법에 따라 배열을 기반으로 구현된 순차 리스트와 메모리의 동적 할당을 기반으로 구현된 연결 리스트로 나뉩니다.
또한, 연결 리스트는 연결 방식에 따라 단일 연결 리스트, 원형 연결 리스트, 이중 연결 리스트로 구현할 수 있습니다.

 

리스트와 집합

집합은 특정한 값들을 저장하는 추상 자료형입니다.

하지만 집합에서는 데이터들의 순서가 존재하지 않고 중복되지 않는다는 점에서 리스트와 다릅니다.

 

 

리스트와 배열

어떻게 보면 배열을 리스트의 일종이라고 할 수 있지만, 배열과 리스트는 다릅니다.

먼저 배열에 대해 정리한 후, 순차 리스트와 연결 리스트에 대해 알아 보고 배열과 리스트를 최종적으로 비교하겠습니다.

 

배열(Array)이란?
같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터의 집합입니다.
중복을 허용하고 순서가 있습니다.
배열은 연속된 메모리 공간으로 이루어져 있기 때문에 논리적 저장 순서와 물리적 저장 순서가 일치합니다.
각 원소에 붙은 번호를 index라고 부르며, index에 있는 원소에 O(1)로 바로 접근할 수 있습니다.
배열은 메모리의 특성이 정적이므로 배열의 크기를 컴파일 이전에 정해주어야 하며, 컴파일 이후에 배열의 크기를 바꿀 수 없는 고정 길이입니다.

 

• 장점

1. index를 통한 검색 및 수정이 용이합니다.(Random access 가능)
2. 연속적인 메모리 관리가 가능합니다.

• 단점

1. 컴파일 이후 배열의 크기 변동이 불가합니다.
2. 삽입/삭제시 Shift 비용이 발생합니다. -> O(n)이 소요됩니다.
3. 고정 크기이기 때문에 빈 공간이 있는 만큼 메모리가 낭비될 가능성이 있습니다.

---

• 순차 리스트 Sequential List

1. 구현 방법

순차 리스트는 배열을 기반으로 구현된 리스트입니다.

Java의 ArrayList도 순차 리스트의 예입니다.

 

2. 메모리 저장 방식

순차 리스트는 배열로 리스트를 만드는 것이기 때문에, 논리적인 순서대로 메모리에 연속적으로 저장되므로 논리적 저장 순서와 물리적 저장 순서가 일치합니다.

 

3. 가변 길이

배열처럼 컴파일 이전에 리스트의 크기를 정해줄 수 있습니다.

하지만 추가 공간이 필요하면 저장 용량을 늘릴 수 있다는 점에서 배열과 차이점이 있습니다.

 

4. 데이터 삽입/삭제

 순차 리스트에서 데이터의 삽입은 앞에서부터 순서대로 채워 나갑니다.

마지막으로 삽입한 원소의 다음 위치에 바로 데이터를 삽입한다면 O(1)의 시간이 소요됩니다.

하지만 중간에 데이터를 삽입할 때에는 삽입 위치 이후에 저장된 데이터들을 한 칸씩 뒤로 이동시켜서 빈 공간을 만든 뒤에 삽입해야 하기 때문에 O(n)의 시간이 소요될 수 있습니다.(Shift 비용 발생)

 

 삭제의 경우에도 마찬가지로 마지막 원소를 삭제하는 경우에는 O(1)이 소요됩니다.

하지만 중간에 있는 데이터를 삭제할 때에는 뒤에 저장된 데이터들을 한 칸씩 앞으로 이동시켜서 빈 공간을 메워야 하므로 O(n)이 소요됩니다.(Shift 비용 발생)

 

이처럼 순차 리스트는 데이터의 논리적인 순서와 물리적인 순서를 일치시켜야 하므로 데이터의 삽입/삭제 과정에서 데이터의 이동으로 인한 오버헤드가 발생합니다.

 

5. 데이터 조회

순차 리스트는 메모리에 연속적으로 데이터가 저장되기 때문에 index를 사용하여 빠른 조회가 가능합니다.

시작 주소(Base Address) + i*sizeof(type)으로 i번째 index에 바로 접근할 수 있어서 데이터 접근 시간은 O(1)입니다.

 

• 장점

1. index를 통한 검색 및 수정이 용이합니다.(Random access 가능)
2. 연속적인 메모리 관리가 가능합니다.
3. 동적 할당이 가능합니다.
4. 배열과 달리 중간에 빈 공간을 허용하지 않으므로 메모리 공간의 낭비가 적습니다.

• 단점

1. 삽입/삭제시 Shift 비용이 발생합니다.
2. 메모리를 추가 확장하는데 비용이 발생합니다.

 

• 연결 리스트 Linked List

1. 구현 방법

연결 리스트는 메모리의 동적 할당을 기반으로 구현된 리스트입니다.

메모리의 물리적인 위치와 순서에 상관없이 노드의 링크를 통해 논리적인 순서를 표현합니다.

노드(Node)는 데이터 필드와 연결된 다음 노드의 주소값을 가리키는 포인터를 저장하는 링크 필드로 구분되어 있습니다.

맨 마지막 노드인 tail의 링크는 Null로 표현합니다.

연결 리스트는 Tree 구조의 근간이 되는 자료구조로 Tree에서 사용되었을 때 그 유용성이 드러납니다.

 

2. 메모리 저장 방식

논리적 순서와 상관없이 노드는 메모리 곳곳에 흩어져있을 수 있습니다.

 

3. 가변 길이

필요한만큼 메모리를 동적으로 할당받아 데이터를 추가할 수 있으며, 삭제 시에는 free를 통해 공간을 삭제할 수 있는 가변 길이입니다.

 

4. 데이터 삽입/삭제

배열과 달리 List의 Head나 Tail에 새로운 노드를 추가할 때는 단순히 링크를 끊고 다시 연결해주면 되기 때문에 O(1)이 소요됩니다.

원하는 위치에 원소를 삽입하고자 할 때 해당 위치를 찾기 위해 첫번째 원소부터 탐색해야 하므로 시간복잡도는 O(n)이 소요됩니다.

특정 원소를 삭제하기 위해서도 해당 원소를 찾기 위해 첫번째 원소부터 탐색해야 하므로 O(n)이 소요됩니다.

 

5. 데이터 조회

연결 리스트의 검색은 O(n)이 소요됩니다.

찾고자 하는 데이터가 저장되어 있는 위치를 찾기 위해 첫번째 원소부터 탐색해야하기 때문입니다.(순차적 접근)

 

• 장점

1. Head/Tail에 원소를 삽입/삭제하는데 O(1)이 소요됩니다.
2. 가변 길이의 데이터를 저장하기에 유용합니다.
3. 메모리가 연속적이지 않아 동적 할당에 유리합니다.
4. 중간에 빈 공간을 허용하지 않으므로 메모리 공간의 낭비가 적습니다.

• 단점

1. 특정 데이터를 검색/삽입/삭제하는데 O(n)이 소요됩니다.
2. Random Access가 불가하여 Sequential access만 가능합니다.
3. 포인터 사용으로 인한 저장 공간 낭비가 있다.

 

---

연결 리스트의 종류

• 단일 연결 리스트

 

단일 연결 리스트

노드가 데이터와 하나의 포인터(next)로 구성되어 있고 각 노드는 다음 노드를 가리키는 단방향의 연결 리스트를 말합니다.

 

• 이중 연결 리스트

 

이중 연결 리스트

노드가 데이터와 두 개의 포인터(prev, next)로 구성되어 있고 각 노드는 앞의 노드와 뒤의 노드를 가리키는 양방향의 연결 리스트입니다.

 

• 원형 연결 리스트

 

원형 연결 리스트

단일 연결 리스트의 마지막 노드와 시작 노드를 연결시켜 원형 구조를 가지는 연결 리스트입니다.

마지막 노드의 next 포인터가 Head 노드를 가리킵니다.

 

---

• 배열과 순차 리스트, 연결 리스트 비교

배열 Array	순차 리스트 Sequential List	연결 리스트 Linked List
논리적 저장 순서가 물리적 저장 순서와 일치 O	논리적 저장 순서가 물리적 저장 순서와 일치 O	논리적 저장 순서와 물리적 저장 순서가 일치 X
메모리 공간의 연속성 O	메모리 공간의 연속성 O	메모리 공간의 연속성 X
고정 길이	가변 길이	가변 길이
조회/수정 O(1)	조회/수정 O(1)	조회/수정 O(n)
삽입/삭제 O(n)	삽입/삭제 O(n)	삽입/삭제 Head/Tail -> O(1), 특정 위치 -> O(n)
정적 할당	동적 할당	동적 할당
데이터 조회가 잦고 고정된 크기의 데이터를 관리할 때 사용	데이터 조회가 잦고 크기가 정해져 있지 않은 데이터를 관리할 때 사용	데이터 삽입/삭제가 잦을 때 사용

 

---

벡터 Vector

C++의 표준 템플릿 라이브러리 STL의 자료구조 중 하나인 벡터는 동적으로 요소를 할당할 수 있는 동적 배열입니다.

컴파일 시점에 데이터 개수를 모르는 경우에 벡터를 사용합니다. 

중복을 허용하고 순서가 있으며, Random access가 가능합니다.

따라서 index로 특정 원소를 탐색하는데 O(1)의 시간복잡도가 소요되며, 맨 뒤에 있는 요소의 삽입/삭제도 O(1)이 소요됩니다.

뒤에서 삽입하는 push_back()의 경우 O(1)의 시간이 걸리는데, 사실 벡터 크기가 증가될 때 amortized 복잡도를 가지기 때문에 O(1)에 가깝습니다.

벡터의 삽입

리스트처럼 삽입을 할 때마다 크기가 증가하는 것이 아니라, (2의 제곱승 + 1)마다 크기를 2배로 늘려줍니다.

Ci = i번째 push_back()을 할 때 드는 비용 = 1 or 1 + 2^k

두 번째 시그마 공식의 경우, 2^(log2 n + 1) - 1 = 2n - 1 입니다.

즉, 3n - 1을 n으로 나누면 평균적으로 드는 비용을 알 수 있고, 3이므로 상수 시간보다는 크지만 상수에 가까운 amortized 복잡도를 가집니다.

따라서 벡터의 삽입은 O(1) 시간복잡도가 소요됩니다.

---

출처

• 참고 도서: 면접을 위한 CS 전공지식 노트 - 주홍철 지음

• https://ko.wikipedia.org/wiki/연결_리스트#단일_연결_리스트

연결 리스트 - 위키백과, 우리 모두의 백과사전