연결 리스트

Linked List

1 개요

자료구조의 일종으로, Linked List라는 말 그대로 어떤 데이터 덩어리(이하 노드Node)를 저장할 때 그 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식으로 자료를 저장한다. 예를 들어 한 반에 있는 학생들의 자료를 저장한다면, 학생 하나하나의 신상명세 자료를 노드로 만들고, 1번 학생의 신상명세 자료에 2번 학생 신상명세가 어디있는지 표시를 해 놓는 방식이다. 쉽게 생각하면 자료를 비엔나 소시지마냥 줄줄이 엮어놓은 것이다.

배열이 철수 1번, 영희 2번, 민수 3번, 순이 4번...식으로 자료의 순번을 맞춘다면, 연결리스트는 철수 다음 영희, 영희 다음 민수, 민수 다음 순이....식으로 자료를 연결해놓는다. 따라서 배열과는 달리 새로운 자료, 즉 노드를 뒤에 연결하거나 중간에 노드 몇개를 껴놓는 것이 쉽다. 그러나 배열에서는 자료마다 번호가 있어서 특정한 자료를 불러내기가 편리한 반면, 연결리스트는 자료 번호가 없이 그저 연결 관계만 있기 때문에 특정한 노드를 불러내기 어려운 단점이 있다.

배열에 비해 데이터의 추가/삽입 및 삭제가 용이하나 순차적으로 탐색하지 않으면 특정 위치의 요소에 접근할 수 없어 일반적으로 탐색 속도가 떨어진다. 즉 탐색 또는 정렬을 자주 하면 배열을, 추가/삭제가 많으면 연결 리스트를 사용하는 것이 유리하다. 단, 연결 리스트라고 해서 반드시 순차 탐색만 해야 한다는 법은 없다. B+tree 자료구조는 연결 리스트에 힙을 더한 것 같은 모양새를 갖고 있는데 이 자료구조는 데이터의 추가/삭제/정렬/조회 모두에 유리하다. 단점은 그 구현의 복잡도. 물론 여러분이 직접 구현할 필요는 전혀 없다. 데이터베이스와 파일시스템이 이 B-tree의 구현체니까.

또한 배열은 크기를 크게 키우기가 어려운 단점이 있다. 연속된 메모리 공간을 할당받아야 하는데 크기가 커지면 그만한 '연속된' 공간을 할당하기가 어려워진다. 요즘 컴퓨터는 페이징 개념을 도입해서 메모리를 관리하기 때문에 연속된 큰 공간을 할당하는 작업도 무리 없이 해내긴 하지만 그렇다 하더라도 배열은 자기가 안 쓰는 공간까지 전부 예약해두고 있어야 하기 때문에 공간 낭비가 생긴다.

2 구현 방법

일반적으로 구조체와 그 포인터로 구성된다. 포인터가 없는 Java언어의 경우에는 포인터 역할을 수행하는 레퍼런스로 구현한다.

2.1 단순 연결 리스트 (Singly Linked List)

다음 노드에 대한 참조만을 가진 가장 단순한 형태의 연결 리스트이다. 가장 마지막 원소를 찾으려면 얄짤없이 리스트 끝까지 찾아가야 하기 때문에(O(n)), 마지막 원소를 가리키는 참조를 따로 가지는 형태의 변형도 있다. 보통 큐를 구현할 때 이런 방법을 쓴다.

이 자료구조는 Head노드를 참조하는 주소를 잃어버릴 경우 데이터 전체를 못 쓰게 되는 단점이 있다. 다음 노드를 참조하는 주소 중 하나가 잘못되는 경우에도 체인이 끊어진 것마냥 거기부터 뒤쪽 자료들을 유실한다. 따라서 안정적인 자료구조는 아니다.

파일 시스템 중 FAT 파일 시스템이 이 단순 연결 리스트로 파일 청크를 연결하는데 그래서 FAT파일시스템은 파일 내용 일부가 손상될 경우 파일의 상당 부분을 유실할 수 있고 랜덤 액세스 성능도 낮다.

2.2 이중 연결 리스트 (Doubly Linked List)

다음 노드의 참조뿐만 아니라 이전 노드의 참조도 같이 가리키게 하면 이중 연결 리스트가 된다. 뒤로 탐색하는 게 빠르다는 단순한 장점 이외에도 한 가지 장점이 더 있는데, 단순 연결 리스트는 현재 가리키고 있는 노드를 삭제하는 게 한 번에 안 되고 O(n)이 될 수밖에 없는데 비해이중 연결 리스트에서 현재 노드를 삭제하는 것은 훨씬 간단하다. 대신 관리해야 할 참조가 두 개나 있기 때문에 삽입이나 정렬의 경우 작업량이 더 많고 자료구조의 크기가 약간 더 커진다.

단일 연결 리스트보다는 손상에 강한 편이다. Head와 Tail노드를 갖고 있다면 둘 중 하나를 가지고 전체 리스트를 순회할 수 있기 때문에 끊어진 체인을 복구하는 게 가능하다. 단일 연결 리스트는 Tail노드로는 리스트 순회가 불가능하고 Head노드 유실시 전체 자료를 다 잃어버린다. 단점은 이런 보정 알고리즘을 구현하지 않았을 경우에는 오히려 손상에 더 취약해진다는 것이다. 예를 들어 next 포인터는 갱신을 했는데 prev포인터는 갱신하지 않았을 경우 prev포인터를 따라가는 순회에서 도달 불가능한 '잃어버린' 노드가 발생한다.

2.3 원형 연결 리스트 (Circular linked list)

