[자료구조] 이중연결리스트(Double Linked List)

- 이중연결리스트는 앞 노드를 가리키는 rlink와

  뒤 노드를 가리키는 llink 두 개의 링크가 더해진 구조이다.

  이렇게 함으로써 양방향으로 검색이 가능해진다.

 

- 이중연결리스트는 head라는 노드 포인터를 가지지 않고

   데이터가 없는 빈 노드 구조체인 head를 가진다.

   head 구조체의 오른편에 리스트를 연결시킨다.

   따라서 맨 처음 초기화 단계에서 head 구조체의 rlink와 llink 모두 head 자신을 가리킨다.

//head 초기화 함수
void init(DListNode* head){
    head->rlink = head;
    head->llink = head;
}

 

- 삽입할 때는 head 구조체의 오른쪽에 삽입할 것이다.

//노드 삽입 함수
DListNode* insert_node(DListNode* before){
    int data;
    DListNode* new_node;
    
    printf("input data : ");
    scanf("%d", &data);
    
    new_node = create_node(data);
    
    new_node->llink = before;
    new_node->rlink = before->rlink;
    before->rlink->llink = new_node;
    before->rlink = new_node;
    
    return before;
}

 

- 삭제하는 함수

//노드 삭제 함수
DListNode* delete_node(DListNode* head){
    if(head == NULL){
        return NULL;
    }else{
        head->rlink = head->rlink->rlink;
        head->rlink->llink = head;
        
        return head;
    }
}

 

<<전체코드>>

//이중 연결 리스트

#include <stdio.h>
#include <stdlib.h>

typedef struct ListNode{
    int data;
    struct ListNode *llink;
    struct ListNode *rlink;
}DListNode;

//노드 생성 함수
DListNode* create_node(int data){
    DListNode* node;
    
    node = (DListNode*)malloc(sizeof(DListNode));
    node->data = data;
    node->llink = NULL;
    node->rlink = NULL;
    
    return node;
}

//head 초기화 함수
void init(DListNode* head){
    head->rlink = head;
    head->llink = head;
}

//노드 삽입 함수
//새로운 노드를 before의 오른쪽에 삽입한다.
DListNode* insert_node(DListNode* head){
    int data;
    DListNode* new_node;
    
    printf("input data : ");
    scanf("%d", &data);
    
    new_node = create_node(data);
    
    new_node->llink = head;
    new_node->rlink = head->rlink;
    head->rlink->llink = new_node;
    head->rlink = new_node;
    
    return head;
}

DListNode* delete_node(DListNode* head){
    if(head == NULL){
        return NULL;
    }else{
        head->rlink = head->rlink->rlink;
        head->rlink->llink = head;
        
        return head;
    }
}

//출력하는 함수
void print_node(DListNode* head){
    DListNode* temp;
    
    for(temp = head->rlink; temp != head; temp = temp->rlink){
        printf("%d ", temp->data);
    }
    printf("\n");
}

int main(int argc, const char * argv[]) {
    int menu;
    
    //여기서 head는 포인터 변수가 아니고 구조체 변수이다.
    DListNode* head = (DListNode*)malloc(sizeof(DListNode));
    init(head);
    
    do{
        printf("========================\n");
        printf("1.insert 2.delete 3.print 4.end\n");
        printf("========================\n");
        printf("menu : ");
        scanf("%d", &menu);
        
        if(menu == 1){
            head = insert_node(head);
        }else if(menu == 2){
            head = delete_node(head);
        }else if(menu == 3){
            print_node(head);
        }
    }while(menu != 4);
}