[Data Structure]연결 리스트 발전편(Linked List Advanced)

순환 연결 리스트(Circular Linked List) - 마지막 노드가 첫번째 노드를 가리키는 형태의 연결 리스트. - 위의 그림과 같은 구조를 생각하실 수 있을 겁니다. 그런데, dummy 노드가 있는 형태에 익숙하시다면, 위 구조물은 오히려 다루기 어려우실 수 있습니다.

그래서 생각한게 tail 포인터 입니다. 아래와 같은 방식으로 구현하면 tail포인터는 마지막 노드를 dummy 노드로 사용하는 것을 생각하실 수 있습니다. typedef struct { int len; Node *tail; } LinkedList; 양방향 연결 리스트(Double Linked List) - 앞선 연결 리스트의 구현방식에서 next포인터가 있어 다음 노드를 가리켰습니다.

그런데, 그런 구현방식을 이용하면 이전 노드로 돌아가려면 다시 처음부터 탐색을 해야만 합니다. 따라서 prev포인터를 추가하면 다음과 같습니다. typedef struct _node { Data item; struct _n...