단순 연결 리스트에서 마지막 원소가 널 대신 처음 원소를 가리키게 하면 원형 연결 리스트가 된다. 이와 비슷하게, 이중 연결 리스트의 처음과 끝을 서로 이으면 이중 원형 연결 리스트를 만들 수 있다.

스트림 버퍼의 구현에 많이 사용한다. 이미 할당된 메모리 공간을 삭제하고 재할당하는 부담이 없기 때문에 큐를 구현하는 데에도 적합하다.

2.4 청크 리스트(Chunked List)

배열과 리스트의 장점을 합친 것. 리스트의 멤버가 배열이다. CPU에 캐시 기능이 있는 경우 지역성Locality이 떨어지는 연결 리스트는 심각한 성능 저하를 불러온다. 이를 보완하기 위해 리스트의 멤버를 레코드의 배열로 하는 것이다. 이 청크 리스트의 발전형이 바로 B+tree다.

3 분석

배열과는 달리 첫번째 데이터의 추가/삭제가 O(1)의 시간안에 수행된다. 배열의 경우 데이터를 추가 또는 삭제할 때 해당 지점 뒤쪽의 데이터를 모두 이동해야 하나 연결 리스트는 그럴 필요가 없다. 하지만, 첫번째가 아닌 중간에 있는 데이터들의 추가/삭제는 해당 데이터를 검색하는데까지 시간이 걸리기 때문에 O(n)의 수행시간을 갖게된다.

다만 탐색시에는 문제가 되는데 각 데이터에 한번에 접근할 수가 없어 항상 순차적으로 도달해야 한다. 이 때문에 데이터 검색에 쥐약이다. 정렬은 O(nlogn)시간에 가능하다. 이 단점을 해결한 것이 위에서 여러 번 언급한 그 B+tree.

4 C에서의 활용

구조체를 활용해서 정의한다.

struct LinkedList {
int number;
char name[20];
...
struct Linked_List* next;
};

연결리스트 데이터 하나의 노드는 구조체 인스턴스 한 개에 대응한다. 이 안에 넣고자 하는 데이터(숫자, 문자 등등...)을 넣고, 거기에 (이전 노드와) 다음 노드의 위치를 표시해주는 포인터를 포함시키면 연결리스트가 정의된다. 위 예시는 단일 연결 리스트의 예로서, 여기에서 Previous를 추가하면 이중 연결 리스트가 된다.

    struct Linked_List* next;

특이할 점은 노드 자신의 위치를 표시하기 위한 자기참조 구조체라는 개념이다. 자기 자신을 구조체 멤버로 가지지 못하는 대신 자기 자신 타입의 포인터를 멤버로 가짐으로써, 스스로의 주소값을 표현하는 것이다. 왜 구조체가 자기 자신을 멤버로 못 가지냐고? 구조체는 항상 고정 크기의 메모리 공간을 할당받아야 하는데 자기 자신을 멤버로 가진다면 그 '고정 크기'를 알 수 없기 때문이다. 그러나 자기 자신에 대한 포인터는 크기가 항상 4바이트(32비트 OS)나 8바이트(64비트 OS)로 같다. 그래서 구조체의 전체 크기를 계산 가능하다.

그럼 Java에서는 어떻게 자기 자신을 멤버로 포함시키냐고? 자바의 클래스는 레퍼런스 참조를 한다. 레퍼런스라 함은 상수 타입의 포인터와 같은 개념이다. 레퍼런스는 상수이면서 연산이 불가능한 포인터와 동일하다.

사용할 때는 head->next->next->name 하는 식으로 사용한다. 조회 메서드에 대해 설명하자면

List * get(int index) {
List *head = HEAD;
List *cur = head;

for(int i=0; i<index; i++) {
cur = cur->next;
}
return cur;
}

이런 식으로 사용한다.

4.1 C++에서의 활용

C++에서 추가된 클래스 기능을 이용하여 정의하는 걸 빼면 C에서와 별반 다를 것은 없다. 다만 클래스는 스트럭트 타입의 변수와는 달리 안에 함수를 정의 가능하므로, 자주 쓰는 기능을 클래스 함수로 정의해놓은 후 조금 더 쾌적하게 연결리스트를 사용할 수 있다.

5 LISP과 연결 리스트

LISP에서 기본으로 제공하는 리스트는 기본적으로 리스트를 생성하는 cons 연산에 의해 결합된 cell 이 연결된 단순 연결형 리스트이다. 구현 상 리스트에 원소를 추가할 때에는 앞쪽에 붙는다. 예를 들어 (1 2 3) 이라는 리스트는 (cons 1 (cons 2 (cons 3 nil))) 이라는 표현과 동일하다.

여기에 리스트의 첫 번째 요소를 가져오는 car, 첫 번째를 제외한 나머지 리스트를 구하는 cdr을 사용하여 루프를 돌면 매우 편리하게 리스트를 사용할 수 있다. 리스트가 비었는지 알아보려면 car 을 수행하여 첫 번째 요소가 nil 인지 검사하면 되고, 길이를 구하려면 nil이 나올때 까지 루프를 돌면서 1씩 더한다든지 하는 식이다. (물론 이는 단순한 것을 예로 든 것으로, 이러한 기본적인 함수는 이미 다 구현되어 제공된다.)

사투리 중에서는 필요성에 의해 양방향 리스트를 다른 자료형으로 구현하여 단순 연결형 리스트와 함께 기본 데이터 타입으로 지원하는 경우도 종종 있다. 이 경우는 리스트라고 안부르고 벡터 등 다른 명칭으로 불린다.