양방향 연결 리스트 (Doubly Linked Lists)

양방향 연결 리스트에서는 노드들이 앞/뒤로 연결되어 있다. 즉, 인접한 두 개의 노드들은 앞의 노드로부터 뒤의 노드가 연결되어 있을 뿐만 아니라, 뒤의 노드로부터 앞의 노드도 연결되어 있다.

단방향 연결 리스트에 비해 단점은 링크를 나타내기 위한 메모리 사용량이 늘어나고, 원소의 삽입/삭제 연산이 더욱 복잡해진다.

장점을 얘기하면 운영체제등에서는 리스트를 대상으로 앞/뒤로 왔다 갔다하는 작업을 빈번히 필요로 하는데 이에 적합하다.

동일한 연산을 일관되게 적용하기 위해서 맨 앞과 맨 뒤에 더미 노드를 추가할 수 있다. 특별한 경우로 처리해야 하는 것들이 줄어들어서 코드 양이 늘어도 코드의 난이도는 쉬워진다.

다음과 같은 연산을 풀어보기.

• 리스트 순회 (traversal)
• 원소 삽입 (insertion)
• 원소 삭제 (delection)
• 리스트 병합 (concatenation)