Java 자바 LinkedList 동작 원리와 사용법

LinkedList란 무엇인가?

LinkedList는 자바에서 유용하게 사용되는 자료구조 중 하나로, 연결 리스트 방식을 이용하여 데이터를 관리하는 클래스입니다. 배열의 구조와는 다르게 각 요소들이 노드로 연결되어 있으며, 데이터의 삽입과 삭제가 빈번한 상황에서 강력한 성능을 발휘합니다. 이 글에서는 LinkedList의 구조와 특성, 장단점, 사용 예제 등을 자세히 다루어, LinkedList를 제대로 이해하고 활용할 수 있도록 하겠습니다.

LinkedList는 자바의 java.util 패키지에 포함된 클래스로, 데이터 요소들이 노드 형태로 연결된 형태의 리스트입니다. 이 연결 리스트는 각 노드가 데이터와 다음 노드에 대한 참조를 가지고 있는 방식으로 이루어져 있으며, 이를 통해 리스트의 중간에 요소를 추가하거나 제거하는 작업이 효율적으로 이루어집니다.

자바의 LinkedList는 이중 연결 리스트(Doubly Linked List) 구조로 구현되어 있어, 각 노드가 앞뒤로 연결되어 있습니다. 따라서 리스트를 양방향으로 탐색하는 것이 가능하여 다양한 상황에서 효과적으로 사용할 수 있습니다.

주요 특징

• 이중 연결 리스트: 각 노드가 이전 노드와 다음 노드의 참조를 모두 가지므로 양방향 탐색이 가능합니다.
• 빠른 삽입 및 삭제: 리스트의 중간에서 요소를 추가하거나 제거하는 것이 효율적입니다. 이는 삽입 및 삭제가 기존 요소의 이동 없이 이루어지기 때문입니다.
• 순차 접근: 배열과 달리, 인덱스를 이용한 빠른 임의 접근(random access)은 지원하지 않으며, 따라서 특정 위치로 접근할 때는 순차 탐색이 필요합니다.

LinkedList의 내부 구조

LinkedList는 노드(Node) 라는 단위로 구성됩니다. 각 노드는 데이터와 다음 노드에 대한 참조(포인터), 그리고 이전 노드에 대한 참조를 가지고 있습니다. 이러한 구조는 리스트의 앞뒤로 요소를 추가하거나 제거할 때 성능적으로 유리한데, 이는 배열과 달리 요소를 이동시키지 않아도 되기 때문입니다.

동작 원리

• 노드 구성: 각 노드는 데이터를 저장하는 필드와, 이전 및 다음 노드를 가리키는 두 개의 포인터를 가집니다.
• 이중 연결: LinkedList는 양방향 탐색을 지원하기 위해 각 노드가 이전 노드와 다음 노드 모두를 참조하는 이중 연결 리스트로 구현되어 있습니다.
• 첫 번째와 마지막 노드 참조: LinkedList는 첫 번째 노드(헤드)와 마지막 노드(테일)를 참조하는 필드를 유지하여, 리스트의 앞과 뒤에서 요소를 빠르게 추가하거나 제거할 수 있습니다.

LinkedList<String> list = new LinkedList<>();
list.add("Apple");
list.add("Banana");
list.add("Cherry");

위 코드에서는 각 요소들이 연결된 노드로 리스트에 저장됩니다. 이때 LinkedList는 각 요소를 추가할 때마다 새로운 노드를 생성하여 연결하게 됩니다.

주요 메서드와 사용법

요소 추가 (add() 메서드)

LinkedList에 요소를 추가하는 가장 기본적인 메서드는 add()입니다. 이 메서드는 리스트의 끝에 새로운 요소를 추가하며, 시간 복잡도는 O(1)입니다.

LinkedList<Integer> numbers = new LinkedList<>();
numbers.add(1);
numbers.add(2);
numbers.add(3);

특정 위치에 요소 추가 (add(index, element) 메서드)

특정 위치에 요소를 추가할 수도 있습니다. 이 경우 해당 인덱스를 찾기 위해 순차 탐색이 필요하므로, 최악의 경우 시간 복잡도는 O(n)이 될 수 있습니다.

numbers.add(1, 10);  // 인덱스 1에 값 10을 추가

요소 접근 (get() 메서드)

get() 메서드는 특정 인덱스의 요소에 접근할 때 사용됩니다. 하지만 LinkedList는 배열과 달리 임의 접근이 불가능하므로, 특정 인덱스로 접근할 때는 순차적으로 탐색해야 하며 시간 복잡도는 O(n)입니다.

int number = numbers.get(1);  // 결과: 10

요소 제거 (remove() 메서드)

