[선형 자료 구조] 동적 배열과 연결 리스트

1. 선형 자료 구조

 

일렬로 늘어선 같은 자료 여러개를 저장하기 위한 가장 기초적인 자료구조는 배열이다.

 

배열과 같이 일렬로 늘어선 자료들을 저장하기 위한 자료 구조인 동적 배열과 연결 리스트를

 

선형 자료 구조라고 한다.

 

2. 동적 배열(dynamic array)

 

배열의 큰 문제 중 하나는 배열의 크기를 지정해야하며, 그 이상의 자료를 집어 넣을 수 없다는 것이다.

 

이와 같은 문제를 해결하기 위해 만들어진 자료구조가 동적 배열이다.

 

동적 배열은 자료의 개수가 변함에 따라 크기가 변경된다.

 

동적 배열은 일반 배열처럼 언어 차원에서 지원되는 기능이 아니라

 

배열을 이용해 만들어 낸 별도의 자료 구조이고, 언어의 표준 라이브러리에 대개 포함되어있다.

 

3. 동적 배열의 특성

 

- 원소들은 메모리의 연속된 위치에 저장된다. (캐시의 효율성)

 

- 주어진 위치의 원소를 반환하거나 변경하는 동작을 O(1)에 할 수 있다.

 

- 배열의 크기를 변경가능하다. 이 동작을 수행하는데 배열의 크기 N에 비례하는 시간이 걸린다.

 

- 주어진 원소를 배열의 맨 끝에 추가함으로써 크기를 1 늘리는 append()연산을 지원한다. (상수시간이 걸린다)

 

 

 

이와 같은 특성을 구현하기위해 

동적 배열은 동적으로 할당받은 배열을 사용한다. (new연산 등으로 할당받은 고정 길이 배열)

 

동적 배열의 크기가 바뀌어야할 때는 단순하게 새로 할당받고 복사한다.(O(N))

항상 배열의 크기는 커질 때를 대비해서 여유분의 메모리를 미리 할당받아 둔다.(capacity)

그리고 배열이 이미 할당한 메모리에 꽉 찼을 때

더 큰 메모리를 할당받아 배열의 원소를 그 쪽으로 전부 옮긴다. (재할당)

 

텅 빈 배열로 시작해 N번 append() 연산을 하면 (재할당시 M만큼 여유분)

재할당의 수 => K = O(N/M) 이다.

N이 커지면 결국 K = O(N) 이된다.

 

재할당마다 복사하는 원소의 수는 M, 2M.. KM로 증가 하므로 전체 복사하는 원소의 수는

 

k(k+1)/2 * M = O(K^2) = O(N^2) 이다.

 

N번의 append() 연산을 하는데 드는 총 시간이 O(N^2)이라면 

한번의 append() 연산에 드는 시간은 평균적으로 O(N^2)/N = O(N)이 된다.

 

총 상수시간에 append() 연산이 수행될려면 재할당마다 정해진 개수의 여유분을 할당하는게 아니라

 

현재 가진 원소의 개수에 비례해서 여유분을 확보하면 전체 평균이 상수시간이 될 수 있다.

 

=> 용량을 두배로 늘림.

=> 항상 복사의 수가 배열의 크기에 선형으로 비례함.

 

k 번의 재할당이 일어나게 되면 

재할당 횟수	1	2	3	4	...	k-2	K-1	k
새배열 크기	2	4	8	16	...	2^(k-2)	2^(k-1)	2^k
복사 양	1	2	4	8	...	2^(K-3)	2^(K-2)	2^(k-1)

 

N번 append =>

재할당의 수 => k

k= lgn   ( N의 개수가 재할당 시점이면 2의 제곱형태)

 

모든 복사하는 원소들의 수는 다음과 같다.

2^(k+1)-1

 

k = lg n 이므로

 

2^(lgn+1)-1 = 2*n -1

 

즉, 복사하는 원소의 수는 O(N) 이기 때문에

append()연산을 N번 실행하는 총 수행 시간은 O(N)이다.

따라서 append() 한번에 드는 시간은 평균적으로 O(1)이다.

 

