Doubly linked list (이중 연결 리스트)

특징

• node와 node가 서로 연결되어 있음
• 상기 이미지와 같이 Next Link Field와 Previous Link Field가 존재함
• node를 탐색하는 방향이 양쪽으로 가능함
• 단방향 연결 리스트는 다음 노드의 탐색만 가능했지만, 이중 연결 리스트는 앞뒤로 탐색이 가능함 -> 상황에 따라 탐색의 방향이 바뀌어야 하는 경우에 사용

노드 추가

• 새로운 노드 (25)를 기존의 노드 (20, 30)에 연결하는 경우
• • 25의 다음 노드로 30을 연결함
• • 30의 이전 노드로 25를 연결함
• • 20의 다음 노드로 25를 연결함
• • 25의 이전 노드로 20을 연결함

노드 제거

• 노드 (30)을 제거하는 경우
• • 삭제하려는 노드의 이전 노드 (20)를 찾음
• • 삭제하려는 노드 (30)를 찾음
• • 삭제하려는 노드의 다음 노드 (40)을 찾음
• • 30을 삭제함
• • 20의 다음 노드로 40을 지정함
• • 40의 이전 노드로 20을 지정함