(C) 자료구조 - 이중 연결 리스트의 구조와 구현

1. 이중 연결 리스트의 개념

- 한계점

단순 연결 리스트 : 선행 노드로 접근하기 어렵다. -> 원형 연결 리스트를 통해 한계점 극복.

원형 연결 리스트 : 현재 노드 바로 이전 노드로 접근하려면 전체 리스트를 한 바퀴 순회해야 한다.

-> 이중 연결 리스트를 통해 한계점 극복.

 

- 이중 연결 리스트

양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트

이중 연결 리스트의 노드 구조

- 원형 이중 연결 리스트

원형 연결 리스트의 구조

 

<이중 연결 리스트의 구조체 정의>

typedef struct Dnode{
    struct Dnode *llink;
    char data[5];
    struct Dnode *rlink;
}

---

2. 이중 연결 리스트의 알고리즘

- 공백 이중 연결 리스트를 생성하는 연산

// 공백 이중 연결 리스트를 생성하는 연산
linkedList_h* createLinkedList_h(void) {
    linkedList_h* DL;
    DL = (linkedList_h*)malloc(sizeof(linkedList_h));            // 헤드 노드 할당
    DL->head = NULL;
    return DL;
}

 

- 이중 연결 리스트를 순서대로 출력하는 연산

// 이중 연결 리스트를 순서대로 출력하는 연산
void printList(linkedList_h* DL) {
    listNode* p;
    printf(" DL = (");
 
    p = DL->head;
    while (p != NULL) {
        printf("%s", p->data);
        p = p->rlink;
        if (p != NULL) printf(", ");
    }
    printf(") \n");
}

 

 

2-1. 이중 연결 리스트에 노드를 삽입하는 알고리즘

1) 삽입할 노드를 준비한다.

2) 새 노드의 데이터 필드에 값을 저장한다.

3) 새 노드 왼쪽 노드의 오른쪽 링크 필드(rlink)에 있던 값을 새 노드의 오른쪽 링크 필드(rlink)에 저장한다.

4) 왼쪽 노드의 오른쪽 링크 필드(rlink)에 새 노드의 주소를 저장한다.

5) 새 노드 오른쪽 노드의 왼쪽 링크 필드(llink)에 있던 값을 새 노드의 왼쪽 링크 필드(llink)에 저장한다.

6) 오른쪽 노드의 왼쪽 링크 필드(llink)에 새 노드의 주소를 저장한다.

7) 노드를 순서대로 연결한다.

// pre 뒤에 노드를 삽입하는 연산
void insertNode(linkedList_h* DL, listNode* pre, char* x) {
    listNode* newNode;
    newNode = (listNode*)malloc(sizeof(listNode));
    strcpy(newNode->data, x);
    if (DL->head == NULL) {
        newNode->rlink = NULL;
        newNode->llink = NULL;
        DL->head = newNode;
    }
    else {
        newNode->rlink = pre->rlink;
        pre->rlink = newNode;
        newNode->llink = pre;
        if (newNode->rlink != NULL) // 삽입 자리에 다음 노드가 있는 경우
            newNode->rlink->llink = newNode;
    }
}

 

 

2-2. 이중 연결리스트에서 노드를 삭제하는 알고리즘

1) 삭제할 노드의 오른쪽 노드와 왼쪽 노드를 찾는다.

2) 삭제할 노드의 오른쪽 노드(old.rlink) 의 주소를 삭제할 노드의 왼쪽 노드(old.llink)의 오른쪽 링크 필드(rlink)에 저장한다.

3) 삭제할 노드의 왼쪽 노드(old.llink)의 주소를 삭제할 노드의 오른쪽 노드(old.rlink)의 왼쪽 링크 필드(llink)에 저장한다.

4) 노드를 순서대로 연결한다.

// 이중 연결 리스트에서 old 노드를 삭제하는 연산
void deleteNode(linkedList_h* DL, listNode* old) {
    if (DL->head == NULL) return;        // 공백 리스트인 경우 삭제 연산 중단
    else if (old == NULL) return;            // 삭제할 노드가 없는 경우 삭제 연산 중단
    else {
        old->llink->rlink = old->rlink;
        old->rlink->llink = old->llink;
        free(old);                                // 삭제 노드의 메모리 해제
    }
}

 

- 이중 연결 리스트의 프로그램

#include <stdio.h>
#include "DoubleLinkedList.h"
 
int main(void) {
    linkedList_h* DL;
    listNode* p;
 
    DL = createLinkedList_h();            // 공백 리스트 생성
    printf("(1) 이중 연결 리스트 생성하기! \n");
    printList(DL);
 
    printf("\n(2) 이중 연결 리스트에 [월] 노드 삽입하기! \n");
    insertNode(DL, NULL, "월");
    printList(DL);
 
    printf("\n(3) 이중 연결 리스트의 [월] 노드 뒤에 [수] 노드 삽입하기! \n");
    p = searchNode(DL, "월"); insertNode(DL, p, "수");
    printList(DL);
 
    printf("\n(4) 이중 연결 리스트의 [수] 노드 뒤에 [금] 노드 삽입하기! \n");
    p = searchNode(DL, "수"); insertNode(DL, p, "금");
    printList(DL);
 
    printf("\n(5) 이중 연결 리스트에서 [수] 노드 삭제하기! \n");
    p = searchNode(DL, "수"); deleteNode(DL, p);
    printList(DL);
 
    getchar(); return 0;
}