양뱡향 연결 리스트(1)
양뱡향 연결리스트는 따로 보면 복잡하지만, 앞에서 나온 내용들을 모두 이해하고나서, 그와 비교하면서 생각하면 생각보다 복잡하진 않다.
모델에 대해서 먼저 설명하겠다.
지금까지는 한쪽방향으로만 연결되어있었지만, 이제부터는 양뱡향으로 연결된 노드의 모델을 살펴 볼 것임.
필요에 따라서는 더미노드도 둘 수 있다. 또한 더미가 항상 head일 필요도 없고, 더미가 tail에 있을수도 있다.
거기에 양뱡향이, 원형일수도 있음. 양뱡향은 보편적으로는 이렇게 구현된다.
즉 양뱡향은, 노드가 양뱡향으로 연결되어있다는 점만 만족하면 부차적인 속성에는 열려있다.
양방향연결리스트는 노드 구조체에 차이가 생긴다. 지금까지는 next만 사용했지만, 이제는 prev라는 포인터도 사용할 것임.
왜 양뱡향으로 연결해서 사용하는가?
양뱡향연결은 포인터 연산이 두배로 는다. 포인터 연산에 익숙하다면… 이 특성이 전혀 여려울게 없다.
오히려 before같은 멤버를 다루지 않아도 되는 장점도 있다.
그럼 양뱡향이 가장 좋은 연결리스트 아닌가? 같은 의문이 들 수 있다.
하지만 보통의 어플리케이션에서, 한번 참조하고 넘어간 노드를 다시 참조할 일은 사실 많이 일어나지 않는 경우이다. 그래서 주어진 문제에서 항상 양뱡향 연결리스트가 최선의 자료구조가 아님.