19-2.연결 리스트

19-2-가.단순 연결 리스트

앞 절에서 만들었던 동적 배열은 같은 타입의 데이터 여러 개를 저장할 수 있는 가변 크기를 가지는 자료 구조이다. 이런 목적으로 사용할 수 있는 또 하나의 자료 구조가 바로 연결 리스트(Linked List)인데 이 절에서는 연결 리스트에 대해 간단하게 연구해 보기로 하자. 연결 리스트와 동적 배열은 완전히 용도가 같은 자료 구조로서 서로 대체 가능하지만 구성 원리나 관리 방법은 질적으로 다르다. 연결 리스트의 대체 자료 구조는 배열이 아니라 동적 배열임을 주의하자.

배열의 가장 큰 특징은 요소들이 물리적으로 인접한 메모리 영역에 연속적으로 배치된다는 점이다. 그래서 첨자 연산이 빠르고 메모리 요구량이 작은 대신 삽입, 삭제가 번거롭다. 첨자 연산법이 단순해지기 위해서는 요소끼리 항상 인접해야 하고 그래서 삽입, 삭제시에 요소들을 밀고 당기고 해야 하는 것이다. 연결 리스트는 요소들이 메모리의 도처에 흩어져서 존재하지만 링크에 의해 논리적으로 연결되어 있어 링크를 따라가면 이전, 이후 요소들을 찾을 수 있다. 삽입, 삭제를 할 때도 물리적인 메모리 이동없이 요소간의 링크만 조작하면 되므로 속도가 빠르다. 다음 그림으로 배열과 연결 리스트가 메모리에 구현된 모양을 비교해 보자.

배열의 요소 하나는 자신이 기억할 데이터값만을 가지는데 비해 연결 리스트의 요소인 노드는 데이터외에 연결 상태에 대한 정보인 링크를 추가로 가져야 한다. 자기 다음의 요소가 누구인지를 스스로 기억하고 있어야 흩어져 있는 노드들의 순서를 알 수 있는데 이 연결 정보를 저장하는 것이 바로 링크이다. 링크를 하나만 가지는 것을 단순 연결 리스트(Single Linked List)라고 하고 두 개의 링크를 가지는 것을 이중 연결 리스트(Double Linked List)라고 한다. 노드를 구성하는 데이터와 링크는 타입이 다르기 때문에 노드는 이형 타입의 집합인 구조체로 정의된다.

struct Node

{

int value; // 데이터

Node *next; // 링크

};

value멤버는 노드가 기억하는 정보의 실체인 데이터이다. 배열 요소 타입에 제한이 없는 것처럼 연결 리스트가 저장하는 정보의 종류에도 제한이 없으므로 노드의 데이터는 임의 타입, 임의 개수로 정의할 수 있다. 여러 개의 변수들을 한꺼번에 가질 수도 있고 포인터나 배열 또는 다른 구조체를 노드에 포함시키는 것도 물론 가능하다. 예제에서는 편의상 정수값 하나만을 노드에 포함시켰다.

next 멤버는 다음 노드에 대한 포인터를 가지는 링크이다. Node 구조체안에 다른 Node 구조체의 번지 정보가 포함되어 있는데 자신에 대한 포인터를 멤버로 가지는 자기 참조 구조체이므로 크기가 무한대가 되지는 않는다(13-2-라 참조). 이 포인터가 가리키는 곳을 찾아가면 다음 노드가 저장된 곳을 알 수 있으며 또 다음 노드의 링크를 따라 가면 그 다음 노드를 연속적으로 찾을 수 있다. 노드들이 링크를 통해 서로의 위치를 기억함으로써 물리적으로 흩어져 있더라도 논리적으로는 한 덩어리의 정보가 될 수 있는 것이다.

단, 어떤 노드가 연결 리스트의 첫 번째 노드인지는 따로 저장해야 하는데 시작점을 기억하는 노드를 머리(head)라고 한다. 일단 머리 노드를 알아야 연속적으로 다음 노드를 찾을 수 있으므로 머리 노드는 언제든지 참조할 수 있는 전역변수로 선언하는 것이 보통이다. 머리는 연결 리스트의 진입점이며 항상 머리부터 검색을 시작하므로 연결 리스트의 대표 노드라고 할 수 있다. 이에 비해 동적 배열은 진입점을 가리키는 포인터로 대표된다. 다음 그림은 1, 2, 3 세 개의 노드를 가지는 연결 리스트가 메모리에 구현된 모양이다.

노드들이 메모리상의 임의 위치에 불규칙적으로 생성된다는 것을 강조하기 위해 노드의 위치도 불규칙적으로 그렸다. 하지만 노드의 물리적인 위치가 어디인가는 전혀 중요하지 않으며 실제 번지에 상관없이 링크에 의해 서로 논리적으로 연결되어 있으므로 일직선으로 그리는 것이 보통이다. 머리는 노드 1을 가리키고 노드1의 링크를 따라가면 노드 2가 있고 노드 2 다음에 노드 3이 있다. 노드 3의 링크는 NULL로 되어 있는데 다음 노드가 없다는 것은 곳 연결 리스트의 끝이라는 뜻이다.

