→ 지금까지 배웠던 연결 리스트는 단순 연결 리스트이다.

• 모두 포인터를 이용하여 구현했다는 공통점이 있다.

• 원형 연결 리스트

  • 마지막 노드가 다시 첫 번째 노드와 연결되어 원형을 이룬다.
  • 일종의 루프 구조로 되어 있다.
  • 노드 사이의 연결이 단방향이다.

• 이중 연결 리스트

  • 노드 사이의 연결이 양방향으로 있다.

• 원형 연결 리스트와 이중 연결 리스트를 사용하면 구현이 쉬워지는 분야가 있다.

  • 단순 연결 리스트만 이용하면 구현이 어려운 분야가 있다.
  • 원형 연결 리스트는 운영체제에서 시간 할당 문제에 사용한다.
    • 리스트 순회를 루프 구조로 인해 계속 수행할 수 있도록 한다.
  • 이중 연결 리스트는 되돌리기 기능을 구현하는 데 유용하다.

1. 원형 연결 리스트

→ 원형 연결 리스트는 리스트의 마지막 노드가 첫 번째 노드와 연결된 단순 연결 리스트를 말한다.

• 노드 사이의 연결이 단방향이라는 점은 단순 연결 리스트와 동일하다.
  • 반면, 원형 구조를 지닌다는 점은 다르다.
  • 마지막 노드가 첫 번째 노드와 연결되어 있어야 한다.

노드의 구조