remove() 메서드는 특정 인덱스에 있는 요소를 제거하거나 특정 값을 가진 첫 번째 요소를 제거합니다. 특정 요소를 제거하는 시간 복잡도는 O(1)이지만, 특정 인덱스로 접근하는 데에는 순차 탐색이 필요하기 때문에 최악의 경우 O(n)이 될 수 있습니다.

numbers.remove(1);  // 인덱스 1의 요소(10)를 제거

첫 번째 및 마지막 요소 관리 (addFirst(), addLast(), removeFirst(), removeLast())

LinkedList는 이중 연결 리스트 구조를 활용하여 리스트의 앞과 뒤에서 요소를 쉽게 추가하거나 제거할 수 있습니다.

numbers.addFirst(0);  // 리스트의 맨 앞에 0 추가
numbers.addLast(4);   // 리스트의 맨 뒤에 4 추가

numbers.removeFirst(); // 첫 번째 요소 제거
numbers.removeLast();  // 마지막 요소 제거

LinkedList의 장단점

장점

1. 빠른 삽입 및 삭제: 리스트의 앞이나 중간에 요소를 추가하거나 제거하는 경우 배열보다 효율적입니다. 특히 리스트의 처음이나 끝에서 작업할 때는 O(1)의 시간 복잡도를 가지며 매우 빠릅니다.
2. 유연한 메모리 사용: LinkedList는 동적 노드 기반 구조이므로 배열처럼 초기 용량을 설정할 필요가 없으며, 요소가 추가될 때마다 필요한 만큼의 메모리를 할당받습니다.

단점

1. 느린 요소 접근: 임의 접근이 불가능하여, 특정 인덱스의 요소에 접근하기 위해서는 순차적으로 노드를 탐색해야 합니다. 따라서 접근의 시간 복잡도는 O(n)입니다.
2. 메모리 오버헤드: 각 노드는 데이터와 함께 이전 및 다음 노드에 대한 참조를 저장해야 하므로, 배열에 비해 메모리 오버헤드가 큽니다.

효율적인 사용 방법

• 삽입/삭제가 빈번한 경우: 리스트의 중간이나 앞뒤에서 요소를 자주 추가하거나 제거해야 하는 경우 LinkedList가 더 적합합니다.
• 읽기 작업이 많은 경우 주의: 리스트 내 특정 요소를 자주 조회해야 한다면, LinkedList는 비효율적일 수 있습니다. 이러한 경우 ArrayList를 사용하는 것이 더 나은 선택입니다.

ArrayList vs LinkedList

LinkedList와 ArrayList는 둘 다 List 인터페이스를 구현하고 있지만, 내부 구조와 사용 목적에서 차이가 있습니다. 각 컬렉션의 특성에 따라 적절하게 선택하는 것이 중요합니다.

ArrayList는 읽기 작업이 많은 경우에 유리하고, LinkedList는 삽입/삭제 작업이 빈번한 경우에 유리합니다. 따라서 데이터의 접근 패턴과 작업 특성에 맞춰 적절한 리스트 타입을 선택하는 것이 중요합니다.

LinkedList 사용 예제

다음은 LinkedList를 사용하여 작업 목록을 관리하는 간단한 예제입니다.

import java.util.LinkedList;

public class TaskList {
    public static void main(String[] args) {
        LinkedList<String> tasks = new LinkedList<>();
        tasks.add("Complete project report");
        tasks.add("Attend team meeting");
        tasks.add("Reply to client emails");

        // 작업 목록 출력
        for (String task : tasks) {
            System.out.println(task);
        }

        // 작업 추가 및 제거
        tasks.addFirst("Prepare presentation");
        tasks.removeLast();

        // 업데이트된 작업 목록 출력
        System.out.println("\n업데이트된 작업 목록:");
        for (String task : tasks) {
            System.out.println(task);
        }
    }
}

위 코드에서 LinkedList는 작업 목록을 관리하는 데 사용되며, 작업을 동적으로 추가하고 제거하는 작업이 간단하게 이루어집니다.

결론

LinkedList는 삽입과 삭제 작업이 빈번한 상황에서 매우 유용한 자료구조입니다. 특히 리스트의 앞뒤에서 요소를 추가하거나 제거하는 작업이 많은 경우 LinkedList의 성능이 두드러집니다. 반면에, 요소의 접근이 빈번한 경우에는 ArrayList가 더 효율적일 수 있습니다.

LinkedList와 ArrayList의 차이점을 이해하고, 상황에 맞게 적절한 컬렉션을 선택하는 것은 자바 프로그래밍의 성능을 크게 향상시킬 수 있는 중요한 요소입니다. 이번 글에서 다룬 내용을 바탕으로 LinkedList를 효과적으로 활용하여 데이터를 관리할 수 있기를 바랍니다.