LinkedList

sungs·2025년 6월 9일

자바

목록 보기

11/95

📌 LinkedList란?

LinkedList는 데이터를 노드(Node)라는 단위로 연결해서 저장하는 연결형 자료구조. Java에서는 java.util.LinkedList 클래스로 제공되며, List, Deque, Queue 인터페이스를 구현한다.

✅ 자바의 LinkedList는 이중 연결 리스트(Doubly Linked List) 로 구현되어 있다.

✅ ArrayList vs LinkedList

비교 항목	ArrayList	LinkedList
내부 구조	배열	이중 연결 리스트
인덱스 접근	빠름 (O(1))	느림 (O(n))
삽입/삭제	느림 (O(n))	빠름 (O(1), 위치만 알면)
메모리 사용량	적음	많음 (노드마다 포인터 필요)

🔍 LinkedList 주요 메서드

LinkedList<String> list = new LinkedList<>();

list.add("Apple");        // 맨 뒤에 추가
list.addFirst("Banana");  // 맨 앞에 추가
list.addLast("Cherry");   // 맨 뒤에 추가

list.remove();            // 맨 앞 제거
list.removeLast();        // 맨 뒤 제거

String first = list.getFirst();  // 첫 요소 조회
String last = list.getLast();    // 마지막 요소 조회

✅ 사용 예시

public class Main {
    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        list.add("A");
        list.add("B");
        list.add("C");

        list.printList();
        // 출력: A <-> B <-> C <-> null
    }
}

내부 구조

class Node {
    String data;
    Node prev;
    Node next;

    Node(String data) {
        this.data = data;
    }
}

class MyLinkedList {
    private Node head;
    private Node tail;

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

    public void printList() {
        Node curr = head;
        while (curr != null) {
            System.out.print(curr.data + " <-> ");
            curr = curr.next;
        }
        System.out.println("null");
    }
}