들어가기 전에
원형 연결 리스트에 대해 살펴보도록 하겠습니다.
학습 목표
원형 연결 리스트를 이해하고 원형 연결 리스트인지 확인하는 방법을 설명할 수 있습니다.
핵심 단어
- 원형 연결 리스트
- 시간 복잡도
원형 연결 리스트
원형 연결 리스트는 마지막 next 포인터가 연결 리스트의 노드를 가리키는 연결 리스트입니다.
원형 연결 리스트의 마지막 next 포인터가 head를 가리키는지 확인하는 방법은 다음과 같습니다.
- head에서 시작하여 t==null이 될 때까지 반복한다면, 시간복잡도는 O(n)O(n) 입니다.
- tail 포인터를 사용할 경우, 시간복잡도는 O(1)O(1) 입니다.
마지막 next 포인터가 임의의 노드를 가리킨다면 확인하는 방법은 다음과 같습니다.
- tail에서 시작하여 tail 포인터가 다시 나타나는지 확인합니다. 시간복잡도는 O(n)O(n) 입니다.
- 임시 포인터 2개를 사용하여 시작점을 잡고 currentSize만큼 떨어진 노드까지 확인한 후 시작점을 다음으로 옮겨 같은 노드가 나타날 때까지 반복합니다. 시간복잡도는 O(n^2)O(n2) 입니다.
연결 리스트를 원형으로 연결할 때의 장점
원형 연결리스트는 사실 기존의 연결리스트에서 tail부분에 head를 연결해놓았을 뿐인 자료구조입니다.
이런 단순 구현이 가질수 있는 장점을 예시로 들어보겠습니다.
백그라운드에서 여러 log들을 1초마다 하나씩 반복적으로 출력하는 기능을 구현하고자 합니다.
다만 개발자는 log가 언제 몇개씩 관리해야하는지 알지 못합니다.
따라서 개발자는 log의 추가 및 삭제를 제공하는 API를 만들고, 실제 log 들을 연결리스트로 관리하여 순회하고자 합니다.
생각해보기
1) 원형 연결 리스트는 어떨 때 사용할까요?
나의 생각 : 음... 잘모르겠다..
출처 : https://www.boostcourse.org/cs204/lecture/625950?isDesc=false 네이버커넥트재단