이중 연결 리스트

들어가기 전에

단일 연결 리스트에 previous 포인터를 추가한 이중 연결 리스트에 대해 살펴보도록 하겠습니다.

 

학습 목표

이중 연결 리스트를 이해하고 장단점을 설명할 수 있습니다.

 

핵심 단어

• 이중 연결 리스트
• 시간 복잡도

이중 연결 리스트

 

 

 

이중 연결 리스트는 단일 연결 리스트에 바로 전의 노드를 가리키는 previous 포인터를 추가한 연결 리스트입니다.

 

removeLast 메소드를 사용할 때, 단일 연결 리스트는 tail 포인터가 있더라도  O(n)O(n) 의 시간 복잡도로 모든 노드를 한 번씩 거쳐야 한다는 단점이 있었습니다. 하지만 이중 연결 리스트는 tail 포인터가 가리키는 노드에서 previous 포인터가 가리키는 노드를 찾으면 되기 때문에 시간 복잡도가  O(1)O(1) 이 됩니다.

 

이중 연결 리스트의 단점은 previous 포인터가 추가되기 때문에 노드를 추가하는 과정이 더 복잡해진다는 것입니다.

 

---

 

생각해보기

1) 이중 연결 리스트의 장단점은 무엇인가요?

 

나의 생각 : 

장점) removeLast()를 할 때 tail포인터가 가리키는 노드에서 previous포인터가 가리키는 노드를 찾으면 되기 때문에 시간 복잡도가 상수가 된다.

단점) previous 포인터가 추가되기 때문에 노드를 추가할 때 과정이 복잡해진다.

 

출처 : https://www.boostcourse.org/cs204/lecture/625949?isDesc=false 네이버커넥트재단