[자료구조] 이중 연결리스트

Fekim·2022년 1월 10일

자료구조

목록 보기

3/7

이중 선형 연결리스트

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

노드 클래스

Node class

이전 노드를 가리키는 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();
    }
}