구현 - 원형 싱글 링크드리스트

개인적으로는 책에 구현법이 나와있지않아서 조금 재미있었던 자료구조다.

역시 그림으로 그려서 이해하는게 편한다.

원형 링크드리스트는 제일 나중에 삽입한 노드가 처음 삽입한 노드를 가르키는 구조를 계속 유지하게끔 back을 관리해야 한다.

class CircleLinkedList

{

private:

SNode* back{};

public:

bool isEmpty() { return back == nullptr; }

SNode* begin() { return back; }

void push_back(int data)

{

SNode* newNode = new SNode(data);

newNode->_next = newNode;

if (back)

{

newNode->_next = back->_next;

back->_next = newNode;

}

back = newNode;

}

void pop_front()

{

if (!back->_next) return;

if (back->_next == back)

{

delete back;

back = nullptr;

return;

}

SNode* temp = back->_next;

back->_next = back->_next->_next;

delete temp;

}

SNode* next(SNode* point)

{

return point->_next;

}

SNode* advance(SNode* point, size_t times)

{

while (point && times--)

point = point->_next;

return point;

}

void clear()

{

if (!back) return;

SNode* del = back;

do

{

SNode* temp = del;

del = del->_next;

delete temp;

} while (del != back);

back = nullptr;

}

void display()

{

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

if (!back)

{

cout << "is empty now\n";

return;

}

SNode* n = back;

do

{

cout << n->_data << endl;

n = n->_next;

} 

while (n != back);

}

};