[자바스크립트] 이중 연결 리스트 (doubly Linked List) 클래스

이중 연결 리스트

단순 연결 리스트는 이전 글을 참고해주세요.

[자료구조] - [자바스크립트] LinkedList 연결 리스트 클래스

이중 연결 리스트란?

단순 연결 리스트는 아래와 같이 한 방향으로 연결되어 있어 특정 노드의 왼쪽 노드를 알 방법이 없습니다.

이를 보완해서 양쪽 방향을 가지는 연결 리스트를 이중 연결 리스트라고 합니다.

기존 노드가 '데이터'와 '다음 노드를 가리키는 포인터' 2개를 갖고있었다면

이중 연결 리스트의 노드는 '데이터'와 '다음 노드를 가리키는 포인터', '이전 노드를 가리키는 포인터' 이렇게 3개를 갖고 있어야 합니다.

이중 연결 리스트의 데이터 삽입

데이터들의 연결 관계를 삽입하고자 하는 데이터와 연결되도록 조정합니다.

아래와 같은 [1,3,5] 리스트에 [2] 를 삽입하여 [1,2,3,5] 리스트를 만들고자 한다면

1단계 [2]의 previous가 [1]을, [2]의 next가 [3]을 가리키도록 합니다.

2단계 [3]의 previous가 [2]를 가리키도록 합니다.

3단계 [1]의 next가 [2]를 가리키도록 합니다.

[1,2,3,5] 리스트 완성입니다.

이전 글에서 구현한 단순 연결 리스트에서 삽입 함수만 고쳐보겠습니다.

// 노드 중간 삽입
function insert(newElement, item) {
    var newNode = new Node(newElement); //새로운 노드 생성
    var current = this.find(item); // 삽입할 위치의 노드 찾기
    newNode.previous = current; // 찾은 노드를 새로운 노드가 previous로 가리키기
    newNode.next = current.next; // 찾은 노드의 next를 새로은 노드가 next로 가리키기
    current.next.previous = newNode; // 찾은 노드의 next 노드가 새로운 노드를 previous로 가리키도록 하기
    current.next = newNode; // 찾은 노드가 새로운 노드를 next로 가리키도록 하기
}

이중 연결 리스트의 데이터 삭제

데이터 자체를 삭제하는 개념이 아닌 데이터끼리 가리키는 곳(포인터)를 활용해서 아무도 가리키지 않게 만들어 삭제와 같은 효과를 줄 수 있습니다.(보통 가비지 콜렉션에 의해 데이터는 결국 삭제되는 것으로 알고있습니다.)

아래 그림과 같이 [1,3,5] 리스트에서 [3]을 삭제하여 [1,5] 리스트를 만들고 싶은 경우

1이 5를, 5가 1을 가리키면 됩니다.

아무도 3을 가리키지 않기 때문에 3에 접근할 수가 없어 의미가 없어진 3을 빼고 보면 아래와 같습니다.

[1,5] 리스트 완성입니다.

이전 글에서 구현한 단순 연결 리스트에서 삭제 함수만 고쳐보겠습니다.

// 노드 삭제
function remove(item) {
    var current = this.find(item); // 삭제할 노드 찾기
    current.next.previous = current.previous; // 삭제할 노드의 next 노드가 previous로 삭제할 노드의 previous를 가리키도록 하기
    current.previous.next = current.next; // 삭제할 노드의 previous 노드가 next로 삭제할 노드의 next 가리키도록 하기
    current.next = null; // 삭제할 노드의 연결 초기화
    current.previous = null; // 삭제할 노드의 연결 초기화
}