SinglyLinkedList 에 이어 작성한 DoublyLinkedList 코드. SinglyLinkedList 와 다른점은, SinglyLinkedList 는 ‘다음’ 노드만 조회 할 수 있지만 DoublyLinkedList 는 ‘다음’ 노드와 ‘이전’ 노드를 조회 할 수 있다. 추가적으로, DoublyLinkedList 가 tail 변수를 가지고 있어서 가장 뒤에 노드를 추가 할 때 일일히 처음부터 순회 할 필요가 없어서 편하다.
앞뒤로 조회가 가능하기 때문에 중간에 노드를 삽입하거나, 삭제 할 때도 처음부터 순회 할 필요 없이 작업 할 수 있다.
코드를 작성하면서 의외로 내가 실수를 많이 했었다.
가장 많이 실수를 했던 부분은 SinglyLinkedList에서 맨 뒤에 추가를 할 때 while(current->nextNode != NULL) 을 사용했어서 여기서 헷갈려서 print 할때라던지 갯수를 셀때 current 가 NULL 인지 확인해야하는걸 current->nextNode 를 확인해서 좀 오류가 났었었다. DoublyLinkedList 에서는 current->nextNode 를 확인 해야 할 필요가 전혀 없으니 앞으로도 주의하도록 해야겠다. 물론 지금 내 머리가 맑지 않아서 저지른 실수이겠지만
그리고, 노드를 삭제하거나 중간에 삽입 할 때 변동 된 부분을 다시 제대로 연결해주는게 좀 헷갈렸는데, 그냥 생각나는대로 작성하는것 보다는 왼쪽에서 오른쪽으로, 아니면 오른쪽에서 왼쪽으로 머릿속에서 그려가면서 연결해주면 더 확실해진다.
메모리를 관리하는건 C++ 의 생명이니까, doublyLinkedList 클래스가 dispose 될 때 메모리를 제대로 정리하도록 했다.
/*
* DoublyLinkedList.cpp
* @author velopert
*/
#include <iostream>
using namespace std;
/*
* Node Class
*/
class Node {
public:
int data;
Node* prevNode;
Node* nextNode;
Node(int data);
void dispose();
};
Node::Node(int data) {
this->data = data;
this->prevNode = NULL;
this->nextNode = NULL;
}
void Node::dispose() {
cout << "disposing node.. data: " << this->data << endl;
delete this;
}
/*
* doublyLinkedList Class
*/
class doublyLinkedList {
public:
Node* head;
Node* tail;
doublyLinkedList();
~doublyLinkedList();
void insertLast(Node* node);
void insertFirst(Node* node);
void insertAfter(Node* target, Node* node);
void insertBefore(Node* target, Node* node);
Node* getNodeAt(int loc);
void removeNode(Node* node);
int getLength();
void print(bool isReverse);
};
doublyLinkedList::doublyLinkedList() {
this->head = NULL;
this->tail = NULL;
}
doublyLinkedList::~doublyLinkedList() {
if(!this->head) return;
Node* current = this->head;
while(current->nextNode) {
if(current->prevNode) current->prevNode->dispose();
current = current->nextNode;
}
current->dispose();
}
void doublyLinkedList::insertLast(Node* node) {
if(!this->head) {
this->head = node;
this->tail = node;
} else {
Node* current = this->tail;
current->nextNode = node;
node->prevNode = current;
this->tail = node;
}
}
void doublyLinkedList::insertFirst(Node* node) {
if(!this->head && !this->tail) {
this->head = node;
this->tail = node;
} else {
Node* current = this->head;
node->nextNode = current;
current->prevNode = node;
this->head = node;
}
}
void doublyLinkedList::insertAfter(Node* target, Node* node) {
if(target == this->tail) {
target->nextNode = node;
node->prevNode = target;
this->tail = node;
} else {
target->nextNode->prevNode = node;
node->nextNode = target->nextNode;
node->prevNode = target;
target->nextNode = node;
}
}
void doublyLinkedList::insertBefore(Node* target, Node* node) {
if(target == this->head) {
target->prevNode = node;
node->nextNode = target;
this->head = node;
} else {
target->prevNode->nextNode = node;
node->prevNode = target->prevNode;
node->nextNode = target;
target->prevNode = node;
}
}
Node* doublyLinkedList::getNodeAt(int loc) {
Node* node = this->head;
while(loc--) {
node = node->nextNode;
}
return node;
}
void doublyLinkedList::removeNode(Node* node) {
if(node==this->head) {
node->nextNode->prevNode = NULL;
this->head = node->nextNode;
} else if (node==this->tail) {
node->prevNode->nextNode = NULL;
this->tail = node->prevNode;
} else {
node->prevNode->nextNode = node->nextNode;
node->nextNode->prevNode = node->prevNode;
}
node->dispose();
}
int doublyLinkedList::getLength() {
int length = 0;
if(!this->head) return length;
Node* current = this->head;
while(current) {
current = current->nextNode;
length++;
}
return length;
}
void doublyLinkedList::print(bool isReverse=false) {
cout << "LinkedList" << (isReverse ? "(reversed): " : ": ");
Node* current = isReverse ? this->tail : this->head;
if(isReverse) {
while(current) {
cout << current->data;
current = current->prevNode;
if(current) {
cout << " <- ";
}
}
} else {
while(current!=NULL) {
cout << current->data;
current = current->nextNode;
if(current) {
cout << " -> ";
}
}
}
cout << endl;
}
/*
* testing
*/
int main() {
cout << "[TEST] Node creation & disposal" << endl;
Node* node = new Node(5);
cout << node->data << endl;
node->dispose();
doublyLinkedList dll;
cout << "[TEST] insertLast & insertFirst & print" << endl;
for(int i = 0; i < 10; i++) {
dll.insertLast(new Node(i));
}
dll.print();
for(int i = 10; i <20; i++) {
dll.insertFirst(new Node(i));
}
dll.print();
dll.print(true);
cout << "[TEST] node search" << endl;
node = dll.getNodeAt(3);
cout << node->data << endl;
cout << "[TEST] length: " << dll.getLength() << endl;
cout << "[TEST] insert before & after" << endl;
dll.insertBefore(dll.getNodeAt(0), new Node(100));
dll.print();
dll.insertBefore(dll.getNodeAt(3), new Node(101));
dll.print();
dll.insertAfter(dll.getNodeAt(dll.getLength()-1), new Node(102));
dll.print();
dll.insertAfter(dll.getNodeAt(2), new Node(103));
dll.print();
cout << "[TEST] removing" << endl;
dll.removeNode(node);
dll.print();
dll.removeNode(dll.getNodeAt(0));
dll.print();
dll.removeNode(dll.getNodeAt(dll.getLength()-1));
dll.print();
cout << "DLL disposal & end of program" << endl;
}
근데 내가 자료구조 공부를 하는 걸 재밌게 할 수 있을 지 몰랐다.
옛날에, 무작정 책 읽고 이해하면서 따라서 코드를 작성 할 때는 이게 도대체 뭐야~ 하면서 굉장히 지루해했었는데, 지금은 어느정도 지식의 기반이 잡힌 상태에서 그냥 내 맘대로 코드를 작성하니깐 흠흠 은근히 재미있다.
초심을 잃지 말고 앞으로도 틈틈히, 열심히 공부하고 복습도 자주 해야겠다.
근데,, 재밌긴 해도 아무래도 난 조만간 초심을 잃을 것 같다..
솔직히 난 개발을 좋아하는 편인데, 자료구조..를 난 개발로 간주하지 않는다
그냥 언젠가 볼 코딩면접 대비와 왠지 해야 할 것만 같은 압박감?아무리 자료구조가 프로그래머의 기본인건.. 인정하는 바 이지만,
그냥 이해만 하고, 필요할때 갖다 쓸 수 있으면 됐지,
언제나 백지에서부터 시작해서 처음부터 구현 할 능력을 갖출 필요가 있나 싶다.그리고 그렇게 할 수 있는 프로그래머라고 해서 개발을 잘하는가…
그래도, 자의로 자료구조를 한번 제대로 복습하는건 뭐 나쁘지 않으니까 노력은 해보자 🙂