[java] 자바의 이중 연결 리스트(Doubly LinkedList) 자료구조에 대해 알아보기

14 Dec 2023

java

자바에서는 링크드 리스트(linked list) 중 하나인 이중 연결 리스트(doubly linked list)라는 유용한 자료구조를 제공합니다. 이중 연결 리스트는 각 노드가 데이터와 이전 노드에 대한 참조(previous reference)와 다음 노드에 대한 참조(next reference)를 가지고 있는 자료구조입니다.

이중 연결 리스트의 구조

이중 연결 리스트의 각 노드는 데이터를 저장하는 부분과 이전 노드의 참조와 다음 노드의 참조를 저장하는 부분으로 구성됩니다. 다음은 자바에서의 이중 연결 리스트의 간단한 구조입니다.

class Node {
    int data;
    Node prev;
    Node next;
}

이중 연결 리스트의 장점

이중 연결 리스트는 데이터를 삽입하거나 삭제하는 작업이 빠르고 효율적입니다. 또한, 양쪽 방향으로의 순회(traversal)가 가능하여 앞쪽부터 뒤쪽 또는 반대로 뒤쪽부터 앞쪽으로도 간단하게 순회할 수 있는 장점을 가지고 있습니다.

예시: 자바에서의 이중 연결 리스트 활용

다음은 자바에서 이중 연결 리스트를 활용하여 데이터를 삽입하고 순회하는 간단한 예시 코드입니다.

public class DoublyLinkedList {
    class Node {
        int data;
        Node prev;
        Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    Node head, tail = null;

    public void insert(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = tail = newNode;
            head.prev = null;
            tail.next = null;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
            tail.next = null;
        }
    }

    public void display() {
        Node current = head;
        if (head == null) {
            System.out.println("List is empty");
            return;
        }
        System.out.println("Nodes of doubly linked list: ");
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
    }
}

마무리

이중 연결 리스트는 데이터를 순회하거나 삽입, 삭제하는 동작이 뛰어나며, 자바에서 구현하기에도 유용한 자료구조입니다. 많은 자료구조와 알고리즘에서 이중 연결 리스트가 활용되므로, 자바 개발자라면 이를 잘 숙지하고 활용할 수 있어야 합니다.