[자료구조] 이중연결리스트 Doubly Linked List

단순/단일연결리스트의 문제점

• 선행 노드를 찾기가 힘들다
• 삽입이나 삭제 시에는 반드시 선행 노드에 대한 정보가 필요

 

이중연결리스트

• 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 갖는 연결리스트
• 장점 : 링크가 양방향이므로 양방향으로 검색이 가능
• 단점 : 공간(2개의 포인터)을 많이 차지하고 코드가 복잡

 

이중연결리스트의 변형

1. 두 개의 포인터 사용
   
   
   • 첫 노드를 가리키는 포인터와 끝 노드를 가리키는 포인터를 각각 사용
   • head/tail 또는 front/rear 명칭 사용
2. 이중연결리스트 + 원형연결리스트
   
   
   • 실전에서 더욱 유용하게 사용됨.
   • 첫 노드와 마지막 노드 간의 양방향 link 유지
   • link값이 NULL인 경우가 없다.
3. 이중연결리스트 + 원형연결리스트 + 헤드노드
   
   
   • 헤드노드 사용: 코딩 편의 (빈리스트인지 검사 불필요)
   • 원형리스트 성질 : 포인터 NULL 없음
   • 이중연결리스트 성질 : 앞뒤 검색 모두 가능 – 편리
   • 가장 보편적이면서도 편리하게 사용 가능한 변형
   • 빈리스트여도 기본적으로 하나의 노드(헤드노드)는 존재

 

예제) 이중연결리스트 노드 추가 & 삭제

#include <iostream>
using namespace std;

class DNode {
public:
	int data;
	DNode *llink;
	DNode *rlink;

	DNode(int value) {
		data = value;
		llink = NULL;
		rlink = NULL;
	}
};

DNode *Head;

void insertDNodeLast(DNode *new_node) { //마지막 노드로 추가
	new_node->rlink = Head;
	new_node->llink = Head->llink;
	Head->llink->rlink = new_node;
	Head->llink = new_node;
}

void insertDNodeFirst(DNode *new_node) { //처음 노드로 추가
	new_node->llink = Head;
	new_node->rlink = Head->rlink;
	Head->rlink->llink = new_node;
	Head->rlink = new_node;
}

void deleteDNode(int key) {
	DNode *removed;

	for (removed = Head->rlink; removed != Head; removed = removed->rlink)
		if (removed->data == key) {
			removed->llink->rlink = removed->rlink;
			removed->rlink->llink = removed->llink;
			cout << "Node with data " << key << " deleted" << endl;
			return;
		}
	cout << "Nothing to delete!" << endl;
}

void printDNode() {
	for (DNode *ptr = Head->rlink; ptr != Head; ptr = ptr->rlink) //정순
																  //for (DNode *ptr = Head->llink; ptr != Head; ptr = ptr->llink) //역순
		cout << ptr->data << endl;

}


void main() {
	int number;
	int indata;

	Head = new DNode(-1);
	Head->rlink = Head;
	Head->llink = Head;

	cout << "처리할 데이터의 개수는? ";
	cin >> number;

	for (int i = 0; i < number; i++) {
		cout << "자료를 입력하세요 : ";
		cin >> indata;

		DNode *new_node = new DNode(indata);
		insertDNodeFirst(new_node);
	}

	printDNode();

	cout << "삭제할 노드의 값은? ";
	cin >> indata;
	deleteDNode(indata);

	printDNode();
}