2-5) 이중 연결 리스트, 원형 연결 리스트

 

아래 내용은 부스트코스 <자바로 구현하고 배우는 자료구조> 강의를 들으며 정리한 것입니다.

 

 

이중 연결 리스트

 

 

단일 연결 리스트에 previous 포인터를 추가한, 양방향 연결 리스트이다.

 

removeLast 메소드를 사용할 때, 시간 복잡도는 O(n)이다. 

단일 연결 리스트는 tail 포인터가 있더라도 새롭게 tail로 바꾸어 줄 이전의 노드를 바로 찾을 수 없기 때문에 current, previous를 이용해 앞에서부터 마지막에서 두 번째 노드까지 이동하는 과정이 필요하기 때문이다.

 

반면 이중 연결 리스트는 (삽입, 제거 시) 시간 복잡도가 O(1)인데,  tail 포인터가 가리키는 노드의 previous 포인터가 가리키는 노드(tail.previous)를 찾으면 되기 때문이다.

단, 노드를 추가하는 과정에서 next 포인터와 함께 previous 포인터를 업데이트 하는 작업을 추가로 필요로하기 때문에 구현이 조금 더 복잡해진다.

 

이중 연결 리스트에서 removeLast

E tmp = tail.data; 	//반환할 마지막 노드의 data 저장

tail.previous.next = null;
tail = tail.previous;

return tmp;

 

원형 연결 리스트

원형 연결 리스트의 구조는 위와 같이 마지막 노드가 첫 번째 노드를 가리키게 하여 원형의 형태로 연결되어 있다.

 

원형 연결 리스트 확인 방법

1. 마지막 next 포인터가 처음의 node를 가리킬 경우

tail 포인터를 사용해 tail.next == head인지 확인 = O(1)

 

2. 마지막 next 포인터가 임의의 node를 가리킬 경우(완벽한 원형이 X)

tail부터 시작해 tail이 다시 나타나는 것을 확인 = O(n)

임시 포인터 두 개를 만들어 currentSize만큼 떨어진 노드까지 이동하여 다시 나타나는 지 확인 = O(n^2) - 한 개의 노드마다 n번 비교