03. 리스트(List)

 리스트는 자료를 순서대로 저장하는 자료구조를 말한다. 여기서 '순서'는 '한 줄로 서기'에서 '한 줄'을 말한다. 즉, 여러 개의 자료가 일직선으로 서로 연결된(Sequential) '선형 구조'를 의미한다. 여기서 C언어에서 제공하는 배열을 떠올릴 수도 있다. 실제로 배열이 리스트를 구현하는 가장 직관적이고 단순한 방법이며 이를 ArrayList라고 부른다. 그리고 포인터를 이용한 방법이 있다. 포인터를 이용한 방법은 Node라는 특별한 자료구조를 이용하여 저장할 Data와 다음 Node를 가리키는 Link를 가지며 LinkedList라고 부른다.

ArrayList

 ArrayList는 배열로 List를 구현한 형태를 말한다. 배열에서 리스트 자료구조를 구현할 때 몇 가지 고려해야 할 사항이 있다. 예를 들어 아래 그림의 ①단계에서 8개의 자료 중 2번째 자료인 20을 제거한다고 가정해 보자. 먼저 2번째 자료를 제거해야 한다. 그 후 3번째 자료를 한 칸씩 이동시켜야 될 것이다. 이과정을 그림을 통해 나타내면 다음과 같다.

 위 그림의 ③단계에서 한 칸씩 이동시킨 이유는 중간 공백을 제거하기 위해서이다. 리스트는 자료가 순서대로 연속해서 저장되어 있어야 하기 때문에 중간의 공백을 제거해야 한다. 왜냐하면, 이러한 중간의 공백은 새로운 자료를 추가할 수 없게 하여 공간의 낭비를 발생시키기 때문이다. ②단계와 같이 칸이 계속 비어 있다고 가정해 보면 분명 배열상에는 빈 공간이 낭비되고 있다는 것을 볼 수 있다.

 

 이제 ③단계에서 자료를 추가하는 경우를 생각해 보자. 41과 11사이에 새로운 자료 100을 추가하고 싶다면 배열 기반의 리스트에서는 어떻게 처리해야 할지 아래 그림을 통해 살펴보도록 하자.

 배열 리스트의 중간에 새로운 자료를 추가하기 위해서 위 그림에서 처럼 자료 '11'에서 부터 모두 한 칸씩 이동시켜야 3번째 자리에 새로운 자료를 저장할 수 있다.

 자료를 추가할때 생각해야 하는 부분이 한 가지 더 있다. 바로 List에 값을 추가하려 할 때 배열에 공간이 모두 사용되고 있는 상태일 때 문제가 된다.

이럴 땐 조금 더 긴 배열을 하나 생성해서 값을 복사한 뒤에 값을 추가해야 한다.

 반대로 값이 여러개 삭제가 되어 배열이 공간을 차지하고 있다면 짧은 배열을 하나 생성하여 값을 복사한 뒤 이전 배열을 삭제하는 방법도 있다.

이렇듯 ArrayList는 Array의 Index를 사용해서 List의 원소에 접근하기는 쉽지만 값의 추가와 삭제에서 많은 연산이 필요하다.

LinkedList

다음으로는 포인터를 이용한 방법이다. 포인터를 이용한 리스트 구현은 LinkedList라고 불린다. ArrayList에서는 Array를 이용해서 순서대로 자료를 저장하여 순서를 나타낼 수 있지만 LinkedList에서는 물리적으로 떨어져 있는 자료를 순서대로 연결시킬 수 있도록 Node를 사용한다. Node는 포인터를 사용하기 때문에 논리적인 순서는 순차적이지만 물리적 위치는 순서대로 인접해 있지 않다. Node는 다음 그림과 같다.

Node의 구조

LinkedList는 자료(Data)와 링크(Link)로 구성된 노드(Node)들로 구성된다. 노드는 연결 리스트의 모든 연산에서 기본 단위가 된다. 자료를 저장하는 부분은 정수(int) 실수(float) 같은 단순한 데이터 타입뿐 아니라 복잡한 구조체(struct) 정보도 저장할 수 있으며, C외 다른 언어의 경우 class같은 다양한 데이터 타입의 자료를 저장할 수 있다. 링크 부분은 포인터와 같이 다음 노드의 주소를 저장하여 현재 노드와 연결된 다음 차례의 노드를 가리킨다. 연결리스트의 제일 마지막 노드는 연결되는 다음 노드가 더 없으므로 NULL값으로 설정된다.

연결리스트는 사용되는 노드와 링크의 종류에 의해 Singly LinkedList, Circular Linked List, Doubly Linked List 3가지를 들 수 있다.

위 그림에서 알 수 있듯이 Singly LinkedList는 나머지와 비교하여 LinkedList의 가장 기본이 되는 간단한 구조를 가지고 있다. Circular LinkedList는 단순 연결 리스트와 거의 동일하지만 마지막 노드가 다시 첫 번째 노드와 연결되어 원형을 이루는 구조라는 점에서 차이가 있다. 마지막으로 Doubly LinkedList는 노드 사이의 링크가 양방향으로 있다는 점에서 차이가 있다.

연결 리스트의 특성을 비교할 때 이전(previous)노드의 접근 연산이 주요한 차이점이다. 단순 연결 리스트는 특정 노드에서 이전 노드에 접근하기 위해서는 첫 번째 노드부터 새로 순회해야 한다. 이와는 대조적으로 이중 연결 리스트는 양방향 링크를 사용하기 때문에 특정노드의 이전 노드에 대한 직접 접근이 가능하다.