이중 선형 연결리스트

• 단순 연결 리스트에서 선행 노드에 접근하기가 어렵다는 점을 개선하여 원형 연결 리스트를 구성했지만, 원형 연결 리스트에서도 이전 노드에 접근하려면 전체 리스트를 한바퀴 순회해야 한다는 문제가 있다. 이런 문제를 개선하여 양쪽 방향으로 순회할 수 있도록 연결한 리스트가 이중 연결 리스트이다.

노드 클래스

• 이전 노드를 가리키는 prev, 다음 노드를 가리키는 next 노드를 멤버로 가지고 있는 점이 특징이다.

리스트 클래스

• head는 첫 노드이다.
• tail는 끝 노드이다.
• size는 노드의 갯수이다.

이중 연결리스트에서 노드 가져오기

public ListNode getNode(int index)
{
    if(index < size/2)  // (1)
    {
        ListNode node = head;
        for(int i = 0; i < index; i++)
        {
            node = node.next;
        }
        return node;
    }
    else                //(2)
    {
        ListNode node = tail;
        for(int i = size-1; i > index; i--)
        {
            node = node.prev;
        }
        return node;
    }
}

• (1) 찾으려는 노드의 index가 리스트의 중간보다 왼쪽인 경우. 순회할 node노드를 생성하여 첫 노드인 head포인터를 넣는다. 노드를 오른쪽으로 이동하여 index까지 순회시킨후 노드를 반환한다.
• (2) 찾으려는 노드의 index가 리스트의 중간보다 오른쪽인 경우. 순회할 node노드를 생성하여 마지막 노드인 tail포인터를 넣는다. 왼쪽으로 이동하며 index까지 순회시킨후 노드를 반환한다.

삽입 알고리즘

첫 노드 삽입 알고리즘

public void insertFirstNode(String data)
{
    ListNode newNode = new ListNode(data);
    
    if(head == null)        //(1)
    {
        head = newNode;
        tail = newNode;
    }
    else if(head != null)   //(2)
    {
        newNode.next = head;
        head.prev = newNode;
        head = newNode;
    }
    size++;
}

• (1) 리스트에 노드가 없는경우. head와 tail 둘 모두에 새로운 노드를 넣는다.
• (2) 리스트에 노드가 있는경우. 새로운 노드를 head 앞에 연결시킨후, 새로운 노드를 head로 놓는다.

끝 노드 삽입 알고리즘

public void insertLastNode(String data)
{
    if(size == 0)   //(1)
    {
        insertFirstNode(data);
    }
    else            //(2)
    {
        ListNode newNode = new ListNode(data);
        tail.next = newNode;
        newNode.prev = tail;
        tail = newNode;
        size++;
    }
}

• (1)size(노드의 갯수)가 0인 경우. 첫 노드 삽입 메소드를 호출한다.
• (2-1)tail노드 뒤에 newNode를 연결시킨다.
• (2-2)newNode의 앞에 tail노드를 연결시킨다.
• (2-3)newNode를 tail 노드로 만든다.

중간 노드 삽입 알고리즘

public void insertMiddleNode(int index, String data)
{
    if(index == 0)           //(1)
    {
        insertFirstNode(data);
    }
    else if(index == size)   //(2)
    {
        insertLastNode(data);
    }
    else                     //(3)
    {
        ListNode newNode = new ListNode(data);
        ListNode prevNode = getNode(index-1);
        ListNode nextNode = prevNode.next;
        
        // 새 노드의 전후 설정
        newNode.prev = prevNode;
        newNode.next = nextNode;
        
        // 이전 노드의 전후 설정
        prevNode.next = newNode;
        
        // 이후 노드의 전후 설정
        nextNode.prev = newNode;
        
        size++;
    }
}

• (1)index가 0인 경우. 첫 노드 삽입 메소드를 호출한다.
• (2)index가 size(노드의 갯수)와 같을 경우. 마지막 노드 삽입 메소드를 호출한다.
• (3)newNode와 이전, 다음 노드를 생성한다. 세 노드를 연결시킨다.

삭제 알고리즘

첫 노드 삭제 알고리즘

public String removeFirstNode()
{
    /* (1) */
    if(size == 0)
    {
        return null;
    }

    /* (2) */
    ListNode removeNode = head;
    head = null;
    head = removeNode.next;
    head.prev = null;
    size--;
    
    return removeNode.getData();
}

• (1)리스트가 비었다면, null을 반환한다.
• (2-1)삭제될 removeNode에 head를 넣어 생성한다.
• (2-2)원래 head를 날려버린다.
• (2-3)head에 removeNode의 오른쪽에 있던 노드를 넣는다.
• (2-4)head의 왼쪽에 null을 넣는다.

끝 노드 삭제 알고리즘

public String removeLastNode()
{
    if(size==0)
    {
        return null;
    }
    else
    {
        ListNode removeNode = tail;
        tail = null;
        tail = removeNode.prev;
        tail.next = null;
        size--;
        return removeNode.getData();
    }
}

중간 노드 삭제 알고리즘

public String removeMiddleNode(int index)
{
    if(size == 0)
        return null;
    
    if(index == 0)
        return removeFirstNode();
    else if(index == size-1)
        return removeLastNode();
    else
    {
        ListNode removeNode = getNode(index);
        ListNode prevNode = removeNode.prev;
        ListNode nextNode = removeNode.next;
        
        prevNode.next = nextNode;
        nextNode.prev = prevNode;
        size--;
        return removeNode.getData();
    }
}

참고문헌

• https://hongku.tistory.com/142
• [자바로 배우는 쉬운 자료구조], 한빛아카데미