단순 연결 리스트로 복수 개의 정수형 데이터를 저장하는 예제를 만들어보고 분석해 보자. 초기화, 삽입, 삭제, 순회 등의 기본적인 동작을 테스트하는데 간결성을 위해 메모리 할당 실패에 대한 에러 처리는 생략했다. 32비트 환경에서는 굳이 메모리 할당 성공 여부를 점검하지 않아도 된다. 짧은 예제이지만 연결 리스트의 구조와 관리 방법 등을 연구해 보기에는 충분할 것이다.

예 제 : SingleList

#include <Turboc.h>

// 노드 구조체

struct Node

{

int value;

Node *next;

};

Node *head;

// 연결 리스트 초기화 - 머리를 할당한다.

void InitList()

{

head=(Node *)malloc(sizeof(Node));

head->next=NULL;

}

// Target 다음에 노드를 삽입한다.

Node *InsertNode(Node *Target,Node *aNode)

{

Node *New;

New=(Node *)malloc(sizeof(Node));

*New=*aNode;

New->next=Target->next;

Target->next=New;

return New;

}

// Target 다음 노드를 삭제한다.

BOOL DeleteNode(Node *Target)

{

Node *Del;

Del=Target->next;

if (Del==NULL) {

return FALSE;

}

Target->next=Del->next;

free(Del);

return TRUE;

}

// 연결 리스트의 모든 노드와 머리를 해제한다.

void UnInitList()

{

while (DeleteNode(head)) {;}

free(head);

head=NULL;

}

void main()

{

int i;

Node *Now,Temp;

InitList();

// 다섯 개의 노드 삽입

Now=head;

for (i=1;i<=5;i++) {

Temp.value=i;

Now=InsertNode(Now,&Temp);

}

// 두 번째 노드 삭제

DeleteNode(head->next);

// 순회하면서 출력

for (Now=head->next;Now;Now=Now->next) {

printf("%d\t",Now->value);

}

printf("\n");

UnInitList();

}

Node 구조체 정의와 연결 리스트 관리 함수가 main 이전에 모두 작성되어 있다. main에서는 연결리스트를 초기화하고 1~5까지 다섯 개의 노드를 삽입한다. 그리고 두 번째 노드를 제거한 후 남은 노드들을 순회하면서 출력해 보았다. 결과는 1, 3, 4, 5가 되는데 예제의 각 부분을 순서대로 분석해 보자.

Node 구조체

Node 구조체는 연결 리스트의 한 요소인 노드를 정의한다. 이 예제의 연결 리스트는 정수를 데이터로 가지므로 정수형 변수 value와 링크 next만을 멤버로 가진다. 더 많은 정보를 저장하고 싶다면 필요한 멤버를 얼마든지 추가할 수 있는데 예를 들어 주소록이라면 name, tel, addr 등의 멤버가 포함될 것이고 파일에 대한 정보라면 path, date, size, attr 등이 포함될 것이다.

Node형 포인터 head는 전역으로 선언되어 있는데 이 변수가 연결 리스트의 진입점이다. 설사 연결 리스트가 비어 있더라도 머리는 반드시 있어야 하며 또한 적절하게 초기화되어야 한다. InitList 함수는 head에 Node 구조체를 할당하며 최초 머리 노드만 존재하므로 head의 링크는 NULL로 초기화된다.

head의 링크(head->next)가 NULL이라는 것은 머리 외에 실제 데이터를 가지는 노드는 없다는 뜻이며 이는 곧 연결 리스트가 비어 있다는 것을 표시한다. 머리 노드는 시작 노드의 번지만을 가지므로 데이터는 사용하지 않는다. main에서 연결 리스트를 사용하기 전에 InitList를 호출하여 초기화했으며 이 상태에서 잠시 후면 머리 뒤쪽에 노드들이 추가될 것이다.

노드의 삽입

노드는 자신과 연결된 노드의 정보를 가지고 있으므로 물리적인 메모리 이동없이 링크만 조작하여 리스트의 중간에 새로운 노드를 쉽게 삽입할 수 있다. 1, 2, 3 세 개의 노드가 있는 상태에서 노드 2다음에 노드 4가 삽입되는 가장 일반적인 경우(두 노드 사이에 새 노드가 끼어드는 경우)의 삽입 과정을 연구해 보자.

① Node 구조체를 새로 할당하여 New 노드를 만들고 이 노드의 value에 4를 대입한다. 노드 4는 메모리에 생성되어 있기만 할 뿐이지 아직 링크로 연결되지 않았으므로 연결 리스트에 포함된 것은 아니다. 노드 4의 링크인 next는 현재 쓰레기값을 가지고 있는 상태이다.

