Doubly Linked List

생활코딩: Data Structure (자료구조)
참고 사이트 : VISUALGO

소개

• doubly linked list의 핵심은 노드와 노드가 서로 연결되어 있다는 점
  • 아래 그림을 보면 linked list와는 다르게 노드가 이전 노드(previous)와 다음 노드(next)로 구성되어 있음

• 이것의 가장 큰 장점은 양방향으로 연결되어 있기 때문에 노드를 탐색하는 방향이 양쪽으로 가능하다는 것

장점

• 양방향 탐색의 가장 큰 장점은 특정 인덱스 위치의 엘리먼트를 가져올 때와 반복자를 이용해서 탐색할 때 드러남

인덱스의 데이터 가져오기

• 노드가 6개일 때 3번째 엘리먼트 이전은 처음부터 시작해서 next를 이용해서 탐색하고, 4번째 이후의 엘리먼트는 마지막 노드부터 previous를 이용해서 조회
  • 단순 연결 리스트가 최악의 경우 노드 전체를 탐색해야 했던 것에 비해서 양방향 연결 리스트는 탐색해야하는 엘리먼트가 반으로 줄어듬

노드 탐색하기

• 단방향 연결 리스트는 다음 노드의 탐색만 가능했던 것에 비해서 이중 연결 리스트의 경우 앞뒤로 탐색이 가능
  • 상황에 따라 탐색의 방향이 바뀌어야 하는 경우라면 이중 연결 리스트를 사용

단점

• 이전 노드를 지정하기 위한 변수를 하나 더 사용해야 하는데 이는 메모리를 더 많이 사용한다는 의미
  • 또 구현이 조금 더 복잡해진다는 단점도 있음
• 하지만 장점이 크기 때문에 현실에서 사용하는 연결 리스트는 대부분 이중 연결 리스트

노드의 추가

• 단순 연결 리스트와 거의 비슷
  • 중요한 차이점은 양방향으로 연결을 해야 한다는 점
• 새로운 노드(25)를 기존의 노드(20, 30)와 연결하는 방법

• 25의 다음 노드로 30을 연결

• 30의 이전 노드로 25를 연결

• 20의 다음 노드로 25를 지정

• 25의 이전 노드로 20을 지정

• 노드의 추가가 끝남

노드의 제거

• 노드를 제거하는 방법

• 삭제하려는 노드의 이전 노드(20)을 찾기

• 삭제하려는 노드(30) 찾기

• 삭제하려는 노드의 다음 노드(40)도 찾기

• 30을 삭제

• 20의 다음 노드로 40을 지정

• 40의 이전 노드로 20을 지정

• 삭제 완료