더블 링크드리스트(Doubly Linked List) 개념과 구현

더블 링크드리스트란?

링크드리스트의 탐색 기능을 개선한 자료구조이다. 링크드리스트는 노드를 찾으려면 헤드에서 테일 방향으로만 탐색할 수 있었는데 더블 링크드리스트는 양방향으로 탐색이 가능하다.

아래는 더블 링크드리스트의 노드 구조이다. 

더블 링크드리스트 노드

class Node 
{
    private Object data;
    private Node prevNode;
    private Node nextNode;
    
    public Node(Object newData)
    {
        this.data = newData;
        this.prevNode = null;
        this.nextNode = null;
    }
}

주요 연산

링크드리스트와 동일하며 이전 노드를 처리하기 위한 구현이 더 추가될 뿐이다.

노드 생성

Node CreateNode(Object newData)
{
    return new Node(newData);
}

newData를 전달받아 Node 객체를 생성하여 노드를 만든다.

노드 추가

더블 링크드리스트 구조

void AppendNode(Node newNode)
{
    if(head == null)
    {
        head = newNode;
    }
    else
    {
        tail = head;
        while(tail.nextNode != null)
        {
            tail = tail.nextNode;
        }
        tail.nextNode = newNode;
        newNode.prevNode = tail;
    }
}

새로운 노드가 추가되면 테일을 탐색 후 테일의 nextNode를 추가된 노드(newNode)로 설정 후 추가된 노드(newNode)의 prevNode를 기존 테일로 설정한다.

이때 크기가 0인 리스트에 추가 한다면 새로운 노드(newNode)를 헤드로 설정한다.

노드 탐색

Node GetNodeAt(int location)
{
    Node current = head;

    while(current != null && (--location) >= 0)
    {
        current = current.nextNode;
    }

    return current;
}

노드 탐색 또한 링크드리스트와 동일하다. 헤드값부터 순회하며 찾고자 하는 노드를 반환한다.

노드 삭제

삭제시에는 nextNode, prevNode 둘 다 건들어야하기 때문에 총 4개의 포인터를 수정해야한다.

노드 삭제 과정

void RemoveNode(Node remove)
{
    if(head == remove)
    {
        head = remove.nextNode;
        if(head != null) head.prevNode = null;
        remove.prevNode = null;
        remove.nextNode = null;
    }
    else
    {
        Node temp = remove;

        remove.prevNode.nextNode = temp.nextNode;
        if(remove.nextNode != null) remove.nextNode.prevNode = temp.prevNode;

        remove.prevNode = null;
        remove.nextNode = null;
    }
}

• 헤드인 노드를 삭제할 경우 헤드를 다음노드로 옮긴 후 삭제처리
• 그 외의 경우는 삭제노드의 이전노드 nextNode를 삭제노드의 nextNode로 설정
  삭제노드의 다음노드 prevNode를 삭제노드의 prevNode로 설정
• 삭제할 노드의 prev, next null 처리

노드 삽입

삽입된 노드

void InsertAfter(Node current, Node newNode)
{
    newNode.nextNode = current.nextNode;
    newNode.prevNode = current;

    if(current.nextNode != null) current.nextNode.prevNode = newNode;
    current.nextNode = newNode;
}

삽입 시에는 새로운 노드의 prevNode는 앞 노드, nextNode는 뒷 노드를 가리킨다. 그리고 앞 노드의 nextNode와 뒷 노드의 prevNode는 새로운 노드를 가리킨다.

노드 개수 세기

int GetNodeCount()
{
    int count = 0;
    Node current = head;

    while(current != null)
    {
        current = current.nextNode;
        count++;
    }
    return count;
}

개수 세기는 head부터 순회라며 count 하려 count값을 반환한다.