2021.2.6 TIL : [자료구조] 양방향 연결리스트

오늘은 양방향 연결 리스트의 동작 원리와 구현 방법을 공부하고, 이를 통해 포인터 사용 능력을 업해보는 시간을 가졌다.

 

양방향 연결 리스트란 지난 2월 5일에 작성한 TIL에서 배운 단일 연결리스트와 달리, 포인터를 2개 사용하여 원소의 앞과 뒤를 모두 연결한 리스트를 의미한다. 따라서 이 리스트의 각 노드는 앞 순서의 노드에 대한 포인터, 뒤 순서의 노드에 대한 포인터를 데이터 값과 함께 가지고 있다. 이를 위해 노드의 자료형 자체에서 포인터 2개와 데이터 값까지 표현해 줄 필요가 있다.

 

특히, 수업에서는 오름차순으로 정리된 연결리스트를 만들었다. 이전까지는 for loop를 주로 사용했는데, 이 수업에서는 while loop를 더 많이 사용했다. for에 적응이 되고 나면 while을 쉽게 할 수 있을 거라고 배웠는데, 그런 것 같다.

 

이 양방향 연결 리스트를 작성할 때, 노드를 추가하거나 삭제하면서 그 순서에 주의해야 한다. 추가 할 때는 추가 대상 노드의 전 노드가 next 포인터를 대상 노드로 바꾸고, 대상 노드의 prev 포인터를 전 노드로 바꾸는 이 과정들은 순서가 있다. 전체 연결 리스트가 순서대로 이어지는 것이기 때문에 짧은 순간이더라도 노드를 추가/삭제하면서 이 순서가 틀어지면 오류가 뜨기 쉽다.

 

또한 가장 처음의 노드인 head와 가장 마지막의 노드인 tail을 정의할 때 역시, 단일 연결리스트에서 마지막 노드의 next 포인터를 NULL로 설정했던 것과 달리, 본인으로 설정하는 것이 좋다. 이는 우리가 코드 전반에서 노드가 NULL일 때 의 조건이 아닌, 노드가 tail일 때의 조건을 사용했기 때문이다. 

 

양방향 연결리스트는 리스트의 앞에서도, 뒤에서도 접근할 수 있다는 점에서 접근 용이성을 장점으로 가진다. 하지만 하나의 노드에서 포인터를 2개 사용하기 때문에 메모리 사용량이 늘어난다는 단점이 있다.