[자료구조 리스트] 이중 연결 리스트(Doubly Linked List)

  이중 연결 리스트(Doubly Linked List)는 각 노드가 두 개의 레퍼런스를 가지고 각각 이전 노드와 다음 노드를 가리키는 연결 리스트입니다. 각 노드에 2개의 레퍼런스를 가지고 각각 이전 노드와 다음 노드를 가리키어 양방향 탐색이 가능합니다. 이중 연결 리스트는 단순 연결 리스트의 단점을 보완하지만, 노드마다 추가로 1개의 레퍼런스를 저장해야 하는 단점을 가집니다.

  이중 연결 리스트에서 수행되는 삽입이나 삭제 연산은 각각 상수 개의 레퍼런스만을 갱신하므로 O(1) 시간에 수행된다. 탐색 연산은 단순 연결 리스트의 탐색과 같이 head 또는 tail로부터 노드들을 순차적으로 탐색해야 하므로 O(n) 시간이 걸립니다.

 

  이중 연결 리스트의 장단점

•   장점
  • 단순 연결 리스트와 달리, 양방향 탐색 가능
• 단점
  • 레퍼런스를 추가 저장하여 메모리를 추가로 필요로 함

 

  ※ "자바와 함께하는 자료구조의 이해"라는 책을 참고하여 쓴 게시글입니다. 책에는 없는 내용을 추가하여 작성된 부분이 있습니다. 문제가 되거나 부정확한 부분이 있다면 알려주시면 감사하겠습니다.

  ※ 책은 게시글보다 정확한 내용을 담고 있으며 코드, 그림, 예제를 이용하여 개념을 자세히 설명합니다.