[Data Structure] 자료구조 LinkedList 효율적인 데이터 삽입과 삭제를 위한 연결 리스트

Java LinkedList : 효율적인 데이터 삽입과 삭제를 위한 연결 리스트

Java에서 LinkedList는 List 인터페이스를 구현한 또 다른 중요한 자료구조입니다. LinkedList는 이중 연결 리스트(doubly linked list)로 구현되어 있어, 삽입과 삭제가 빈번한 경우 특히 유용합니다.

LinkedList란?

LinkedList는 List 인터페이스와 Deque 인터페이스를 구현한 클래스입니다. 이 자료구조는 이중 연결 리스트를 기반으로 하며, 각 요소가 자신과 다음 요소의 참조(reference)를 포함한 노드(node)로 구성됩니다. 배열과 달리 요소들이 물리적으로 연속된 위치에 저장되지 않으며, 삽입 및 삭제 작업이 효율적으로 수행됩니다.

LinkedList의 주요 특징

• 빠른 삽입과 삭제 : 요소를 삽입하거나 삭제할 때, 배열과 달리 데이터를 이동시킬 필요가 없으므로 O(1)의 시간 복잡도를 가집니다.
• 느린 요소 접근 : 인덱스를 통해 요소에 접근할 때는 O(n)의 시간 복잡도를 가지며, 배열 기반의 ArrayList보다 느립니다.
• 이중 연결 리스트 구조 : 각 노드는 자신보다 앞에 있는 노드와 뒤에 있는 노드의 참조를 가지고 있어, 양방향으로 탐색할 수 있습니다.
• Deque 기능 : LinkedList는 Deque 인터페이스를 구현하여, 양쪽 끝에서의 삽입, 삭제가 가능합니다.
• 비연속적인 데이터 저장 : LinkedList는 데이터가 연속적으로 저장되지 않고, 각 요소가 노드로 연결되어 있습니다. 따라서 중간에 빈 공간이 없습니다.
• 내부 구현 : LinkedList는 내부적으로 각 요소를 가리키는 노드들로 이루어진 연결 리스트로 구현됩니다.
• 가변 크기 : ArrayList와 마찬가지로 LinkedList도 필요에 따라 크기를 동적으로 늘리거나 줄일 수 있습니다.
• 메모리 공간 : 각 노드는 데이터와 이전 노드와 다음 노드를 가리키는 두 개의 포인터를 저장해야 하므로 메모리 공간을 더 많이 차지할 수 있습니다.

LinkedList의 구조 및 동작 원리

LinkedList는 이중 연결 리스트로 구현됩니다. 각 노드는 데이터를 저장하는 필드와 이전 및 다음 노드를 가리키는 참조 필드로 구성됩니다. LinkedList는 첫 번째 노드인 head와 마지막 노드인 tail을 통해 리스트 전체를 관리합니다.

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        // LinkedList 생성
        LinkedList<String> animals = newLinkedList<>();

        // 요소 추가
        animals.add("Dog");
        animals.add("Cat");
        animals.add("Elephant");

        // 첫 번째 요소 접근
        System.out.println("첫 번째 동물: " + animals.get(0));  // 출력: Dog// 첫 번째 요소 제거
        animals.remove(0);

        // 마지막 요소 추가
        animals.addLast("Lion");

        // 전체 요소 출력for (String animal : animals) {
            System.out.println(animal);
        }
    }
}

LinkedList의 장단점

• 장점
  • 효율적인 삽입/삭제 : LinkedList는 리스트의 어느 위치에서든 삽입 및 삭제 작업이 O(1) 시간 복잡도로 매우 효율적입니다.
  • 메모리 재할당 불필요 : ArrayList와 달리 LinkedList는 요소를 추가할 때마다 배열의 크기를 재할당할 필요가 없으므로, 메모리 사용 측면에서 유리합니다.
  • Deque 인터페이스 지원 : LinkedList는 양쪽 끝에서의 삽입 및 삭제 작업이 모두 가능한 Deque로 사용될 수 있습니다.
