[자료구조] 리스트 - 02 . 더블 링크드 리스트

[더블 링크드 리스트]

[더블 링크드 리스트]

=>링크드 리스트의 탐색기능을 개선한 자료구조

: 헤드 -> 테일의 일방탐색에서 양방향 탐색이 가능하다 .

 

[구조]

=>자신의 앞에 있는 노드 와 자신의 다음 노드 두가지 포인터를 가지고 있다.

출처 : https://www.geeksforgeeks.org/difference-between-singly-linked-list-and-doubly-linked-list/

[구조체로 표현]

=>구조체로 표현해보자면 다음과 같다.

typedef struct tagNode
{
    int Data;	//데이터 필드
    struct tagNode* PrevNode;	//그전 노드를 가리키는 포인터
    struct tagNode* NextNode;	//다음 노드를 가리키는 포인터
}Node;

[더블 링크드 리스트의 주요 연산]

[노드의 생성과 소멸]

 

생성

//노드 생성

void DLL_CreateNode(ElementType data)
{
    Node* NewNode=(Node*)malloc(sizeof(Node));
    NewNode->PrevNode=NULL;
    NewNode->NextNode=NULL;
    NewNode->Data=data;
    
    return NewNode;
}

소멸

//소멸

void DLL_DestroyNode(Node* Node)
{
	free(Node);
}

 

[노드 추가]

 

추가

//추가

void DLL_AppendNode(Node ** Head,Node * NewNode)
{
    if((*Head)==NULL)
    {
    	(*Head)=NewNode;
    }
    else
    {
    	Node*Tail=(*Head);
        while(Tail->NewNode!=NULL)
        {
        	Tail=Tail->NextNode;
        }
        Tail->NextNode=NewNode;
        NewNode->PrevNode=Tail;	//기존의 테일을 새로운 테일의 PrevNode가 가리킨다
    }
}

 

[노드 탐색]

 

탐색

//탐색

Node* DLL_GetNodeAt(Node * Head , int Location)
{
    Node* Current=Head;
    while(Current!=NULL&&(--Location)>=0)
    {
    	Current=Current->NextNode;
    }
    return Current; 
}

 

[노드 삭제]

 

삭제

//삭제

void DLL_RemoveNode(Node**Head , Node* Remove)
{
    if((*Head)==Remove)
    {
    	(*Head)=Remove->NextNode;
        if((*Head)!=NULL
        	  (*Head)->PrevNode=NULL;
              
        Remove->NextNode=NULL;
        Remove->PrevNode=NULL;     
    }
    else
    {
    	Node*Temp=Remove;
        Remove->PrevNode->NextNode=Temp->NextNode;
        if(Remove->NextNode!=NULL)
        Remove->NextNode->PrevNode=Temp->PrevNode;
        
        Remove->NextNode=NULL;
        Remove->PrevNode=NULL;
    }
}

 

[노드 삽입]

 

삽입

//노드 삽입
void SLL_InsertNode(Node*Current , Node *NewNode)
{
	NewNode->PrevNode=Current;
    NewNode->NextNode=Current->NextNode;
    
    if(Curremt->NextNode!=NULL)
    {
    	Current->NextNode->PrevNode=NewNode;
    }
    Current->NextNode=NewNode;
}

 

[노드 개수 세기]

 

개수 새기

int DLL_GetNodeCount(Node*Head)
{
    unsigned int count=0;
    Node * Current=Head;
    
    while(Current!=NULL)
    {
    	Current=Current->NextNode;
        count++;
    }
    return count;
}