자료구조 - 원형 연결리스트

앞서 우리가 구현한 연결 리스트의 마지막 노드는 NULL 을 가리켰다. 바로 이 마지막 노드가 첫 번째 노드를 가리키게 하면 이것이 바로 원형 연결리스트가 된다.

원형 연결리스트

 

 

원형 연결리스트에 노드를 머리에 추가한 모습

 

 

원형 연결리스트에 노드를 꼬리에 추가한 모습

 

위 사진처럼 노드를 머리에 추가하나 꼬리에 추가하나 두 연결리스트 모두 8→1→2 형태로 가리키기 때문에 

원형 연결리스트에서는 머리와 꼬리의 구분이 없다고도 볼 수 있다.

 

 

위의 그림상에서 꼬리에 노드를 추가하려면 head를 시작으로 리스트의 끝을 찾아가는 과정을 거쳐야만 한다.

 

 

하지만 여기서 tail 이라는 포인터 변수를 노드 끝을 가리키도록 하면 새로운 노드를 추가하기에 어려움이 없다.

tail 이라는 포인터 변수는 꼬리를 가리키고

tail → next 는 리스트에서 머리를 가리키게 된다.

 

 

다음 그림의 왼쪽 편은 새로운 노드가 생성되었지만 아직 리스트에 추가되지 않는 상황을 보이고

오른쪽 편은 새로운 노드가 리스트에 추가되어 tail 포인터 변수가 새 노드를 가리키고 있음을 보인다.

 

 

다음 그림은 4 라는 값을 가진 노드를 tail 이 가리키는 노드가 가리키는 노드, 즉 머리에 추가한 상황이다. 

 

 

다음 그림은 7 이라는 값을 가진 노드를 tail 이 가리키는 노드가 가리키는 노드, 즉 머리에 추가한 상황이다. 

 

 

다음 그림은 그림 05-8 에서 7이 저장된 노드를 꼬리에 추가한 상황이다.

 

 

다음 그림은 노드를 머리에 추가한 결과와 꼬리에 추가한 결과를 비교한 그림이다.