자바 LinkedList 완전 정복: 개념과 직접 구현하기

안녕하세요! 이번에는 자바 컬렉션 프레임워크의 또 다른 핵심 자료구조인 LinkedList에 대해 알아보겠습니다. ArrayList에 이어 LinkedList의 개념과 구현 방법, 그리고 두 자료구조의 차이점과 각각 어떤 상황에서 사용하면 좋은지 초보자도 쉽게 이해할 수 있도록 설명해드리겠습니다.

LinkedList란 무엇인가?

LinkedList는 각 노드(Node)가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조입니다. 각 노드는 데이터와 다음 노드를 가리키는 참조(포인터)로 구성되어 있습니다.

ArrayList와 LinkedList의 핵심 차이점

메모리 확보 방식

• ArrayList: 연속된 메모리 공간에 데이터를 저장하며, 공간이 부족하면 더 큰 배열을 생성하고 복사
• LinkedList: 필요할 때마다 개별 노드를 생성하여 연결하므로 메모리를 효율적으로 사용

데이터 접근 방식

• ArrayList: 인덱스를 통한 직접 접근이 가능하여 조회 속도가 빠름 (O(1))
• LinkedList: 첫 노드부터 순차적으로 탐색해야 하므로 조회 속도가 상대적으로 느림 (O(n))

데이터 변경 특성

• ArrayList: 중간에 데이터 삽입/삭제 시 요소들을 이동시켜야 하므로 성능이 저하됨
• LinkedList: 노드 간의 참조만 변경하면 되므로 중간 삽입/삭제가 빠름

간단히 정리하면, 검색이 많은 작업에는 ArrayList가, 삽입/삭제가 많은 작업에는 LinkedList가 더 적합합니다.

LinkedList의 기본 구조

LinkedList의 가장 기본적인 구성 요소는 **노드(Node)**입니다. 각 노드는 다음과 같은 구조를 가집니다:

public class Node {
    Object item;     // 데이터를 저장
    Node next;       // 다음 노드의 참조(주소)
    
    public Node(Object item) {
        this.item = item;
    }
}

이 노드들이 서로 연결되어 LinkedList를 형성합니다:

[Node A] -> [Node B] -> [Node C] -> null

LinkedList 직접 구현하기

1. 기본 구조 구현

가장 먼저 LinkedList의 기본 구조를 구현해봅시다:

public class MyLinkedListV1 {
    private Node first;  // 첫 번째 노드
    private int size = 0;  // 요소 개수
    
    // 기타 메서드들...
}

2. 데이터 추가 (마지막에 추가)

public void add(Object e) {
    Node newNode = new Node(e);
    if (first == null) {
        first = newNode;  // 리스트가 비어있으면 첫 노드로 설정
    } else {
        Node lastNode = getlastNode();  // 마지막 노드 찾기
        lastNode.next = newNode;  // 마지막 노드의 다음으로 새 노드 연결
    }
    size++;
}

private Node getlastNode() {
    Node x = first;
    while (x.next != null) {  // 다음 노드가 없을 때까지 진행
        x = x.next;
    }
    return x;
}

3. 특정 위치에 데이터 추가

public void add(int idx, Object e) {
    Node newNode = new Node(e);
    if (idx == 0) {
        // 첫 번째 위치에 추가할 경우
        newNode.next = first;
        first = newNode;
    } else {
        // 중간이나 끝에 추가할 경우
        Node prevNode = getNode(idx - 1);  // 이전 노드 찾기
        newNode.next = prevNode.next;  // 새 노드의 다음을 이전 노드의 다음으로 설정
        prevNode.next = newNode;  // 이전 노드의 다음을 새 노드로 설정
    }
    size++;
}

4. 데이터 조회

public Object get(int idx) {
    Node x = getNode(idx);
    return x.item;
}

private Node getNode(int idx) {
    Node x = first;
    for (int i = 0; i < idx; i++) {
        x = x.next;
    }
    return x;
}

5. 데이터 삭제

public Object remove(int idx) {
    Node removeNode = getNode(idx);
    Object removeItem = removeNode.item;
    
    if (idx == 0) {
        // 첫 번째 노드 삭제
        first = removeNode.next;
    } else {
        // 중간이나 마지막 노드 삭제
        Node prevNode = getNode(idx - 1);
        prevNode.next = removeNode.next;
    }
    
    // 삭제된 노드의 참조 정리
    removeNode.next = null;
    removeNode.item = null;
    
    size--;
    return removeItem;
}

제네릭을 적용한 LinkedList 구현

타입 안전성을 강화하기 위해 제네릭을 적용한 LinkedList를 구현해봅시다:

public class MyLinkedListV3<E> {
    private Node<E> first;
    private int size = 0;
    
    // Node 클래스도 제네릭으로 구현
    private static class Node<E> {
        E item;
        Node<E> next;
        
        public Node(E item) {
            this.item = item;
        }
    }
    
