[C++ Fundamentals of Data Structures/C++ 자료구조론(이석호)] 4.10 이중 연결 리스트

- 이중 연결 리스트

#include <iostream>
using namespace std;

class DblList;

class DblListNode {
	friend class DblList;
private:
	int data;
	DblListNode* left, * right;

public:
	DblListNode(int element, DblListNode* lNode = NULL, DblListNode* rNode = NULL) {
		data = element;
		left = lNode;
		right = rNode;
	}
};

class DblList {
private:
	DblListNode* head;
	DblListNode* tail;
	int size;

public:
	explicit DblList(int element) {
		tail = head = new DblListNode(element);
		size = 1;
	}
	~DblList();

	void InsertHead(int element) {
		DblListNode* newNode = new DblListNode(element);
		if (head == NULL)
			tail = head;
		else {
			newNode->right = head;
			head->left = newNode;
		}
		head = newNode;
		size++;
	}
	
	void InsertTail(int element) {
		DblListNode* newNode = new DblListNode(element);
		if (tail == NULL)
			head = tail;
		else {
			newNode->left = tail;
			tail->right = newNode;
		}
		tail = newNode;
		size++;
	}

	void Insert(DblListNode* newnode, DblListNode* x) { //x의 오른쪽에 newnode 삽입
		if (x == tail) { //x가 tail노드면 x 오른쪽에 newnode삽입 후, newnode를 tail로 지정
			newnode->left = x;
			newnode->right = NULL;
			x->right = newnode;
			tail = newnode;
		}
		else {
			newnode->left = x;
			newnode->right = x->right;
			x->right = newnode;
			x->right->left = newnode;
		}
	}

	void Delete(DblListNode* x) { // 노드 x 삭제
		if (x == head) {
			x->right->left = NULL;
			head = x->right;
			delete x;
		}
		else if (x == tail) {
			x->left->right = NULL;
			tail = x->left;
			delete x;
		}
		else {
			x->left->right = x->right;
			x->right->left = x->left;
			delete x;
		}
	}
};

* 도저히 디버깅까진 자신 없음 ^^..

* 함수 작성으로 만족하겠음

* 참고 : https://hazarddev.tistory.com/42

 

 

- 원형 이중 연결 리스트

#include <iostream>
using namespace std;

class DblList;

class DblListNode {
	friend class DblList;
private:
	int data;
	DblListNode* left, * right;

public:
	DblListNode(int element = 0, DblListNode* lNode = NULL, DblListNode* rNode = NULL) {
		data = element;
		left = lNode;
		right = rNode;
	}

	friend class DblList;
	friend ostream& operator<<(ostream& os, DblList& d);
};

class DblList {
private:
	DblListNode* first;

public:
	DblList() { //이중 원형 연결 리스트
		first = new DblListNode;
		first->left = first;
		first->right = first;
	}
	~DblList() {
		DblListNode* delNode = first; //위치를 기억해두어야한다
		DblListNode* delNextNode = first->right;

		while (1) {
			if (delNextNode->data >= 0) { //dummynode의 데이터 0, 그 외 양수
				delete delNode;
				delNode = delNextNode;
				delNextNode = delNextNode->right;
			}
			else {
				delete delNode;
				break;
			}
		}
	}

	void Insert(DblListNode* newnode, DblListNode* x) { //노드 x의 오른쪽에 newnode삽입
		newnode->left = x;
		newnode->right = x->right;
		x->left = newnode;
		x->right = newnode;
	}

	void Delete(DblListNode* x) { //노드 x 삭제
		x->left->right = x->right;
		x->right->left = x->left;
		delete x;
	}
	friend ostream& operator<<(ostream& os, DblList& d);
};

ostream& operator<<(ostream& os, DblList& d) {
	os << "오른쪽 진행" << endl;
	DblListNode* temp1 = d.first, * temp2 = d.first; //first의 위치 저장
	os << "dummy->";

	while (temp1->right->data != 0) {
		os << temp1->right->data;
		if (temp1->right->right->data != 0)
			os << "->";
		else
			os << " ";
		temp1 = temp1->right;
	}

	os << endl << "왼쪽 진행" << endl;
	os << "dummy->";

	while (temp2->left->data != 0) {
		os << temp2->left->data;
		if (temp2->left->left->data != 0)
			os << "->";
		else
			os << " ";
		temp2 = temp2->left;
	}
	return os;
}

int main(void) {
	DblList d;
	DblListNode* temp1 = new DblListNode(1);
	DblListNode* temp2 = new DblListNode(2);
	DblListNode* temp3 = new DblListNode(3);
	DblListNode* temp4 = new DblListNode(4);

	d.Insert(temp1, NULL);
	d.Insert(temp2, temp1);
	d.Insert(temp3, temp2);
	d.Insert(temp4, temp3);

	cout << "더블 링크드리스트 출력" << endl;
	cout << d << endl;

	d.Delete(temp1);
	cout << "더블 링크드리스트 출력" << endl;
	cout << d << endl;

	return 0;
}

* 디버깅 안 돌려봄

* 중요한 건 삽입, 삭제 함수 !

* 참고 : https://jaimemin.tistory.com/169