② 새로 만든 노드 4의 링크에 노드 3의 번지를 대입하여(New->next=Target->next) 노드 4가 노드 3앞에 위치하도록 연결한다. 이때 노드 3의 번지는 바로 앞에 있는 노드 2의 링크에서 구할 수 있는데 노드 2의 값을 바꾸기 전에 먼저 읽어야 한다. 순서가 바뀌면 안된다. 여기까지 처리하면 노드 4가 노드 3앞에 연결되었지만 아직 노드 2 다음에 연결되지는 않았다.

③ 노드 2의 링크에 노드 4를 대입(Target->next=New)하여 노드 4가 노드 2 다음에 위치하도록 연결한다. 이렇게 되면 노드 2와 노드 3의 연결은 끊어지며 노드 2→노드 4→노드 3 순으로 연결 상태가 재설정되어 노드 4가 중간에 삽입된다.

이 삽입 동작을 구현하는 함수가 바로 InsertNode 함수인데 두 개의 인수를 받아들인다. Target 인수는 삽입하고자 하는 노드의 이전 노드이며 Target 다음에 새 노드를 삽입한다. 단순 연결 리스트는 다음 링크밖에 없으며 이전 노드를 알 수 없기 때문에 특정 노드의 뒤쪽으로만 새 노드를 삽입할 수 있다. 특정 노드의 앞쪽에 삽입하려면 한 칸 더 앞에 있는 노드의 링크도 변경해야 하는데 이 노드를 구할 수 없는 것이다.

두 번째 인수 aNode는 삽입 대상이 되는 노드의 데이터를 가지는 임시 노드이다. main에서 Node 구조체를 만들고 이 구조체의 value에 원하는 값을 채워 보내며 InsertNode는 aNode 자체를 New에 대입한다. value만 전달할 수도 있지만 이렇게 하면 Node 구조체가 바뀔 때마다 InsertNode 함수를 수정해야 하는 번거로움이 있어 임시 노드를 전달하는 방법을 쓴다. 구조체 대입은 메모리 복사이므로 멤버가 늘어나도 수정할 필요가 없다.

InsertNode 함수는 물리적으로 새 노드를 생성하는 부분과 논리적으로 링크를 연결하는 두 부분으로 구성되어 있다. 메모리상에 새로운 링크를 만들고 새로 만들어진 노드와 삽입될 위치의 앞, 뒤 노드의 링크를 조작한다. 그리고 새로 만들어진 노드의 포인터를 리턴함으로써 이 노드 다음에 연속적으로 다른 노드를 삽입할 수 있도록 한다.

Node *InsertNode(Node *Target,Node *aNode)

{

Node *New;

New=(Node *)malloc(sizeof(Node)); // 노드 생성. 그림의 ①번 과정에 해당

*New=*aNode;

New->next=Target->next; // 뒤쪽 노드와 연결. 그림의 ②번 과정에 해당

Target->next=New; // 앞쪽 노드와 연결. 그림의 ③번 과정에 해당

return New;

}

main 함수에서 루프를 돌며 InsertNode를 다섯 번 호출하는데 최초 head에서부터 삽입을 시작한다. 이 과정을 따라가 보자.

최초 머리만 있는 상태에서 머리 다음에 노드1을 삽입했는데 이 경우는 중간에 끼어드는 것이 아니라 끝에 추가된다고 볼 수 있다. 추가되는 경우도 InsertNode 함수의 코드가 그대로 적용되는데 머리의 링크는 새로 만든 노드를 가리키고 head 링크에 저장되어 있던 NULL은 새로 만든 노드가 가져감으로써 이 노드가 머리 대신 끝 노드가 된다. 리스트의 끝에 추가되는 과정도 중간에 삽입되는 일반적인 경우와 같은 방법으로 처리하면 된다.

InsertNode는 새로 추가된 노드의 포인터를 리턴하는데 이 포인터를 받아 InsertNode의 인수로 다시 전달하면 새 노드 뒤쪽에 노드들을 연속적으로 추가할 수 있다. main에서는 InsertNode가 리턴하는 포인터를 Now로 대입 받아 Now뒤쪽에 계속 2, 3, 4, 5를 추가했다. 그래서 여기까지 실행하면 head이하 다섯 개의 노드가 링크로 죽 연결된 상태가 만들어진다. 노드는 실행중에 메모리를 동적으로 할당하여 생성되므로 메모리 한계까지 얼마든지 추가할 수 있다.

노드의 삭제