• 단점
  • 느린 요소 접근 : LinkedList는 인덱스를 통해 요소를 접근할 때, 첫 번째 노드부터 순차적으로 탐색해야 하므로 O(n) 시간 복잡도를 가집니다.
  • 높은 메모리 사용 : 각 요소마다 데이터 외에 두 개의 참조 필드를 저장해야 하므로, ArrayList보다 메모리를 더 많이 사용합니다.
  • 캐시 효율성 저하 : 메모리 상에서 연속된 공간에 저장되지 않기 때문에, CPU 캐시 효율이 낮아질 수 있습니다.

LinkedList의 내부 동작 원리

LinkedList의 내부 동작을 이해하려면, 각 노드와 참조의 관계를 살펴봐야 합니다.

노드 구조

LinkedList의 각 요소는 Node 객체로 표현되며, 각 Node는 다음과 같은 필드를 가집니다:

• 데이터: 실제 저장되는 값.
• 이전 노드 참조 (previous): 앞에 있는 노드를 가리키는 참조.
• 다음 노드 참조 (next): 뒤에 있는 노드를 가리키는 참조.

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

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

삽입과 삭제

LinkedList에서의 삽입 및 삭제는 참조만 변경해 주면 되기 때문에 매우 효율적입니다. 예를 들어, 새로운 노드를 삽입할 때는 이전 노드의 next 필드와 다음 노드의 prev 필드를 수정하는 것만으로도 작업이 완료됩니다.

메모리 관리

LinkedList는 각 노드가 독립적으로 메모리에 할당되므로, 노드의 추가 및 삭제가 빈번한 경우에는 메모리 관리가 중요해집니다. 특히, 노드의 참조를 잘못 관리하면 NullPointerException과 같은 오류가 발생할 수 있습니다.

LinkedList vs ArrayList

LinkedList와 ArrayList는 모두 List 인터페이스를 구현하지만, 서로 다른 사용 목적을 가지고 있습니다.

• LinkedList: 삽입과 삭제가 빈번하고, 요소 접근이 적은 경우에 적합합니다. 예를 들어, 큐(queue)나 스택(stack)과 같은 자료구조로 사용할 수 있습니다.
• ArrayList: 요소 접근이 빈번하고, 삽입과 삭제가 드물거나, 중간 삽입/삭제가 없는 경우에 적합합니다.

단방향 연결 리스트(Singly Linked List)

단방향 연결 리스트는 각 노드가 다음 노드에 대한 참조만 가지는 구조입니다. 이 구조에서는 리스트의 끝으로만 이동할 수 있으며, 삽입/삭제가 간단하지만, 양방향 탐색이 불가능합니다.

public class SinglyLinkedList {
    private Node head;

    private static class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    // 노드 추가
    public void append(int data) {
        if (head == null) {
            head = newNode(data);
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode(data);
    }

    // 리스트 출력
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
    }
}

양방향 연결 리스트(Doubly Linked List)

양방향 연결 리스트는 각 노드가 이전 노드와 다음 노드에 대한 참조를 모두 가지는 구조입니다. 이 구조에서는 리스트의 양쪽 방향으로 이동이 가능하며, 삽입/삭제가 더 유연합니다.

public class DoublyLinkedList {
    private Node head;

    private static class Node {
        int data;
        Node next;
        Node prev;

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

    // 노드 추가
    public void append(int data) {
        if (head == null) {
            head = newNode(data);
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        Node newNode=newNode(data);
        current.next = newNode;
        newNode.prev = current;
    }

    // 리스트 출력
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
    }
}

결론

LinkedList는 데이터 삽입 및 삭제가 빈번한 경우에 매우 유용한 자료구조입니다. ArrayList와 달리 메모리 공간을 효율적으로 사용하지는 않지만, 노드 간의 참조만으로 리스트를 관리할 수 있어 성능 면에서 유리한 점이 많습니다. 상황에 따라 ArrayList와 LinkedList를 적절히 선택하는 것이 중요합니다. 특히, 데이터 구조의 특성과 예상 작업을 고려하여 올바른 자료구조를 선택하는 것이 성능 최적화의 핵심입니다.

Ref.

https://www.alphacodingskills.com/java/ds/java-linked-list.php

Java - Linked List - AlphaCodingSkills