헤드노드를 이용한 이중연결리스트의 구현

헤드노드를 이용한 간단한 이중연결리스트의 구현프로그램입니다.

헤드노드는 구현의 편의를 위해 사용하는 것으로, 헤드노드를 이용해 이중연결리스트를 원형리스트와 결합된 형태로 사용할 수 있습니다. 

헤드노드는 리스트의 첫 번 째 노드를 가리키는 포인터로써, 아무런 데이터도 갖지않습니다. 주의해야 할 것은 헤드노드는 헤드포인터가 아니며 

원형리스트의 첫번째 삽입 연산처럼 본인의 left,right링크를 본인으로 설정해주는 초기화연산을 해야합니다. 

그러므로 헤드노드를 이용한 이중연결리스트의 구현에서 헤드 포인터는 필요가 없습니다.

또한 주의해야 할것은 헤드노드를 이용하여 삽입 할 때는 삽입한 노드를 맨 앞 노드로(헤드노드의 바로 뒤 노드) 설정하기 때문에

헤드노드의 left는 항상 맨 끝 노드를, right은 항상 맨 첫번 째 노드를 가리킵니다.  이 것이 원형리스트와 다른 유일한 점입니다. 

즉, 아래와 같은 구조를 가집니다.

코드

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct DlistNode
{
    int data;
    struct DlistNode* left;
    struct DlistNode* right;
}DlistNode;
void init(DlistNode* head)
{
    //원형 연결리스트처럼 최초의 링크주소는 본인가리킴
    head->left = head;
    head->right = head;
}
void insert_node(DlistNode* before, DlistNode* newNode)
{
    newNode->left = before;
    newNode->right = before->right;
    //주의)헤드노드의 left는 맨 뒤 노드를 가리킴
    before->right->left = newNode;
    before->right = newNode;
    //결과: 0,1,2,3,4 삽입 후 출력:4,3,2,1,0
}
 void remove_node(DlistNode* before, DlistNode* removed)
{
    //헤드노드는 지워지면안됨
    if (removed == before)
        return;
    removed->left->right = removed->right;
    removed->right->left = removed->left;
    free(removed);
}
void display(DlistNode* head)
{
    DlistNode* temp;
    for (temp = head->right; temp != head; temp = temp->right)
    {
        printf("%d \t", temp->data);
    }puts(" ");
}
int main()
{
    DlistNode head_node;
    DlistNode* p[5];
    init(&head_node);
    //5개의 노드 삽입//0~4
    for (int i = 0; i < 5; i++)
    {
        p[i] = (DlistNode*)malloc(sizeof(DlistNode));
        p[i]->data = i;
        insert_node(&head_node, p[i]);
    }
    remove_node(&head_node, p[4]);
    display(&head_node);
}

결과