구현 - 더블 링크드 리스트

계속해서 느끼는 것이지만, ADT를 생각하고 그림을 그려서 구현하는 게 가장 효과적인 길인 것 같다.

좀 더 생각해봐야 할 것:

구조체에 이런저런 멤버 함수를 만드는게 타당할까? 밑의 DNode는 별로 바람직해보이지 않는다.

아예 클래스로 만들어서 숨길 건 숨기고 객체화 하는게 '객체지향적'인 면에서는 좋을 것 같다.

struct DNode

{

int _data{ 0 };

DNode* _prev{ nullptr };

DNode* _next{ nullptr };

DNode(int n = 0) :_data(n) {};

void insert_before(DNode* point)

{

this->_next = point;

this->_prev = point->_prev;

if (point->_prev)

point->_prev->_next = this;

point->_prev = this;

}

void suicide()

{

if (this->_prev)

this->_prev->_next = this->_next;

if (this->_next)

this->_next->_prev = this->_prev;

delete this;

}

};

class DoubleLinkedList

{

private:

DNode* front{};

DNode* back{};

public:

DNode* begin() { return front; }

DNode* end() { return back->_next; }

DNode* Back() { return back; }

bool isEmpty()

{

return front == nullptr;

}

DNode* insert(DNode* point, int data)

{

if (front && !point) throw;

DNode* newNode = new DNode(data);

if (isEmpty())

{

front = back = newNode;

return newNode;

}

if (front == point)

front = newNode;

newNode->insert_before(point);

return newNode;

}

void erase(DNode* point)

{

if (isEmpty() || point == nullptr) throw;

if (point == front)

front = front->_next;

else if (point == back)

back = back->_prev;

point->suicide();

}

void push_back(int data)

{

DNode* newNode = new DNode(data);

if (isEmpty())

front = back = newNode;

else

{

newNode->_prev = back;

back->_next = newNode;

back = newNode;

}

}

void display()

{

cout << "double linked list : \n";

for (DNode* iter = begin(); iter; iter = iter->_next)

{

cout << iter->_data << endl;

}

if (!front) cout << "is empty\n";

}

void clear()

{

while (front)

{

DNode* temp = front;

front = front->_next;

delete temp;

}

back = nullptr;

}

};