이번엔 포인터로 구현한 연결 리스트를 알아볼 차례이다
연결 리스트는 여기 저기 흩어져 있는 데이터들을 포인터로 연결하여 하나의 자료형으로 묶는다
데이터의 삽입, 삭제 시 데이터 자체를 이동시키지 않고 포인터가 가리키는 대상만 바꿔주면 되며, 데이터 삽입이 추가로 필요할 때마다 동적할당을 이용해 유동적으로 크기를 줄이거나 늘릴 수 있기 때문에 순차 리스트의 단점을 보완할 수 있다
연결 리스트는 '노드'라고 하는 데이터의 집합인데, 노드는 데이터 필드와 링크 필드로 구성되어 있다
데이터 필드에는 저장할 데이터가 링크 필드에는 다음 노드의 주소가 저장된다
또 연결 리스트를 구분하는 첫 번재 노드는 헤드 포인터로 선언되며, 마지막 노드의 링크 필드는 NULL 값을 가진다
여기서 선언된 헤드 포인터로 연결 리스트들을 구분할 수 있는데, 모든 데이터는 이 헤드 포인터를 통해 앞에서 부터 순차적으로 접근 가능하다
이러한 연결 리스트에는 단순 연결 리스트 (Singly Linked List), 마지막 노드의 링크가 첫 번째 노드를 가리키는 원형 단순 연결 리스트 (Circular Singly Linked List), 이전과 이후 링크 필드가 2개 존재하여 앞 뒤로 참조가 가능한 이중 연결 리스트 (Doubly Linked List)가 존재하며, 이중 연결 리스트를 순환 시키는 순환 이중 연결 리스트 (Circular Doubly Linked List)도 존재하는데, 여기서 더 발전하여 헤드 포인터가 빠지고 헤드 노드로 시작하는 순환 이중 연결 리스트도 존재한다
이 장에서는 여러 연결 리스트 중 단순 연결 리스트와 순환 단순 연결 리스트를 알아볼 것이다
Singly Linked List (단순 연결 리스트)
먼저 단순 연결 리스트의 노드를 정의하면 다음과 같다
typedef int Data; // 노드 안에 저장할 Data 정의
typedef struct // 노드 내부 정의
{
Data data;
struct Node *Next;
} Node;데이터 필드에는 Data 타입의 데이터를 저장하고 링크 필드에는 다음 Node를 가리키는 포인터를 저장한다
이렇게 정의한 노드를 헤드 포인터로 생성해서 공백 리스트를 만드는데
Node *head = NULL;처음 노드를 생성할 때는 저장할 노드가 없으므로 NULL값을 주면 된다
또한 헤드 포인터가 NULL이면 공백이라는 의미이다
공백 리스트에 노드를 생성할 때에는 malloc()을 이용해 동적으로 생성하는데, 생성하는 방법은 다음과 같다
head = (Node *)malloc(sizeof(Node));
head -> data = 10;
head -> Next = NULL;이렇게 되면 아래와 같이 노드가 생성된다
노드를 생성 했는데, 새로운 노드는 어떻게 삽입할까?
단순 연결 리스트의 삽입은 맨 앞에 삽입하는 경우와 중간이나 끝에 삽입하는 경우 이렇게 2가지로 나뉘는데, 먼저 맨 앞에 삽입하는 경우를 알아보자
Node* insert_first(Node *head, Data value)
{
Node *p = (Node*)malloc(sizeof(Node)); // p라는 새로운 노드 생성
p -> data = value;
p -> Next = head; // ①
head = p; // ②
return head;
}p라는 새로운 노드를 생성하여 p의 다음을 헤드가 가리키는 노드를 가리키게 만들고, 헤드가 새로 만든 p를 가리키게 하면 새로운 노드를 맨 앞에 삽입할 수 있다
그림으로 표현하면 아래와 같은 순서로 새로운 노드가 삽입된다
다음으로 중간이나 마지막에 삽입하는 방법을 알아보자
// 노드 q 뒤에 새로운 노드 p 삽입
Node* insert(Node *head, Node *q, Data value)
{
Node *p = (Node *)malloc(sizeof(Node));
p -> data = value;
p -> Next = q -> Next; // ①
// p를 마지막에 삽입한다면 p -> Next = NULL;
q -> Next = p; // ②
return head;
}p에 데이터를 담고, p의 다음을 q의 다음을 가리키게 한다음 p의 다음을 q에 연결하면 중간이나 마지막에 삽입할 수 있다
그림으로 표현하면 다음과 같다
삽입에 대하여 알아봤으니 삭제를 알아볼 차례이다
삭제 역시 첫 번째 노드를 삭제할 때, 중간이나 마지막 노드를 삭제할 때로 나뉘지만 코드 하나로 표현할 수도 있다
// q 다음 원소 p를 삭제
Node* delete(Node *head, Node *q)
{
Node *p = q -> Next;
if (q == head) head = p -> Next; // ①
else q -> Next = p -> Next; // ②
free(p);
return head;
}p에 삭제할 노드를 담고, q가 헤드인지 아닌지에 따라 다르게 연산하면 노드를 삭제할 수 있다
그림으로 표현하면 다음과 같다
마지막으로 검색 기능을 알아보자
단순 연결 리스트에서 데이터를 검색하기 위해서는 헤드 포인터부터 차례대로 검색해야 한다
// key 검색
Data search(Node *head, Data key)
{
Node *p = head;
while (p != NULL)
{
if (p -> data == key) return p -> data;
p = p -> Next;
}
return NULL; // 리스트에 찾는 값이 없을 때
}p에 head를 담고, p의 데이터와 key 값을 비교하여 찾는 값이면 해당 값을 return하는데, 만약 찾는 값이 아니라면 p에 p의 다음 노드를 넣는다
이렇게 리스트의 끝까지 데이터를 검색했는데 key값이 리스트 안에 없다면 NULL을 return 한다
Circular Singly Linked List (순환 단순 연결 리스트)
순환 단순 연결 리스트는 리스트의 마지막 값의 링크 필드를 첫 번째 노드를 가리키게 만들어 하나의 노드에서 다른 모든 노드에 접근이 가능하다
이런 특징 때문에 삽입, 삭제가 그냥 단순 연결 리스트보다 용이힌데, 특히 리스트의 끝에 노드를 삽입하는 연산이 더 효율적이다 (사실상 리스트의 시작과 끝이 의미 없어지긴 했지만)
그림으로 표현하면 다음과 같은데
리스트가 순환하더라도 헤드 포인터는 반드시 존재해야 하며, 마지막 노드 다음에 새로운 노드를 추가하려면 헤드 포인터가 마지막 노드를 가리키게 한다음 삽입을 진행하면 된다
마지막으로 연결 리스트의 장단점을 알아보면
장점
① 메모리 활용이 효율적
② 데이터 추가, 삭제가 용이
단점
① n번째 데이터에 접근하기 위해, n번의 탐색이 필요
② 데이터 탐색이 단방향