[자료구조] Doubly Linked List (연결 자료구조)

1. 이중 연결 리스트
2. 삽입, 삭제 연산
3. 코드


1. 이중 연결 리스트

단순 연결리스트(Singly Linked List) 는 선행 노드에 접근하기가 어렵다는 단점이 있다.
원형 연결리스트(Circular Linked List) 는 단순 연결리스트에 비하여 선행 노드에 접근하기는 쉬우나, 전체 리스트를 한바퀴 순회해야 한다.
위 연결리스트들은 모두 리스트의 링크 필드가 한 방향으로만 이어지게 되었기 때문에 선행 노드에 접근하기는 좀처럼 쉽지 않다.

이중 연결 리스트(Doubly Linked List) 는 양쪽 방향으로 각 노드에 접근할 수 있도록 구성한 리스트이다.
이중 연결 리스트의 노드 구조는 다음과 같다.

두 개의 링크 필드와 한 개의 데이터 필드로 구성되어 있다.

1
2
3
4
5
public class DblNode{
DblNode llink;
String data;
DblNode rlink;
}

2. 삽입, 삭제 연산

다음은 이중 연결 리스트에서 원소 삽입을 하는 알고리즘이다.

1
2
3
4
5
6
7
insertNode(Dl, pre, x)
new <- getNode();
new.data <- x;
new.rlink <- pre.rlink;
pre.rlink <- new;
new.llink <- pre;
new.rlink.llink <- new;


다음은 이중 연결 리스트에서 원소 삭제를 하는 알고리즘이다.

1
2
3
4
5
deleteNode(Dl, old)
old.llink.rlink <- old.rlink;
old.rlink.llink <- old.llink;
returnNode(old); // 삭제된 old 노드를 자유 공간 리스트에 반환
end deleteNode()


3. 코드

  • DblNode

https://github.com/dudri63/dataStructure/blob/master/DoublyLinkedList/DblList.java

  • DblList

https://github.com/dudri63/dataStructure/blob/master/DoublyLinkedList/DblList.java

  • Ex_dblList

https://github.com/dudri63/dataStructure/blob/master/DoublyLinkedList/DblList.java


Reference

  • 이지영, 『자바로 배우는 쉬운 자료 구조』. 서울: (주)한빛아카데미, 2013
Share