이와 같이 동적배열의 용량 관리는 동적 배열의 효율성에 큰 영향을 끼친다.

그러므로 동적배열을 사용할 때 재할당을 최소한하도록 용량을 미리 늘려두자.

 

c++: reserve()

자바: ensureCapacity()

c#: capacity 프로퍼티 설정.

 

 

4. 연결 리스트

 

배열 원소들의 순서를 유지하면서 임의의 위치에 원소를 삽입하거나, 임의의 위치에서 원소를 삭제하는 것은 시간이 오래 걸리는 작업이다.

 

해당 위치에 있는 원소 뒤쪽들을 전부 이동시켜야하기 때문이다.

 

이와 같은 문제를 해결하기위해 연결 리스트 자료구조가 만들어졌다.

 

연결리스트는 

 

원소들의 메모리가 흩어져있고, 

 

이전 원소를 가리키는 포인터와 

다음 원소를 가리키는 포인터를 가지고있는 방식으로 구현되어있다.

 

원소의 내용물과 포인터들의 집합을 리스트의 노드(node)라고 부른다.

 

struct ListNode {
    int element;
    ListNode *prev, *next;
    };

 

배열과 달리 연결 리스트에서는 메모리 여기저기에 노드들이 있어서 특정 위치 값을 찾기 힘들다

 

i번째 노드를 찾으려면 머리에서부터 하나씩 포인터를 따라가며 해당 노드를 찾을 수 밖에 없다.

 

결과적으로 노드를 찾는데 O(N) 이 걸린다.

 

노드를 추가하거나 삭제하는 것은 바로 이전 이후 노드들의 포인터 값만 바꾸면 되기 때문에 

삭제 삽입은 O(1)이다.

 

c++ : stl -> list

자바, c# -> Linkedlist

 

5. 연결 리스트 연산 응용

 

잘라 붙이기(splicing)

 

다른 리스트를 통째로 삽입하는것 또한 상수시간에 해결할 수 있다.

하지만 연결 리스트의 크기는 상수시간안에 알 수 없어서

지원하지 않는 언어들이 있다.

c#, 자바 : 리스트 크기를 구하는 연산을 상수시간에 지원하는 대신 잘라 붙이기x (추가 삭제마다 업데이트)

c++: list 의 splice()

 

삭제했던 원소 돌려놓기

 

양방향 연결 리스트의 장점중 하나로

노드의 삭제는 자신의 포인터를 바꾸는게 아니라 좌 우 노드의 각각의 포인터만을 변형한다.

그러므로 해당 노드는 이전의 위치를 여전히 저장하고 있고

이는 다시 돌려 놓을 수 있음을 의미한다.

 

하지만 이 방법은 이전 이후 노드들이 삭제된 상태에서 수행하면

리스트가 망가지기 때문에, 항상 삭제한 순서의 반대로 복구가 이루어져야한다.

 

이 연산은 프로그램에서 되돌리기(undo) 연산을 지원하는 데 유용하게 쓸 수 있다.

-> Dancing Links

또는 조합 탐색에서 문제 상태를 되돌리는 작업을 효율적으로 할 수 있다.

 

6. 동적 배열과 연결 리스트 비교

 

가장 큰 차이점은 삽입과 삭제, 그리고 임의의 원소에 접근하는 데 드는 시간이다.

 

삽입과 삭제를 할 일이 없거나 배열의 끝에서만 하면 될 경우 동적 배열이 효율적이다.

(임의의 원소 빠르게, 메모리에 연속배치 -> cpu캐시 효율 증가)

 

모든 원소들을 순회하며 삽입과 삭제를 한다면 연결리스트가 효율적이다.

 

이전/ 다음 원소 찾기	O(1)	O(1)
맨 뒤에 원소 추가/ 삭제	O(1)	O(1)
맨 뒤 이외의 위치에 추가/ 삭제	O(n)	O(1)
임의의 위치의 원소 찾기	O(1)	O(n)
크기 구하기	O(1)	구현에 따라 O(1), O(n)

 

 

- 알고리즘 문제해결전략 609p