[C++] 이중연결리스트 코드 구현 방법 Doubly linked list

이 포스트에서는 이중연결 리스트를 C++ 코드로 구현하는 방법을 다룬다.

 

▣ 연결리스트 종류

 ●  단순 연결 리스트 (Simply linked list)

  ▷ 하나의 링크만 있고, 각각 노드의 링크는 후행 노드만을 가리키는 구조다.

•   특정 노드의 후행 노드는 쉽게 접근할 수 있지만, 특정 노드의 선행 노드에 대한 접근은 헤드 노드부터 재검색해야 하는 문제점이 있다. 
•   자세한 내용은 아래 포스트를 참고하세요.

2020/09/10 - [Programming/Data Structure] - [C++] 연결리스트 Linked list 코드 구현 방법

[C++] 연결리스트 Linked list 코드 구현 방법

 

●  원형 연결 리스트 (Circular linked list)

원형 연결 리스트 관련 글은 아래 포스트를 참고하세요. 

2020/09/11 - [Programming/Data Structure] - [C++] 원형 연결 리스트 코드 구현 방법 Circular linked list

[C++] 원형 연결 리스트 코드 구현 방법 Circular linked list

 

●  이중 연결 리스트 (Doubly linked list)

  ▷ 특정 노드는 선행 노드를 가리키는 링크와 후행 노드를 가리키는 링크를 가진다.

•   특정 노드에서 선행 노드와 후행 노드에 간단한 프로그램 코드를 통해 접근할 수 있다.

  ▷ 이중연결리스트의 Rhead는 첫 노드를 가리키고, Lhead는 리스트의 마지막 노드를 가리킨다.  

  ▷ 이중연결리스트의 마지막 노드의 Rlink는 NULL이고, 첫 노드의 Llink는 NULL이다.

 

▣ 이중연결리스트 코드 구현

● doubleLinkedList.h  ( 이중연결리스트 클래스를 구현한 헤더파일, 귀찮아서 그냥 헤더파일에 집어넣었다 전부..)

#pragma once
#include <iostream>
using namespace std;

struct Node {
	int data;
	Node* Llink;
	Node* Rlink;
};

struct HeadNode {
	Node* Lhead; // 원래 리스트의 반대쪽으로
	Node* Rhead; // 원래 연결리스트 방향으로
};

class doubleList {

public:
	/* 이중연결리스트 생성 */
	HeadNode* createList() {
		HeadNode* H = new HeadNode;
		H->Lhead = NULL;
		H->Rhead = NULL;
		return H;
	}

	/* 이중연결리스트 끝에 노드 삽입*/
	void addEndNode(HeadNode* H, int adddata) {
		Node* prevNode;
		Node* newNode = new Node;
		newNode->data = adddata;
		newNode->Llink = NULL;
		newNode->Rlink = NULL;
		
		if (H->Rhead == NULL) { // 리스트가 비어있을 때
			H->Rhead = newNode;
			H->Lhead = newNode;
		}
		else { // 리스트에 노드가 있을 때
			prevNode = H->Lhead;  // 리스트의 마지막노드는 Lhead가 가리키고 있을 것이므로 이걸 prevNode로 
			prevNode->Rlink = newNode;
			newNode->Llink = prevNode;
			H->Lhead = newNode; // 새 노드가 마지막 노드가 된다.
		}
	}

	/* 이중연결리스트 특정 노드 삽입*/
	void addThisNode(HeadNode* H, int afterthisdata, int adddata) {
		Node* prevNode;
		Node* newNode = new Node;
		newNode->data = adddata;
		newNode->Llink = NULL;
		newNode->Rlink = NULL;

		prevNode = H->Rhead;

		while (prevNode->data != afterthisdata) {
			prevNode = prevNode->Rlink;
		}

		newNode->Rlink = prevNode->Rlink; //새 노드가 이전노드가 가리키던 노드를 가리키게
		newNode->Llink = prevNode;  // 새노드의 Llink가 이전노드를 가리키게
		prevNode->Rlink = newNode;  // 이전노드의 Rlink가 새노드를 가리키게
		newNode->Rlink->Llink = newNode; // 새노드의 다음 노드의 Llink가 이전노드가 아닌 새노드를 가리키게
	}

