Doubly Linked List - 이중 연결 리스트

Doubly Linked List?

Doubly Linked List

- Linked List(연결리스트)에서 삽입과 삭제가 일어날 때, 좀 더 편리하게 이용하기 위한 자료구조

- 이전 Node를 가리키는 prev 포인터와 다음 Node를 가리키는 next 포인터를 가지고 있는게 핵심이다

 

구현 방법에는 참 여러가지가 있겠지만, 편리한 구현을 위해

작성자는 head와 tail을 dummy로 설정하여 구현하였다!

 

왜냐하면, 편하기 때문이다 ^8^

( 아닐수도 있어요... ㅎㅎ )

public class DoublyLinkedList {
    private class Node {
        private int val;
        private Node next;
        private Node prev;

        Node(final int val) {
            this.val = val;
            this.next = null;
            this.prev = null;
        }
    }

    private Node head;
    private Node tail;

    public DoublyLinkedList() {
        this.head = new Node(0);
        this.tail = new Node(0);

        head.next = tail;
        tail.prev = head;
    }
}

head와 tail을 dummy로 만들고 서로 이어주는게 핵심!!

삽입 과정

다음과 같은 그림에서 97이라는 Node를 4번째에 삽입하도록 하겠다!

1. 새로운 Node를 만들고

2. 97과 1번 Node에 서로 연결시켜주고

3. 88번 next Node를 97로 가리키고, 1과 다시 연결!

public void pushSequence(int num) {
        Node temp = findNextNode(num);
        if (temp == null) {
            pushBack(num);
        } else {
            Node node = new Node(num);

            node.prev = temp.prev;
            node.next = temp;

            if (temp.prev != null) temp.prev.next = node;
            temp.prev = node;
        }
    }

이 코드에서 temp는 위 그림에서 1번 Node와 알치한다!

 

* 만약, 뒤나 앞에다 삽입하고 싶다면?

1. 뒤에다 넣고 tail과 연결하고~

2. tail을 바꿔준다!

이런 느낌이지만~

다만, 제가 구현한건 dummy tail이라서 코드는 달라요!!

public void pushBack(int num) {
    Node node = new Node(num);

    node.prev = tail.prev;
    node.next = tail;

    tail.prev.next = node;
    tail.prev = node;
}

앞쪽 삽입도 구현하기 쉽겠죠?

public void pushFront(int num) {
    Node node = new Node(num);

    node.prev = head;
    node.next = head.next;

    head.next.prev = node;
    head.next = node;
}

삭제 과정

삭제는 정말 정말 쉬워요~!!

1. 지울 Node를 찾고~

2. 88의 next를 97로, 97의 prev를 45로~!

 public void deleteNode(final int num) {
        Node node = findNode(num);
        if (node == null) {
            throw new IllegalArgumentException("해당하는 원소가 없습니다.");
        }

        if (node.prev != null) node.prev.next = node.next;
        if (node.next != null) node.next.prev = node.prev;
    }

해당하는 숫자의 Node를 찾고, 서로 앞과 뒤를 연결해주면 된다!!

 

 

소스 코드

제가 직접 구현한 소스 코드와 Test 코드를 같이 첨부했어요!!

package datastructure;

public class DoublyLinkedList {
    private class Node {
        private int val;
        private Node next;
        private Node prev;

        Node(final int val) {
            this.val = val;
            this.next = null;
            this.prev = null;
        }
    }

    private Node head;
    private Node tail;

    public DoublyLinkedList() {
        this.head = new Node(0);
        this.tail = new Node(0);

        head.next = tail;
        tail.prev = head;
    }

    public void pushBack(int num) {
        Node node = new Node(num);

        node.prev = tail.prev;
        node.next = tail;

        tail.prev.next = node;
        tail.prev = node;
    }

    public void pushFront(int num) {
        Node node = new Node(num);

        node.prev = head;
        node.next = head.next;

        head.next.prev = node;
        head.next = node;
    }

