[Section 2] 동적 배열과 연결 리스트(Linked List)의 이해

자료구조와 알고리즘 목차 보기

[INTRO] 자료구조와 알고리즘

0. INTRO

연결 리스트는 자료 구조의 한 종류이다. 이 연결 리스트의 개요에 대해 말하자면, 자료 구조의 데이터 끝에 널(NULL)이라 불리는 요소가 존재하며, 이 널(NULL) 포인트를 기점으로 데이터가 일렬로 연결된 자료구조를 일컫는다. 연결 리스트를 배열 기반으로 이해하고 그 의미에 대해 알아보자.

1.  연결 리스트의 의미

연결 리스트는 자료 구조의 한 종류로, 데이터가 연결되어 저장하는 것을 말한다. 다음의 그림을 참조하자.

 

연결 리스트의 형태

위와 같이 널 포인트를 기점으로 데이터 1과 2가 연결되어 있는 형태이므로 자료 구조를 임의로 확장하거나 축소하는 것이 가능하다. 널 포인트를 제외하고 메모리 할당이 낭비되지 않는 것이 연결 리스트의 핵심 장점이라고 할 수 있다. 연결 리스트를 형성하기 위한 추상 자료형을 고려해보자. 연결 리스트의 ADT는 크게 주요  ADT와 보조 ADT로 나뉜다. 

주요 ADT (Main ADT Operations)와 보조 ADT (Auxiliary ADT Operations)

가장 먼저 연결 리스트의 주요 ADT는 삽입과 삭제 기능이다. 이 두 가지 기능을 구현해야 한다. 그리고 보조 ADT는 리스트의 삭제, 카운트, 그리고 임의의 n번째 노드를 찾는 것이다. 이 5가지 기능을 갖추도록 ADT를 구현한 자료 구조를 연결 리스트라 부른다. 

 

그렇다면, 배열을 이용해서 연결 리스트 알고리즘을 만들 수 있지 않을까?

2. 동적 배열(Dynamic Array)의 탄생

일반적인 배열 형태의 데이터에 접근하는 데 걸리는 시간은 일정하다. 이는 원소에 접근하기 위한 인덱스(index) 데이터를 사용하기 때문이다. 예를 들어, 배열 자료의 형성은 한 번의 덧셈과 한 번의 곱셈이 수행된다. 이렇게 배열 자료의 생성은 간단하고 자료 접근에 용이한 측면을 가지지만, 데이터들이 단 하나의 자료 블록(block)에 할당되고 전체 사이즈가 고정되어있다는 단점을 가지고 있다. 

 

동적 배열은 고정된 사이즈를 가지는 배열의 단점을 없애기 위해서 탄생했다. 그 생성 원리는 비교적 간단하다. 먼저, 고정된 배열을 생성하고 첫 배열에 자료들이 모두 할당되면, 새로운 이중 배열을 생성하는 방식이다. 따라서 동적 배열은 연결 리스트 자료구조의 일종인 셈이다. 

3.  동적 배열과 연결 리스트의 차이

앞서 알아본 바와 같이, 동적 배열과 연결 리스트의 핵심적 차이는 바로 널 포인트의 유무이다. 그리고 동적 배열은 데이터의 사이즈가 고정되어 있기 때문에, 할당되는 데이터 공간의 낭비가 존재한다. 한편, 시간적 측면에서도 연결 리스트와 동적 배열 간의 차이가 존재한다. 

 

* 동적 배열과 연결 리스트의 시간 복잡도 관계는 다음과 같다.

 

ADT 기능	연결 리스트	배열	동적 배열
n번째 특정 원소로 접근	O(n)	O(1)	O(1)
헤드 부분 삽입/삭제	O(1)	O(n)	O(n)
리스트 끝 부분 삽입/삭제	O(n)	O(1)	O(1)   * 배열에 원소가 찬 경우 O(n)
중간 부분(n번째) 삽입/삭제	O(n)	O(n)	O(n)
공간 낭비 측면	O(n)	0	O(n)