[알고리즘] Doubly Linked List ( 정의 / 주요 연산 )

https://steady-developer-hyemin.tistory.com/19

[알고리즘] Linked List ( 노드 추가, 탐색, 삭제, 삽입 )

더블 링크드 리스트 (이중 연결 리스트)

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

- 양방향으로 탐색이 가능

 

링크드 리스트 : 노드가 다음 노드를 가리키는 포인터만을 가집니다.

더블 링크드 리스트 : 노드가 다음 노드를 가리키는 포인터도 있고 노드가 자신의 앞에 있는 노드를 가리키는 포인터도 갖고 있습니다. (양방향)

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

 

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

노드 생성 / 소멸

1. 노드의 생성

/* 노드 생성 */
Node* DLL_CreateNode(ElementType NewData)
{
	Node* NewNode = (Node*)malloc(sizeof(Node));
    NewNode -> Data = NewData;
    
    NewNode -> PrevNode = NULL;
    NewNode -> NextNode = NULL;
    
    return NewNode;
}

링크드 리스트에서 PrevNode에 NULL을 대입하여 초기화하는 부분만 추가되었습니다.

 

2. 노드의 소멸

/* 노드의 소멸 */
void DLL_DestroyNode(Node* Node)
{
	free(Node);
}

노르를 자유 저장소에서 제거하는 함수는 링크드 리스트와 동일합니다.

 

 

노드 추가

/* 노드 추가 */
void DLL_AppendNode(Node** Head, Node* NewNode)
{	/* 해드 노드가 NULL이라면 새로운 노드가 Head*/
	if((*Head) == NULL)
    {
    	*Head = NewNode;
    }
    else
    {
    	/* tail을 찾아 NewNode를 연결*/
    	Node* Tail = (*Head);
        while (Tail -> NextNode != NULL)
        {
        	Tail = Tail -> NextNode;
        }
        Tail -> NextNode = NewNode;
        NewNode -> PrevNode = Tail;
    }
}

주어진 노드를 리스트의 끝에 추가합니다. 함수는 헤드 포인터와 새로운 노드를 매개변수로 받아들이며, 헤드 노드가 NULL인 경우 새로운 노드가 헤드가 되고, 그렇지 않은 경우 리스트의 끝에 새로운 노드가 추가됩니다.

 

 

노드 탐색

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 -> PrevNode = NULL;
        Remove -> NextNode = NULL;
        
    }
    else
    {
    	Node* Temp = Remove;
        Remove -> PrevNode -> NextNode = Temp -> NextNode;
        if(Remove -> NextNode != NULL)
        	Remove -> NextNode -> PrevNode = Temp -> PrevNode;
        
        Remove -> PreNode = NULL;
        Remove -> NextNode = NULL;
    }
}

더블 링크드 리스트는 삭제할 노드의 양쪽 포인터 두 개, 이전 노드의 NextNode 포인터, 이후 노드의 PrevNode 포인터 등 모두 4개의 포인터를 다뤄야합니다.

삭제할 노드의 NextNode 포인터가 가리키고 있던 노드의 NextNode 포인터가 가리키게 바꾸고, 또 삭제할 노드의 PrevNode 포인터가 가리키고 있던 노드를 뒷 노드의 PrevNode 포인터가 가리키게 바꿉니다.

그리고 삭제할 노드의 NextNode와 PrevNode는 깨끗하게 NULL로 초기화 합니다.

 

 

노드 삽입

/* 노드 삽입 */
void DLL_InsertAfter(Node* Current, Node* NewNode)
{
    NewNode->NextNode = Current->NextNode;
    NewNode->PrevNode = Current;

    if (Current->NextNode != NULL)
    {
        Current->NextNode->PrevNode = NewNode;
    }
    Current->NextNode = NewNode;
}

NewNode의 NextNode 포인터를 Current의 NextNode로 설정하여 새 노드가 Current의 다음 노드를 가리키도록 합니다.

NewNode의 PrevNode 포인터를 Current로 설정하여 새 노드가 Current를 가리키도록 합니다.

Current 의 NextNode가 NULL이 아닌 경우,

현재 노드의 다음 노드의 PrevNode 포인터를 NewNode로 설정하여 NewNode가 다음 노드를 가리키게 합니다.

그리고 Current의 NextNode 포인터를 NewNode로 설정하여, Current의 다음 노드가 NewNode를 가리키게 합니다.