연결리스트: 단일/이중/환형

단일 연결리스트

각 노드가 데이터와 다른 노드를 가리키는 Next포인터로 구성된 선형 자료구조이다.
단일 연결리스트는 시작 부분에 head가 있는 가장 기본형 연결리스트다. 추가/삭제 시 O(1), 검색 시 O(n)의 시간 복잡도를 가진다.

이중 연결리스트

이중 연결리스트는 양방향으로 이동할 수 있는 리스트로 이전 노드를 가리키는 Prev 포인터가 존재해서 데이터를 삭제할 때 삭제하고 끊어진 노드를 연결하기 위해 두 번 탐색해야 하는 단일 리스트보다 Prev를 통해 이전 노드의 탐색과 연결을 할 수 있어서 더 간편하지만 용량이 더 크다.

환형 연결 리스트

환형 연결리스트는 끝 노드가 head를 가리키는 첫 노드를 가리키는 형태의 구조를 가진 원형 노드이다. 환형 리스트의 장점은 일정 주기로 로그를 출력하는 작업과 같은 반복적인 순회에서 리스트의 끝을 체크할 필요없이 계속해서 노드를 반복할 수 있기에 이러한 반복 작업에서 이득을 볼 수 있다.