[Java] 이중 연결리스트(Doubly-Linked-List) | 구현

Doubly-Linked-List (이중 링크드 리스트)란?

Fig. 1. 이중 연결리스트

이중 연결 리스트는 각 노드가 이전 노드와 다음 노드를 참조하는 연결 리스트입니다. 각 노드는 값을 가지고 있고, 두 개의 포인터를 가지고 있어서 이전 노드와 다음 노드를 참조할 수 있습니다.

이중 연결 리스트는 다음과 같은 특징을 가집니다:

• 양방향 탐색이 가능하다.
• 삽입, 삭제가 양쪽 끝에서 모두 가능하다.
• 배열과 달리 중간에 노드를 삽입, 삭제하기 쉽다.
• 단방향 연결 리스트보다 메모리 사용량이 더 많다.

이중 연결 리스트는 특히 큐(Queue)와 덱(Deque)에서 사용됩니다. 큐는 선입선출(FIFO) 구조이므로, 이전 노드와 다음 노드를 모두 참조할 수 있는 이중 연결 리스트가 적합합니다. 덱은 큐와 스택(Stack)의 기능을 모두 가지고 있으므로, 이중 연결 리스트를 기반으로 구현할 수 있습니다.

---

 

구현

위 코드에서는 제네릭 타입 T를 가진 이중 연결 리스트를 구현한 것입니다. 

public class DoublyLinkedList<T> {
    private Node head;
    private Node tail;
    private int size;

    private static class Node<T> {
        private T item;
        private Node<T> prev;
        private Node<T> next;

        public Node(T value) {
            this.item = value;
        }
    }

    public DoublyLinkedList() {
        head = null;
        tail = null;
        size = 0;
    }

 

DoublyLinkedList 클래스에는 head와 tail 변수가 있으며, 각 노드는 이전 노드와 다음 노드를 가리키는 prev와 next 변수를 가지고 있습니다. 노드는 Node 클래스로 정의되어 있으며, 이 클래스는 DoublyLinkedList 클래스 내부에 선언되어 있습니다.

 

 public void addFirst(T value) {
        Node<T> newNode = new Node<>(value);
        if (isEmpty()) {
            head = newNode;
            tail = newNode;
        } else {
            head.prev = newNode;
            newNode.next = head;
            head = newNode;
        }
        size++;
    }

 

public void addLast(T value) {
        Node<T> newNode = new Node<>(value);
        if (isEmpty()) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
        size++;
    }

 

addFirst(), addLast() 메소드에서는 새로운 노드를 생성하고, 리스트가 비어있는 경우와 그렇지 않은 경우를 나누어 처리합니다. 

 

위 코드는 head와 tail 변수를 사용하여 리스트의 시작과 끝을 O(1) 시간 내에 찾을 수 있습니다. 또한, 제네릭 타입 T를 사용하여 다양한 자료형의 데이터를 저장할 수 있습니다. 따라서, 이 코드는 가장 효율적인 이중 연결 리스트 구현 방법 중 하나입니다

---

연관 포스팅

2023.03.24 - [자바 JAVA] - [Java] 단일 링크드 리스트(Singly Linked-List) 간단하게 정의 및 구현 - 1

[Java] 단일 링크드 리스트(Singly Linked-List) 간단하게 정의 및 구현 - 1

2023.02.27 - [알고리즘 분석 및 데이터 구조] - 알고리즘 분석 | ADT 란 | 큐 Queues | List ADT

알고리즘 분석 | ADT 란 | 큐 Queues | List ADT

---