[C언어] 자기참조 구조체에 의한 연결 리스트 (Linked List) 구현

In computer science, a linked list is a data structure that consists of a sequence of data records such that in each record there is a field that contains a reference (i.e., a link) to the next record in the sequence.

Each record of a linked list is often called an element or node.

The field of each node that contains the address of the next node is usually called the next link or next pointer. The remaining fields are known as the data, information, value, or payload fields.

-----------------------------------------------------------------------------------------------------


자료구조 "Linked List" 를 C로 구현하는 방법에 대해 알아보자.

링크트 리스트를 구현하기 위해서는,
데이터들이 자신과 같은 타입의 데이터를 포인팅하는 정보를 포함해야한다.

즉, 데이터 타입 내부에 자신과 같은 타입에 대한 포인터를 가지고 잇어야 한다는 말이 된다.

연결 리스트는 다음과 같은 방식으로 만들수 있다.

struct list { int data; struct list *p; };

이제 이러한 형의 데이타를 선언해주면 이러한 타입의 변수들을 만들수 있고, 그것들을 서로 연결시키면 된다.
sturct list a,b,c;

a를 b로 연결시키고, b를 c로 연결시키고, c는 매듭을 지어보자. 마지막노드로 매듭을 지을때는 포인터를 널포인터로 만들면 된다.

a.p = &b;
b.p = &c;
c.p = NULL;


연결 리스트의 특징은, 데이터들이 줄줄이 사탕으로 엮여있기 때문에, 줄줄이 사탕중 어느 하나를 잡으면, 그 것으로 부터 이어진 데이터에 접근이 가능하다는 것이다.

즉, 위의 예에서, 노드 b 에 접근을 했다면, 거기서 c로 접근을 할 수 있다.
b에서 c의 데이터에 접근하는 방법은 아래와 같다.

b.p -> data

만약 a에서 c의 데이터에 접근하고 싶다면 다음과 같이 된다.

a.p -> p -> data

이렇게 하면, a에서 b의 포인터로 접근하고 b의 포인터가 가리키는 노드로 간후에 거기서 데이타에 접근한다.

이러한 연결 리스트를 이용하여, 순차적으로 접근 가능한 데이터를 다룰 수 있다.
그리고, 연결리스트를 통해서도 스택이나 큐를 구현할 수 있는데, 이에 대해서는 나중에 살펴본다.

각종 리스트 구조 (linear linked list, circular linked list, multiple-linked list 등등) 와, 각종 리스트 연산에 관해서는 나중에 따로 다루기로 한다.