    public void pushSequence(int num) {
        Node temp = findNextNode(num);
        Node node = new Node(num);

        node.prev = temp.prev;
        node.next = temp;

        if (temp.prev != null) temp.prev.next = node;
        temp.prev = node;
    }

    public void deleteNode(final int num) {
        Node node = findNode(num);
        if (node == null) {
            throw new IllegalArgumentException("해당하는 원소가 없습니다.");
        }

        if (node.prev != null) node.prev.next = node.next;
        if (node.next != null) node.next.prev = node.prev;
    }

    private Node findNode(final int num) {
        Node node = head.next;
        while (node.next != null) {
            if (node.val == num) {
                return node;
            }
            node = node.next;
        }
        return null;
    }

    private Node findNextNode(final int num) {
        Node node = head;
        while (node.next != null) {
            if (node.next.val > num) {
                return node.next;
            }
            node = node.next;
        }
        return node;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node node = head.next;
        while (node.next != null) {
            sb.append(node.val).append(' ');
            node = node.next;
        }
        return sb.toString();
    }
}

package datastructure;

import org.junit.jupiter.api.Test;

import static org.assertj.core.api.Assertions.assertThat;
import static org.junit.jupiter.api.Assertions.assertThrows;

class DoublyLinkedListTest {
    @Test
    void 제대로_뒤쪽에_삽입되는지_테스트() {
        /* Given */
        DoublyLinkedList doublyLinkedList = new DoublyLinkedList();
        /* When */
        doublyLinkedList.pushBack(3);
        doublyLinkedList.pushBack(4);
        doublyLinkedList.pushBack(5);
        doublyLinkedList.pushBack(6);
        /* Then */
        assertThat(doublyLinkedList.toString()).isEqualTo("3 4 5 6 ");
    }

    @Test
    void 제대로_앞쪽에_삽입되는지_테스트() {
        /* Given */
        DoublyLinkedList doublyLinkedList = new DoublyLinkedList();
        /* When */
        doublyLinkedList.pushFront(3);
        doublyLinkedList.pushFront(4);
        doublyLinkedList.pushFront(5);
        doublyLinkedList.pushFront(6);
        /* Then */
        assertThat(doublyLinkedList.toString()).isEqualTo("6 5 4 3 ");
    }

    @Test
    void 제대로_순서대로_삽입되는지_테스트() {
        /* Given */
        DoublyLinkedList doublyLinkedList = new DoublyLinkedList();
        /* When */
        doublyLinkedList.pushSequence(3);
        doublyLinkedList.pushSequence(2);
        doublyLinkedList.pushSequence(8);
        doublyLinkedList.pushSequence(1);
        /* Then */
        assertThat(doublyLinkedList.toString()).isEqualTo("1 2 3 8 ");
    }

    @Test
    void 삽입된_원소가_제대로_삭제되는지_테스트() {
        /* Given */
        DoublyLinkedList doublyLinkedList = new DoublyLinkedList();
        /* When */
        doublyLinkedList.pushSequence(3);
        doublyLinkedList.pushSequence(2);
        doublyLinkedList.pushSequence(8);
        doublyLinkedList.pushSequence(1);
        doublyLinkedList.deleteNode(1);
        /* Then */
        assertThat(doublyLinkedList.toString()).isEqualTo("2 3 8 ");
        assertThrows(IllegalArgumentException.class, () -> {
            doublyLinkedList.deleteNode(7);
        });
    }
}

결론

이중 연결 리스트는, 배열처럼 중간 삽입, 삭제는 시간이 정말 정말 느리다

하지만 단순 앞, 뒤 삽입은 빠른게 장점!!

메서드에 따른 시간복잡도를 정리하면서 마칠게요~!

• pushFront : O(1)
• pushBack : O(1)
• pushSequence : O(N)
• deleteNode : O(N)

Doubly Linked List