- 이중 연결 리스트
#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;
}
* 디버깅 안 돌려봄
* 중요한 건 삽입, 삭제 함수 !