노드를 삭제하는 방법도 역시 링크를 조작하는 것이다. DeleteNode 함수는 인수로 주어진 Target 노드 다음의 노드를 삭제한다. 단순 연결 리스트는 앞쪽 노드를 찾지 못하므로 노드 자체를 삭제할 수는 없고 지정한 노드의 뒤쪽만 삭제할 수 있다. 그래서 삭제하고자 하는 노드의 앞 노드를 인수로 전달해야 한다.1, 2, 3 세 개의 노드가 있는 상태에서 노드 2를 삭제하는 예를 보자.

노드 2를 제거하려면 DeleteNode 함수로 노드 1을 전달해야 하는데 노드1은 head->next로 쉽게 구할 수 있다. DeleteNode 함수는 Target->next로 삭제 대상 노드를 찾아 Del에 대입한다. 그리고 Del이 가리키고 있는 다음 노드를 Target의 다음 노드로 설정(Target->next=Del->next)함으로써 Del을 리스트에서 제외시킨다. 이렇게 되면 Del은 메모리에 아직 남아 있지만 연결 리스트에서는 논리적으로 삭제된 것이다. Del이 차지하고 있는 메모리를 free 함수로 해제하면 이 노드는 물리적으로 제거된다.

DeleteNode 함수는 한가지 예외를 처리하고 있는데 Target으로 마지막 노드가 전달된 경우 삭제할 대상이 없으므로 에러를 리턴한다. 마지막 노드의 링크는 NULL을 가리키고 있으며 이 값은 리스트의 끝이라는 표식일 뿐 실제 노드가 아니므로 삭제할 수 없다. main에서 노드2를 삭제했으며 이 결과 1, 3, 4, 5만 리스트에 남게 된다.

순회

순회란 연결 리스트에 포함된 모든 노드를 한 번씩 읽어 보는 것이다. 순회중에 여러 가지 작업을 할 수 있으며 일단 순회를 해야 어떤 처리라도 할 수 있다. 특정값을 가진 노드를 검색한다거나 노드 전체를 출력할 때는 머리에서부터 링크를 따라 모든 노드를 방문해 봐야 한다. 배열의 경우는 for 루프를 돌며 첨자를 증가시키는 방법으로 간단히 순회할 수 있지만 연결 리스트는 연속된 메모리 공간에 노드들이 배치되어 있지 않으므로 링크를 따라 가면서 노드를 반복적으로 읽어보는 방법밖에 없다. 노드의 총 개수를 알고 싶을 때도 순회가 필요하다.

main에서는 head->next, 즉 첫 번째 노드에서부터 시작해서 value를 출력하고 링크를 따라 다음 노드로 이동하기를 노드가 NULL이 아닐 때까지 반복함으로써 순회한다. 동작이 복잡해 보이지만 Node 형의 포인터 변수와 단순한 for문 하나면 전체 순회가 가능하다. 노드들은 연속적인 메모리 공간에 있지도 않고 생성되는 위치를 예측할 수도 없지만 머리에서부터 next링크만 따라 다니면 순서에 맞게 모든 노드를 순회할 수 있다. 노드 2가 삭제되었으므로 출력되는 결과는 1, 3, 4, 5가 될 것이다.

단순 연결 리스트는 뒤쪽 링크만을 가지기 때문에 순방향으로만 순회할 수 있다. 역방향 참조가 필요하다면 다음 항에서 연구해 볼 이중 연결 리스트를 사용해야 한다.

해제

연결 리스트의 노드들은 실행중에 메모리를 할당해서 생성되므로 다 사용했으면 해제해야 한다. 이 작업은 UnInitList 함수에서 담당하는데 방법은 생각보다 간단하다. head의 다음 노드인 첫 번째 노드를 삭제하기를 실패할 때까지, 즉 머리가 리스트의 끝이 될 때까지 반복하는 것이다. 마치 키보드의 Del키로 문자를 지우듯이 뒤쪽 노드들이 머리쪽으로 이동하면서 순서대로 사라진다. 머리 자체는 DeleteNode 함수로 삭제할 수 없으므로 별도로 해제해야 한다.

FindPrevNode

단순 연결 리스트는 링크가 하나 뿐이며 특정 노드의 앞쪽 노드를 알 수 있는 편리한 방법이 없다. 그래서 삽입할 때나 삭제할 때도 항상 대상 노드의 이전 노드를 지정해야 한다. 그러나 꼭 이전 노드를 알고 싶다면 조금 비효율적이기는 하지만 전혀 불가능한 것은 아니다. 머리에서부터 순회를 시작하여 자기 자신을 만날 때까지 링크를 따라 다니다가 바로 직전의 노드를 취하면 된다. 이 방법을 연구해 보고 이전 노드를 찾는 FindPrevNode 함수를 작성해 보아라. 또 이 함수를 응용하여 지정한 노드의 앞에 새 노드를 삽입하는 InsertNodeLeft 함수와 지정한 노드를 삭제하는 DeleteNodeSelf 함수를 작성해 보아라.