자료 구조 - 더블 링크드 리스트(Double Linked List)

더블 링크드 리스트는 기존의 링크드 리스트에서 탐색 기능을 개선한 자료 구조입니다.

기존의 다음 노드에 대한 포인터만 존재하던 노드에서 이전 노드에 대한 포인터를 추가하여 양방향으로 탐색이 가능하도록 만든 자료 구조입니다.

아래는 더블 링크드 리스트의 코드입니다.

typedef struct tagNode {
	int Data; // 데이터 필드
	struct tagNode* PrevNode; // 이전 노드에 대한 포인터
	struct tagNode* NextNode; // 다음 노드에 대한 포인터
} Node;

 

더블 링크드 리스트 노드의 생성과 소멸

---

기존의 링크드 리스트에서 이전 노드에 데한 포인터(PrevNode)를 NULL로 초기화하는 것만이 추가되었습니다.

Node* DLL_CreatNode(int NewData) {
	Node* NewNode = (Node*)malloc(sizeof(Node));
	NewNode->Data = NewData;
	NewNode->PrevNode = NULL;
	NewNode->NextNode = NULL;

	return NewNode;
}

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

 

 

더블 링크드 리스트 노드의 추가와 삭제

---

더블 링크드 리스트 노드의 추가는 이전 노드(PrevNode)에 대한 포인터를 연결해주면 됩니다.

void DLL_AppendNode(Node** Head, Node* NewNode) {
	if (*Head == NULL) {
		*Head = NewNode; // 헤드가 널이면 새로운 노드가 헤드
	}
	else {
		Node* Tail = (*Head);
		while (Tail->NextNode != NULL)
		{
			Tail = Tail->NextNode;
		}
		Tail->NextNode = NewNode; // 마지막 노드의 다음 노드에 새로운 노드 연결
		NewNode->PrevNode = Tail; // 새로운 노드의 이전 노드는 기존의 마지막 노드
	}
}

 

노드의 삭제는 조금 더 복잡합니다. 삭제할 노드의 이전 노드, 다음 노드의 포인터를 적절하게 연결해줘야 합니다.

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 = Remove->NextNode;  // 삭제할 노드의 이전 노드의 다음 노드에 대한 포인터는 삭제할 노드의 다음 노드
		if (Remove->NextNode != NULL) { // 삭제할 노드의 다음 노드가 널이 아니면
			Remove->NextNode->PrevNode = Temp->PrevNode; // 삭제할 노드의 다음 노드의 이전 노드에 대한 포인터는 삭제할 노드의 이전 노드
		}

		Remove->NextNode = NULL; // 삭제한 노드 초기화
		Remove->PrevNode = NULL;
	}
}

 노드의 탐색은 기존의 링크드 리스트와 똑같습니다. 밑의 포스팅을 참고해주세요.

2021/01/19 - [etc/Data Structure] - 자료 구조 - 링크드 리스트(Linked List)

자료 구조 - 링크드 리스트(Linked List)

 

더블 링크드 리스트 노드의 삽입

---

노드의 삽입은 아래와 같은 과정으로 이루어집니다.

1. 새로운 노드의 PrevNode 포인터는 앞 노드(이전 노드)를, NextNode 포인터는 뒷 노드(다음 노드)를 가리킨다.
2. 앞 노드의 NextNode와 뒷 노드의 PrevNode 포인터는 새로운 노드를 가리킨다.

void DLL_InsertAfter(Node* Current, Node* NewNode) {
	// Current 뒤에 NewNode 추가
    
	NewNode->NextNode = Current->NextNode; // 새로운 노드의 다음 노드는 현재 노드의 다음 노드
	NewNode->PrevNode = Current; // 새로운 노드의 이전 노드는 현재 노드

	if (Current->NextNode != NULL) { // 현재 노드의 다음 노드가 널이 아니면
		Current->NextNode->PrevNode = NewNode; //현재 노드의 다음 노드의 이전 노드에 대한 포인터는 새로운 노드
	}
	Current->NextNode = NewNode; // 현재 노드의 다음 노드에 대한 포인터는 새로운 노드
}