자료구조 :: 리스트(4) 이중 연결리스트

# 이중 연결리스트

이중 연결리스트는 하나의 노드가 선행 노드와 후속 노드에 대한 두개의 링크를 가지는 리스트이다.
링크가 양방향이므로 알고리즘에 따라 양방향으로 자유롭게 검색이 가능하다.

DoubleLinkedList.cpp

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

typedefstruct NODE 
{ 
int data; 
    NODE *llink; 
    NODE *rlink; 
}NODE; 

// 이중연결리스트에서 필요한 헤드 노드를 만든다.
void Init_Node(NODE *phead) 
{ 
    phead->llink=phead; 
    phead->rlink=phead; 
}  

NODE* Create_Node(int pData) 
{ 
    NODE *New_Node=(NODE*)malloc(sizeof(NODE)); 
if(New_Node == NULL) 
    { 
        printf("메모리 할당 에러"); 
        exit(1); 
    } 

    New_Node->data=pData; 
    New_Node->llink=NULL; 
    New_Node->rlink=NULL; 

return New_Node; 
} 

// 노드의 오른쪽에 삽입
void Insert_Node(NODE *phead,NODE *New_Node) 
{ 
    New_Node->llink=phead; 
    New_Node->rlink=phead->rlink; 
    phead->rlink->llink=New_Node; 
    phead->rlink=New_Node; 
} 

void Remove_Node(NODE *phead,NODE *remove) 
{ 

if(remove == NULL || remove == phead)   
return ; // 헤드 노드는 삭제할 수 없다.

    remove->llink->rlink=remove->rlink; 
    remove->rlink->llink=remove->llink; 

    free(remove); 
} 

NODE* Search_Node(NODE *phead,int data) 
{ 
    NODE *p=phead->rlink; 

do
    { 
if(p->data == data)     
return p; 

        p=p->rlink; 

    }while(p != phead); 

returnNULL; 
} 

void Display_Node(NODE *phead) 
{ 
    NODE *p=phead->rlink; // phead는 데이터가 없다.

do
    { 
        printf("%d-> ",p->data); 

        p=p->rlink; 

    }while(p != phead); 

    printf("\n"); 
} 

int main() 
{ 
    NODE head,*p; 

    Init_Node(&head); 

    Insert_Node(&head,Create_Node(10)); 
    Insert_Node(&head,Create_Node(20)); 
    Insert_Node(&head,Create_Node(30)); 

    Display_Node(&head); // 오른쪽에 삽입했으모로 30->20->10

    p=Search_Node(&head,20);   

    Remove_Node(&head,p); 

    Display_Node(&head); // 30->10

return0; 

}