저번 게시물에 이어서 이중 연결 리스트 (Doubly Linked List)에 대해 함께 알아보겠습니다.
이중 연결리스트
이중 연결 리스트의 가장 큰 특징은 한 노드에서 양방향으로 이전 노드 또는 다음 노드에 접근할 수 있다는 것입니다.
가장 큰 예를 들면 마지막 노드에 접근하기 위해 head부터 next를 따라 tail까지 접근했던 것에 반해,
이중 연결 리스트는 그냥 head의 왼쪽 노드로 접근해주면 됩니다.
단점은 다른 노드로 접근하는 링커가 하나 더 존재함에 따라 메모리가 커지고, 구현의 복잡도가 증가합니다.
1) 이중 연결리스트 ADT
ADT
Init_List(void): 연결 리스트를 초기화합니다.
Add_First(ListMark *ls, int data): 연결 리스트의 가장 앞쪽에 노드를 추가합니다.
Add_Last(ListMark *ls, int data): 연결 리스트의 가장 뒷쪽에 노드를 추가합니다.
Add_Pos(ListMark *ls, int pos, int data): 연결리스트의 원하는 위치에 노드를 추가합니다.
Delete_First(ListMark *ls): 연결리스트의 가장 앞 노드를 삭제합니다.
Delete_Last(ListMark *ls): 연결리스트의 가장 뒷 노드를 삭제합니다.
Delete_Pos(ListMark *ls, int pos, int data): 연결리스트의 원하는 위치에 노드를 추가합니다.
Return_Size(ListMark *ls): 연결 리스트에 저장된 노드의 갯수를 반환합니다.
Reset_List(ListMark *ls): 연결리스트에 저장된 모든 노드의 메모리를 해제하고, 초기화합니다.
Print_List(ListMark *ls): 연결 리스트에 저장된 모든 데이터를 출력합니다.
이중 연결 리스트를 구성하는 함수는 위와 같습니다.
본인이 구현하는 프로그램의 목적과 특성에 맞게 추가, 변경, 삭제할 수 있습니다.
2) 이중 연결 리스트 구현
이중 연결 리스트는 앞서 공부한 원형 연결리스트의 모든 노드가 자기 뒷 노드 뿐만 아니라 앞 노드도 가리킬 수 있다는 것이 특징입니다.
따라서, 각 노드 당 앞, 뒷 노드를 가리키는 링커가 2개 존재합니다.
2-1) 이중 연결리스트 구조체 선언
typedef struct NODE {
struct NODE *lnext;
struct NODE *rnext;
int data;
} Node;
typedef struct LISTMARK {
Node *head;
Node *tail;
int size;
} ListMark;
NODE 구조체에서 보이는 것과 같이 각 노드 당 앞 노드를 가리키는 *lnext와 뒷 노드를 가리키는 *rnext 두 개의 링커를 가집니다.
2-2) 이중 연결 리스트 초기화
ListMark *Init_List(void){
ListMark *ls = (ListMark *)malloc(sizeof(ListMark));
ls->head = NULL;
ls->tail = NULL;
ls->size = 0;
return ls;
}
이중 연결 리스트의 처음과 끝 노드를 가리키는 구조체 멤버 변수를 초기화해줍니다.
ls->size는 노드의 추가, 삭제 시 크기가 변화하며 연결 리스트 내의 노드 갯수를 저장합니다.
해당 함수는 아래와 같이 사용할 수 있습니다.
2-3) 이중 연결리스트 노드 추가
void Add_First(ListMark *ls, int data){ // 연결 리스트의 가장 앞 쪽에 노드를 추가합니다.
Node *tmp = (Node *)malloc(sizeof(Node)); // 추가될 노드이므로 메모리를 할당해줍니다.
tmp->data = data;
if(ls->head == NULL){ // head와 tail이 NULL로 초기화됐으므로, NULL일 때 저장된 노드는 없습니다.
ls->head = ls->tail = tmp; // 첫 노드는 head와 tail이 함께 가리킵니다.
ls->head->lnext = tmp; // 어차피 ls->head와 ls->tail이 같은 주소를 가지기 때문에, 모든 노드의 링커가 다시 스스로를 가리킵니다.
ls->head->rnext = tmp;
}
else{
tmp->lnext = ls->head->lnext; // tmp가 새로운 head가 돼야 하므로, tmp의 lnext가 head의 이전 노드 (ls->tail)를 가리킵니다.
tmp->rnext = ls->head; // tmp의 rnext는 head를 가리킵니다.
ls->head->lnext = tmp; // head의 lnext는 tail에서 새로운 head인 tmp로 갱신됩니다.
ls->tail->rnext = tmp; // tail의 rnext는 새로운 head인 tmp를 가리킵니다.
ls->head = tmp; // tmp를 새로운 head로 갱신합니다.
}
ls->size++;
}
void Add_Last(ListMark *ls, int data){ // 연결 리스트의 가장 마지막에 노드를 추가합니다.
Node *tmp = (Node *)malloc(sizeof(Node)); // Add_First와 동일한 논리를 가집니다.
tmp->data = data;
if(ls->tail == NULL){
ls->head = ls->tail = tmp;
ls->tail->lnext = tmp;
ls->tail->rnext = tmp;
}
else{
tmp->lnext = ls->tail;
tmp->rnext = ls->tail->rnext;
ls->tail->rnext = tmp;
ls->head->lnext = tmp;
ls->tail = tmp;
}
ls->size++;
}
void Add_Pos(ListMark *ls, int pos, int data){ // 연결 리스트의 원하는 위치에 노드를 추가합니다.
Node *tmp = (Node *)malloc(sizeof(Node));
Node *cur;
last_pos = ls->size; // last_pos는 연결 리스트의 마지막 노드 위치 순서를 가리킵니다.
tmp->data = data;
if(pos <= ls->size){ // 원하는 위치가 연결리스트 내에 있는지 확인합니다.
if(pos == 1){
puts("Add_Pos -> Add_First.");
Add_First(ls, data); // 첫 번째 위치라면 Add_First를 수행합니다.
}
else if(pos == last_pos){
puts("Add_Pos -> Add_Last.");
Add_Last(ls, data); // 마지막 위치라면 Add_Last를 수행합니다.
}
else{
int n = pos - 1;
cur = ls->head;
while(--n){ // 내가 넣고 싶은 자리 바로 앞으로 cur이 설정된다.
cur = cur->rnext;
}
// 넣고자 하는 자리 바로 앞 노드와 cur이 같습니다.
tmp->lnext = cur; // cur 다음에 tmp가 들어가야 하기 때문에, tmp->lnext(이전 노드)는 cur을 가리킵니다.
tmp->rnext = cur->rnext; // tmp는 cur->rnext가 가리키는 노드를 가리킵니다.
cur->rnext = tmp; // cur->rnext는 새롭게 자신의 다음에 위치할 노드인 tmp를 가리킵니다.
tmp->rnext->lnext = tmp; // tmp의 다음 노드의 lnext는 tmp를 가리킵니다.
++ls->size;
}
}
else{
puts("You entered wrong position.");
}
}
2-4) 이중 연결 리스트 노드 삭제
void Delete_First(ListMark *ls){ // 연결 리스트에 저장된 첫 번째 노드를 삭제합니다.
Node *cur;
Node *tmp;
tmp = ls->head;
if(tmp == NULL){
puts("List is empty.");
}
else{
cur = ls->head->rnext; // 이전 head가 삭제되고 다음 노드(==ls->head->rnext)가 새로운 head (==cur)가 됩니다.
cur->lnext = ls->head->lnext; // 새로운 head인 cur은 이전 head의 링커가 가리키는 노드를 가리킵니다.
ls->tail->rnext = cur; // tail의 rnext는 새로운 head인 tmp를 가리킵니다.
ls->head = cur; // cur이 새로운 head로 지정됩니다.
free(tmp); // tmp에 저장된 이전 head의 메모리를 해제합니다.
ls->size--;
}
}
void Delete_Last(ListMark *ls){ // 연결 리스트에 저장된 마지막 노드를 삭제합니다.
Node *cur; // Delete_First와 동일한 논리를 가집니다.
Node *tmp;
tmp = ls->tail;
if(tmp == NULL){
puts("List is empty.");
}
else{
cur = ls->tail->lnext;
cur->rnext = ls->head;
ls->head->lnext = cur;
ls->tail = cur;
free(tmp);
ls->size--;
}
}
void Delete_Pos(ListMark *ls, int pos, int data){ // 연결 리스트의 원하는 위치에 노드를 삽입합니다.
Node *cur;
Node *tmp;
int last_pos = ls->size;
if(pos <= ls->size){
if(ls->head == NULL){
puts("List is empty.");
}
else if(pos == 1){
Delete_First(ls);
}
else if(pos == last_pos){
Delete_Last(ls);
}
else{
int n = pos;
cur = ls->head;
while(--n){ // 내가 지우고 싶은 자리로 cur이 설정된다.
cur = cur->rnext;
}
// cur은 지우고자 하는 노드로 설정됩니다.
tmp = cur;
cur->lnext->rnext = cur->rnext; // cur의 이전 노드가 cur 다음 노드를 가리키도록 합니다.
cur->rnext->lnext = cur->lnext; // cur의 다음 노드가 cur 이전 노드를 가리키도록 합니다.
free(tmp); // tmp == cur 이므로, 지우고자 하는 노드의 메모리를 해제합니다.
ls->size--;
}
}
else{
puts("You entered wrong position.");
}
}
2-5) 이중 연결 리스트 출력, 노드 개수 반환
void Print_List(ListMark *ls){ // 연결 리스트에 저장된 모든 데이터를 출력합니다.
Node *cur;
cur = ls->head;
if(cur == NULL){
puts("List is empty.\n");
}
else{
int n = 1;
while(n <= ls->size){ // ls->size는 연결 리스트에 저장된 모든 노드의 개수와 동일합니다.
printf("List[%d] = %d.\n", n, cur->data);
cur = cur->rnext; // cur이 출력되고, cur은 자신의 다음 노드로 갱신됩니다.
n++;
}
}
printf("\n");
}
void Return_Size(ListMark *ls){ // 연결 리스트에 저장된 노드의 개수를 출력합니다.
printf("\nCurrent list size is %d.\n", ls->size);
// ls->size는 연결 리스트에 저장된 모든 노드의 갯수와 동일합니다.
}
2-6) 이중 연결리스트 노드 전체 삭제 및 초기화
void Reset_List(ListMark *ls){
Node *tmp;
Node *cur;
cur = ls->head;
while(cur != ls->tail){ // cur이 head부터 tail 이전까지 이동하며 메모리를 해제합니다.
tmp = cur->rnext; // ls->size를 사용하면 while 문 종료와 함께 메모리 해제를 완료할 수 있습니다. (tail이 남지 않아요.)
free(cur);
cur = tmp;
printf("Previous list size was %d, and now list size is %d.\n", ls->size, --ls->size);
}
free(cur); // cur == ls->size 이므로, 마지막 노드인 tail의 메모리를 해제합니다.
printf("Previous list size is %d, and now list size is %d.\n", ls->size, --ls->size);
ls->head = NULL; // Init_List와 동일한 역할을 합니다. (초기화)
ls->tail = NULL;
ls->size = 0;
}
#include <stdio.h>
#include <stdlib.h>
int last_pos;
typedef struct NODE{
struct NODE *lnext;
struct NODE *rnext;
int data;
} Node;
typedef struct LISTMARK{
Node *head;
Node *tail;
int size;
} ListMark;
ListMark *Init_List(void){
ListMark *ls = (ListMark *)malloc(sizeof(ListMark));
ls->head = NULL;
ls->tail = NULL;
ls->size = 0;
return ls;
}
void Add_First(ListMark *ls, int data){
Node *tmp = (Node *)malloc(sizeof(Node));
tmp->data = data;
if(ls->head == NULL){ // 여기 한번 더 확인
ls->head = ls->tail = tmp;
ls->head->lnext = tmp;
ls->head->rnext = tmp;
}
else{
tmp->lnext = ls->head->lnext;
tmp->rnext = ls->head;
ls->head->lnext = tmp;
ls->tail->rnext = tmp; // 이쪽을 이어주는 것
ls->head = tmp;
}
ls->size++;
}
void Add_Last(ListMark *ls, int data){
Node *tmp = (Node *)malloc(sizeof(Node));
tmp->data = data;
if(ls->tail == NULL){
ls->head = ls->tail = tmp;
ls->tail->lnext = tmp;
ls->tail->rnext = tmp;
}
else{
tmp->lnext = ls->tail;
tmp->rnext = ls->tail->rnext;
ls->tail->rnext = tmp;
ls->head->lnext = tmp;
ls->tail = tmp;
}
ls->size++;
}
void Add_Pos(ListMark *ls, int pos, int data){
Node *tmp = (Node *)malloc(sizeof(Node));
Node *cur;
last_pos = ls->size;
tmp->data = data;
if(pos <= ls->size){
if(pos == 1){
puts("Add_Pos -> Add_First.");
Add_First(ls, data);
}
else if(pos == last_pos){
puts("Add_Pos -> Add_Last.");
Add_Last(ls, data);
}
else{
int n = pos - 1;
cur = ls->head;
while(--n){ // 내가 넣고 싶은 자리 바로 앞으로 cur이 설정된다.
cur = cur->rnext;
}
tmp->lnext = cur;
tmp->rnext = cur->rnext;
cur->rnext = tmp;
tmp->rnext->lnext = tmp;
++ls->size;
}
}
else{
puts("You entered wrong position.");
}
}
void Delete_First(ListMark *ls){
Node *cur;
Node *tmp;
tmp = ls->head;
if(tmp == NULL){
puts("List is empty.");
}
else{
cur = ls->head->rnext;
cur->lnext = ls->head->lnext;
ls->tail->rnext = cur;
ls->head = cur;
free(tmp);
ls->size--;
}
}
void Delete_Last(ListMark *ls){
Node *cur;
Node *tmp;
tmp = ls->tail;
if(tmp == NULL){
puts("List is empty.");
}
else{
cur = ls->tail->lnext;
cur->rnext = ls->head;
ls->head->lnext = cur;
ls->tail = cur;
free(tmp);
ls->size--;
}
}
void Delete_Pos(ListMark *ls, int pos, int data){
Node *cur;
Node *tmp;
int last_pos = ls->size;
if(pos <= ls->size){
if(ls->head == NULL){
puts("List is empty.");
}
else if(pos == 1){
Delete_First(ls);
}
else if(pos == last_pos){
Delete_Last(ls);
}
else{
int n = pos;
cur = ls->head;
while(--n){ // 내가 지우고 싶은 자리로 cur이 설정된다.
cur = cur->rnext;
}
tmp = cur;
cur->lnext->rnext = cur->rnext;
cur->rnext->lnext = cur->lnext;
free(tmp);
ls->size--;
}
}
else{
puts("You entered wrong position.");
}
}
void Print_List(ListMark *ls){
Node *cur;
cur = ls->head;
if(cur == NULL){
puts("List is empty.\n");
}
else{
int n = 1;
while(n <= ls->size){
printf("List[%d] = %d.\n", n, cur->data);
cur = cur->rnext;
n++;
}
}
printf("\n");
}
void Return_Size(ListMark *ls){
printf("\nCurrent list size is %d.\n", ls->size);
// return size;
}
void Reset_List(ListMark *ls){
Node *tmp;
Node *cur;
cur = ls->head;
while(cur != ls->tail){
tmp = cur->rnext;
free(cur);
cur = tmp;
printf("Previous list size was %d, and now list size is %d.\n", ls->size, --ls->size);
}
free(cur);
printf("Previous list size is %d, and now list size is %d.\n", ls->size, --ls->size);
ls->head = NULL;
ls->tail = NULL;
ls->size = 0;
}
void Check_List(ListMark *ls){
printf("ls->head->data = %d.\n", ls->head->data);
printf("ls->tail->data = %d.\n", ls->tail->data);
printf("ls->head->rnext->data = %d.\n", ls->head->rnext->data);
printf("ls->tail->lnext->data = %d.\n", ls->tail->lnext->data);
printf("ls->head->lnext->lnext->data = %d.\n", ls->head->lnext->lnext->data);
printf("ls->tail->rnext->rnext->data = %d.\n", ls->tail->rnext->rnext->data);
printf("ls->head->rnext->rnext->data = %d.\n", ls->head->rnext->rnext->data);
printf("ls->tail->lnext->lnext->data = %d.\n\n", ls->tail->lnext->lnext->data);
}
int main(void) {
ListMark *ls = Init_List();
Add_First(ls, 11);
Add_First(ls, 12);
Add_First(ls, 13);
Add_First(ls, 14);
Return_Size(ls);
Print_List(ls);
Add_Last(ls, 21);
Add_Last(ls, 22);
Add_Last(ls, 23);
Add_Last(ls, 24);
Return_Size(ls);
Print_List(ls);
// Check_List(ls);// 여긴 잘 된다.
Reset_List(ls);
Return_Size(ls);
Print_List(ls);
Add_First(ls, 11);
Add_First(ls, 12);
Add_First(ls, 13);
Add_First(ls, 14);
Return_Size(ls);
Print_List(ls);
// Check_List(ls);
Add_Last(ls, 21);
Add_Last(ls, 22);
Add_Last(ls, 23);
Add_Last(ls, 24);
Return_Size(ls);
Print_List(ls);
// Check_List(ls);
Delete_First(ls);
Delete_First(ls);
Delete_First(ls);
Return_Size(ls);
Print_List(ls);
// Check_List(ls);
Delete_Last(ls);
Delete_Last(ls);
Delete_Last(ls);
Return_Size(ls);
Print_List(ls);
// Check_List(ls);
Add_Pos(ls, 1, 31);
Add_Pos(ls, 1, 32);
Print_List(ls);
// Check_List(ls);
Add_Pos(ls, 2, 33);
Add_Pos(ls, 3, 34);
Print_List(ls);
// Check_List(ls);
Delete_Pos(ls, 1, 31);
Delete_Pos(ls, 1, 32);
Print_List(ls);
// Check_List(ls);
Delete_Pos(ls, 2, 33);
Delete_Pos(ls, 3, 34);
Print_List(ls);
// Check_List(ls);
return 0;
}
아래 출력 결과는 main 함수를 그대로 출력한 것입니다.
이중 연결 리스트의 특성을 확인하기 위해선 main 함수에서 주석 처리된 Check_List() 함수를 실행하시면 됩니다.
아래 출력 결과 이후에 Check_List() 함수를 실행시킨 결과를 함께 확인해보겠습니다.
'Programming > C' 카테고리의 다른 글
| [자료구조 C 언어] C 프로그래밍 자료구조 - 12 : 스레드 이진 트리 (Thread Binary Tree) (0) | 2020.03.16 |
|---|---|
| [자료구조 C 언어] C 프로그래밍 자료구조 - 11 : 트리, 이진 트리의 개념 (Tree, Binary Tree) (0) | 2020.03.11 |
| [자료구조 C 언어] C 프로그래밍 자료구조 - 9 : 원형 연결리스트 (Circular Linked List) (0) | 2020.03.09 |
| [자료구조 C 언어] C 프로그래밍 자료구조 - 8 : 연결리스트를 사용한 큐 (Queue) (0) | 2020.03.05 |
| [자료구조 C 언어] C 프로그래밍 자료구조 - 7 : 연결리스트를 사용한 스택 (Stack) (0) | 2020.03.05 |