	/* 이중연결리스트 특정 노드 삭제*/
	void deleteNode(HeadNode* H, int deldata) {
		Node* delNode;
		delNode = H->Rhead;

		if (delNode == NULL) return; // 리스트가 빈 경우

		while (delNode->data != deldata) {
			delNode = delNode->Rlink;
		}

		if (delNode == H->Lhead) { //삭제할 노드가 리스트의 마지막 노드일 때
			if (delNode == H->Rhead) { // 삭제할 노드가 유일한 노드일 때 
				H->Rhead = NULL;
				H->Lhead = NULL;
			}
			else { 
				delNode->Llink->Rlink = NULL; //삭제할노드 바로 앞 노드의 Rlink가 NULL
				H->Lhead = delNode->Llink;  // 헤드의 Lhead가 삭제할노드 바로 앞 노드를 가리키게
			}
		}
		else if (delNode == H->Rhead) { //삭제할 노드가 리스트의 첫 노드일 때
			H->Rhead = delNode->Rlink;
			delNode->Rlink->Llink = NULL;
			}
		else {
			delNode->Llink->Rlink = delNode->Rlink;
			delNode->Rlink->Llink = delNode->Llink;
		}
		delete delNode;
		cout << deldata << "를 가지는 노드를 삭제했습니다." << endl;
	}

	/* 이중연결리스트 출력*/
	void printList(HeadNode* L) {

		//노드 순서대로 리스트 출력
		Node* p;

		p = L->Rhead;

		if (p == NULL) { // 리스트가 빈 경우
			cout << endl << "연결 리스트가 비어있습니다." << endl << endl;
			return;
		}

		cout << "연결리스트 목록 = ( ";

		while (p != NULL) {
			cout << p->data;
			p = p->Rlink;
			if (p != NULL) cout << " --> ";
		}
		cout << " )" << endl << endl;
	}

};

 

● doublistMain.cpp 

이중연결리스트를 구현하는 main함수가 들어있는 코드다.

#include <iostream>
#include "doubleLinkedList.h"
using namespace std;

void main()
{
	doubleList list;
	HeadNode* L;
	L = list.createList();

	cout << "1. 빈 연결 리스트를 생성했습니다." << endl << endl;

	int data1, data2, data3;
	cout << "2. 연결 리스트에 추가할 노드의 데이터를 3개 정해주세요: ";
	cin >> data1 >> data2 >> data3;
	list.addEndNode(L, data1);
	list.printList(L);
	list.addEndNode(L, data2);
	list.printList(L);
	list.addEndNode(L, data3);
	list.printList(L);
	cout << endl;


	cout << "3-1. 어떤 노드 뒤에 노드를 추가할건가요? ";;
	cin >> data1;
	cout << "3-2. 그 노드 뒤에 어떤 데이터를 가진 노드를 추가할건가요? ";
	cin >> data2;
	list.addThisNode(L, data1, data2);
	list.printList(L);
	cout << endl;

	cout << "4-1. 삭제하고자 하는 노드를 알려주세요 : ";
	cin >> data1;
	list.deleteNode(L, data1);
	list.printList(L);
	cout << endl;

	cout << "4-2. 삭제하고자 하는 노드를 또 알려주세요 : ";
	cin >> data2;
	list.deleteNode(L, data2);
	list.printList(L);
	cout << endl;

	cout << "4-3. 삭제하고자 하는 노드를 또 알려주세요 : ";
	cin >> data3;
	list.deleteNode(L, data3);
	list.printList(L);
	cout << endl;

	cout << "4-4. 삭제하고자 하는 노드를 또 알려주세요 : ";
	cin >> data1;
	list.deleteNode(L, data1);
	list.printList(L);
	cout << endl;

	cout << "피곤하니까 연산을 끝내겠습니다." << endl;

}

 

● 출력결과