열혈 자료구조 - 5-1. 원형 연결 리스트(1)

단순 연결 리스트와 원형 연결 리스트

- 단순 연결 리스트의 마지막 노드는 NULL을 가르키지만 원형 연결 리스트는 마지막 노드가 첫 번째 노드(HEAD)를 가르킴

 

원형 연결 리스트의 노드 추가

- 머리(HEAD)에 추가하거나 꼬리(TAIL)에 추가할 수 있음

- 어디에 추가하든 내용은 같음

    -> HEAD가 가르키는 노드만 다름

    -> 메모리 모델을 볼 때 머리와 꼬리의 구분이 없음

 

원형 연결 리스트의 장점

- HEAD와 TAIL의 구분이 없다는 것이 장점의 이유가 됨

- HEAD와 TAIL의 포인터 변수를 각각 두지 않고 하나의 포인터 변수만 가지고 머리 또는 꼬리에 노드를 추가할 수 있음

- 위 장점을 장점을 살리기 위해서는 꼬리를 가르키는 TAIL 변수를 사용해야 함

    -> TAIL을 사용하는 원형 연결 리스트를 변형된 원형 연결 리스트라 함

- 노드를 추가할 때 꼬리에 추가하려하면 tail에 추가하고 머리에 추가하고 싶을 땐 tail->next에 추가