링크드 리스트

Linked List

Linked List(연결 리스트)는 데이터를 노드(Node)라는 개별 단위로 저장하며, 각 노드는 다음 노드의 주소를 가리키는 포인터를 포함하고 있는 자료구조

배열과 달리 메모리 공간이 물리적으로 연속될 필요는 없지만, 노드 간의 연결을 통해 논리적인 연속성을 유지한다. 이 특성 덕분에 삽입과 삭제에 강한 성능을 가지며, 메모리를 보다 유연하게 사용할 수 있다.

Node 구조

Linked List는 기본적으로 여러 개의 Node로 구성

각 Node는 두 가지 요소를 포함

• value: 실제 저장하는 값
• next: 다음 노드를 가리키는 포인터

public class Node {
    int value;
    Node next;

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

 

논리적 연속성

배열은 메모리상에 데이터가 연속적으로 배치되지만, Linked List는 각 노드가 다음 노드의 주소를 기억함으로써 비연속적인 메모리 공간을 논리적으로 연결-> 메모리 단편화가 덜 발생, 동적 메모리 할당에 유리

단일 연결 리스트(Singly Linked List) 기본 구현

노드 연결 및 순회

Node first = new Node(1);
Node second = new Node(2);
Node third = new Node(3);

first.next = second;
second.next = third;

// 순회
Node current = first;
while (current != null) {
    System.out.println(current.value);
    current = current.next;
}

 

Linked List 클래스 구현 및 append 메서드

public class LinkedList {
    Node head;

    public LinkedList() {
        this.head = null;
    }

    public void append(int value) {
        Node newNode = new Node(value);
        if (head == null) {
            head = newNode;
        } else {
            Node ptr = head;
            while (ptr.next != null) {
                ptr = ptr.next;
            }
            ptr.next = newNode;
        }
    }
}

LinkedList list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);

 

tail 포인터를 사용한 효율 개선

public class LinkedList {
    Node head;
    Node tail;

    public LinkedList() {
        this.head = null;
        this.tail = null;
    }

    public void append(int value) {
        Node newNode = new Node(value);
        if (head == null) {
            head = tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
    }
}

 

Linked List의 종류

종류	설명
Singly Linked List	한 방향 연결만 가능. 구조가 단순
Doubly Linked List	앞뒤로 이동 가능. 탐색과 삭제에 유리
Circular Linked List	마지막 노드가 처음 노드를 가리켜 순환

 

이중 연결 리스트(Doubly Linked List)

구조

public class Node {
    int value;
    Node next;
    Node prev;

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

구현 예시

public class DoublyLinkedList {
    Node head;
    Node tail;

    public void append(int value) {
        Node newNode = new Node(value);
        if (head == null) {
            head = tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
    }

    public void print() {
        Node current = head;
        while (current != null) {
            System.out.println(current.value);
            current = current.next;
        }
    }
}

 

Java의 LinkedList 클래스 사용법 (Deque 기반)

Java는 자체적으로 양방향 연결 리스트(Doubly Linked List) 구조를 활용한 LinkedList 클래스를 제공

Deque 인터페이스를 통해 양쪽에서 삽입/삭제가 가능

선언 및 초기화

import java.util.Deque;
import java.util.LinkedList;

Deque<Integer> list = new LinkedList<>();

주요 메서드

list.addFirst(1);      // 앞에 삽입
list.addLast(2);       // 뒤에 삽입
list.removeFirst();    // 앞에서 삭제
list.removeLast();     // 뒤에서 삭제

 

ArrayList vs LinkedList

항목	ArrayList	LinkedList
내부 구조	배열 기반	이중 연결 리스트
삽입/삭제 (앞쪽)	느림 (O(n))	빠름 (O(1))
인덱스 접근	빠름 (O(1))	느림 (O(n))
순차 탐색	유사	유사

add(0, val) 또는 remove(0)처럼 앞쪽에서 자주 조작해야 한다면 LinkedList가 더 적합

활용 포인트

• 삽입/삭제가 빈번한 문제에서 유리 (특히 양쪽 끝 조작)
• Deque 활용 문제 (슬라이딩 윈도우, 회전 큐 등)에서 자주 등장
• 단일 연결 리스트 순회 문제는 구현형 코테에서 출제