    // 다른 메서드들도 제네릭 타입으로 변환
    public void add(E e) { /* ... */ }
    public E get(int idx) { /* ... */ }
    public E remove(int idx) { /* ... */ }
    // ...
}

제네릭을 사용하면 컴파일 시점에 타입 안전성을 보장받을 수 있습니다:

// 제네릭 사용 예시
MyLinkedListV3<String> strList = new MyLinkedListV3<>();
strList.add("Hello");
String str = strList.get(0);  // 형변환 불필요

MyLinkedListV3<Integer> intList = new MyLinkedListV3<>();
intList.add(1);
Integer num = intList.get(0);  // 형변환 불필요

LinkedList 연산의 시간 복잡도

LinkedList의 주요 연산별 시간 복잡도는 다음과 같습니다:

• get(index): O(n) - 처음부터 순차적으로 탐색
• add(element) (끝에 추가): O(n) - 마지막 노드를 찾아야 함
• add(0, element) (맨 앞에 추가): O(1) - 첫 노드 참조만 변경
• add(index, element) (중간에 삽입): O(n) - 해당 위치까지 탐색 필요
• remove(0) (맨 앞 삭제): O(1) - 첫 노드 참조만 변경
• remove(index) (중간/끝 삭제): O(n) - 해당 위치까지 탐색 필요

ArrayList vs LinkedList: 언제 무엇을 사용할까?

ArrayList가 유리한 경우

1. 빈번한 조회 작업: 인덱스로 직접 접근할 수 있어 조회가 O(1)로 매우 빠름
2. 순차적 접근: 메모리 지역성(locality) 원리로 인해 캐시 효율이 좋음
3. 크기 변화가 적은 경우: 크기 변경이 적다면 재할당 비용이 발생하지 않음

LinkedList가 유리한 경우

1. 빈번한 삽입/삭제 작업: 특히 리스트의 시작이나 중간에 자주 삽입/삭제하는 경우
2. 크기 예측이 어려운 경우: 동적으로 노드만 추가하므로 메모리 효율적
3. 큐나 스택처럼 양 끝에서의 작업이 많은 경우: 양방향 LinkedList는 이런 작업에 O(1) 성능

실전 활용 예시

LinkedList를 실제로 활용하는 예시를 살펴보겠습니다:

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        // 문자열을 저장하는 LinkedList 생성
        LinkedList<String> names = new LinkedList<>();
        
        // 요소 추가
        names.add("Alice");
        names.add("Bob");
        names.add("Charlie");
        
        // 맨 앞과 맨 뒤에 요소 추가 (LinkedList 전용 메서드)
        names.addFirst("David");
        names.addLast("Emily");
        
        System.out.println("LinkedList: " + names);
        
        // 첫 번째와 마지막 요소 조회
        System.out.println("First: " + names.getFirst());
        System.out.println("Last: " + names.getLast());
        
        // 요소 삭제
        names.removeFirst();
        names.removeLast();
        
        // 반복문을 통한 모든 요소 출력
        System.out.println("이름 목록:");
        for (String name : names) {
            System.out.println("- " + name);
        }
        
        // LinkedList를 스택처럼 사용
        LinkedList<Integer> stack = new LinkedList<>();
        stack.push(1);  // addFirst()와 동일
        stack.push(2);
        stack.push(3);
        
        System.out.println("스택에서 꺼낸 항목: " + stack.pop());  // 3
        
        // LinkedList를 큐처럼 사용
        LinkedList<Integer> queue = new LinkedList<>();
        queue.offer(1);  // add()와 동일
        queue.offer(2);
        queue.offer(3);
        
        System.out.println("큐에서 꺼낸 항목: " + queue.poll());  // 1
    }
}

요약 및 결론

LinkedList는 노드들이 서로 연결된 형태로 데이터를 저장하는 자료구조입니다. ArrayList와 달리 메모리 상에 연속적으로 저장되지 않고, 필요할 때마다 노드를 생성하여 연결합니다.

LinkedList의 주요 특징:

1. 각 노드는 데이터와 다음 노드를 가리키는 참조로 구성됨
2. 중간 삽입/삭제가 빠름 (O(1)) - 참조만 변경하면 됨
3. 조회가 상대적으로 느림 (O(n)) - 처음부터 순차적으로 탐색해야 함
4. 메모리 사용이 효율적 - 필요할 때만 노드를 생성

LinkedList는 삽입/삭제가 빈번한 작업, 크기를 예측하기 어려운 경우, 또는 큐나 스택과 같은 자료구조를 구현할 때 적합합니다. 반면, 조회 작업이 많거나 인덱스 기반 접근이 필요한 경우에는 ArrayList가 더 적합합니다.

자료구조의 선택은 프로그램의 요구사항과 데이터 사용 패턴에 따라 달라질 수 있으므로, 각 자료구조의 장단점을 이해하고 적절한 상황에 맞는 자료구조를 선택하는 것이 중요합니다.