이번 포스팅은 "단순 연결 리스트"를 이해했다는 전제 하에 내용을 진행합니다. 단순 연결 리스트에 대해 잘 알지 못한다면 이전 포스팅을 참고해주시고 그 후 이 포스팅을 읽어주세요 (단순 연결 리스트 공부하기)
원형 연결 리스트의 정의
원형 연결 리스트는 단순 연결 리스트와 달리 "마지막 노드가 첫 번째 노드를 가리키는 리스트"입니다. 즉, 마지막 노드가 NULL 값을 가지는 것이 아니라 첫 번째 노드 주소값을 가지는 것입니다.
원형 연결 리스트는 하나의 노드에서 모든 노드로의 접근이 가능하다는 장점을 가지고 있습니다. 링크를 따라가다가 보면 모든 노드에 접근한 후, 다시 처음으로 돌아오게 되는 것입니다. 이렇게 되면 노드의 삽입과 삭제 연산이 기존 단순 연결 리스트보다 더욱 단순해지게 됩니다. (삽입과 삭제 연산 자체는 단순 연결 리스트와 거의 같으나, 연결 리스트의 처음과 끝에 삽입하는 것이 쉬워집니다)
원형 연결 리스트 구현
C언어로 원형 연결 리스트를 구현해보도록 하겠습니다. 원형 연결 리스트를 구현할 때 주의할 것은 마지막 노드의 링크가 NULL이 아니기 때문에 리스트의 끝에 도달했는지를 헤드 포인터와 비교해야 한다는 것입니다. 또한 리스트를 출력할 때 while문이 아니라 do-while문을 사용해야 합니다.
#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct ListNode { // 노드 타입
element data;
struct ListNode *link;
} ListNode;
// 리스트의 항목 출력
void print_list(ListNode *head) {
ListNode* p ;
if (head == NULL) return;
p = head->link;
do {
printf("%d->", p->data);
p = p->link;
} while (p != head);
printf("%d->", p->data); // 마지막 노드 출력
}
// 리스트 처음 삽입 함수
ListNode* insert_first(ListNode* head, element data) {
ListNode *node = (ListNode *)malloc(sizeof(ListNode));
node->data = data;
if (head == NULL) {
head = node;
node->link = head;
}
else {
node->link = head->link;
head->link = node;
}
return head; // 변경된 헤드 포인터 반환
}
// 리스트 끝 삽입 함수
ListNode* insert_last(ListNode* head, element data) {
ListNode *node = (ListNode *)malloc(sizeof(ListNode));
node->data = data;
if (head == NULL) {
head = node;
node->link = head;
}
else {
node->link = head->link;
head->link = node;
head = node;
}
return head; // 변경된 헤드 포인터를 반환
}
// 원형 연결 리스트 테스트 프로그램
int main() {
ListNode *head = NULL;
// list = 10->20->30->40
head = insert_last(head, 20); // insert_last()가 반환한 헤드 포인터를 head에 대입한다.
head = insert_last(head, 30);
head = insert_last(head, 40);
head = insert_first(head, 10);
print_list(head);
return 0;
}이중 연결 리스트의 정의
단순 연결 리스트는 특정 노드에서 후속 노드에 접근하기는 쉽지만, 선행 노드에 접근하기는 쉽지 않습니다. 원형 연결 리스트라도 특정 노드에서 후속 노드를 접근하기는 쉽지만, 선행 노드에 접근하기 위해서는 거의 전체 노드를 거쳐서 돌아와야 합니다. 그렇기에 어떤 프로그램에서 노드를 양방향으로 접근해야 한다면 단순 연결 리스트나 원형 연결 리스트는 적합하지 않습니다. 이러한 문제를 해결하고자 이중 연결 리스트가 만들어졌습니다.
이중 연결 리스트는 하나의 노드가 선행 노드와 후속 노드에 대한 두개의 링크를 가지는 리스트입니다. 링크가 양방향이기에 접근도 양방향으로 가능합니다. 단점으로는 공간을 많이 차지하며 코드가 복잡해진다는 것입니다.
이중 연결 리스트에서 더욱 응용을 하여 이중 연결 리스트와 원형 연결 리스트를 혼합한 형태로도 많이 사용되기도 합니다. 결국 그만큼 이중 연결 리스트는 활용도가 높다는 것을 알 수 있습니다.
이중 연결 리스트의 삽입과 삭제
이중 연결 리스트 또한 삽입과 삭제 연산은 단순 연결 리스트와 아주 유사합니다. 그러나 양방향으로 링크가 존재하다보니 단순 연결 리스트보다는 약간 신경 쓸 것이 더 있습니다.
삽입 연산 (Insert)
이중 연결 리스트의 삽입 연산은 다음 순서대로 링크 필드의 값을 바꾸면 됩니다.
삭제 연산 (Delete)
이중 연결 리스트의 삭제 연산은 다음 순서대로 링크 필드의 값을 바꾸면 됩니다.
이중 연결 리스트 구현
C언어로 구현한 이중 연결 리스트는 다음과 같습니다.
#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct DListNode { // 이중연결 노드 타입
element data;
struct DListNode* llink;
struct DListNode* rlink;
} DListNode;
// 이중 연결 리스트를 초기화
void init(DListNode* phead) {
phead->llink = phead;
phead->rlink = phead;
}
// 이중 연결 리스트의 노드를 출력
void print_dlist(DListNode* phead) {
DListNode* p;
for (p = phead->rlink; p != phead; p = p->rlink) {
printf("<-| |%d| |-> ", p->data);
}
printf("\n");
}
// 새로운 데이터를 노드 before의 오른쪽에 삽입한다
void dinsert(DListNode *before, element data) {
DListNode *newnode = (DListNode *)malloc(sizeof(DListNode));
newnode->data = data;
newnode->llink = before;
newnode->rlink = before->rlink;
before->rlink->llink = newnode;
before->rlink = newnode;
}
// 노드 removed를 삭제한다
void ddelete(DListNode* head, DListNode* removed) {
if (removed == head) return;
removed->llink->rlink = removed->rlink;
removed->rlink->llink = removed->llink;
free(removed);
}
// 이중 연결 리스트 테스트 프로그램
int main() {
DListNode* head = (DListNode *)malloc(sizeof(DListNode));
init(head);
printf("추가 단계\n");
for (int i = 0; i < 5; i++) {
// 헤드 노드의 오른쪽에 삽입
dinsert(head, i);
print_dlist(head);
}
printf("삭제 단계\n");
for (int i = 0; i < 5; i++) {
print_dlist(head);
ddelete(head, head->rlink);
}
free(head);
return 0;
}