자료구조 · 알고리즘 기초집LESSON 05

연결 리스트: 노드로 데이터를 연결하는 원리

난이도초급 → 중급 입문

예상 시간40분

선수지식이전 강의

05강. 연결 리스트: 노드로 데이터를 연결하는 원리

1. 이번 강의에서 해결할 문제

배열 기반 목록만 사용하면 중간 원소 이동이 왜 필요한지, 연결 구조가 어떤 비용을 바꾸는지 이해하기 어렵습니다.

2. 학습 목표

3. 핵심 개념

단일 연결 리스트는 각 노드가 값과 다음 노드 참조를 가집니다. 머리 노드를 알고 있을 때 앞 삽입은 O(1)이지만, k번째 위치를 찾는 데 O(k)가 필요합니다. 특정 노드 참조를 이미 가진 경우 연결 변경은 빠르지만, 값을 찾아야 한다면 탐색 비용이 먼저 듭니다. Java LinkedList의 API를 직접 구현과 완전히 동일시하지 말고, 실제 애플리케이션에서는 접근 패턴과 메모리 지역성도 고려합니다.

4. 단계별 실습

1. 예제 파일 작성

실행 환경: 코드 편집기

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: 같은 이름의 파일이 있다면 덮어쓰기 전에 Git diff로 변경 범위를 확인합니다. 선택한 LTS JDK의 java -version과 javac -version이 모두 실행되어야 합니다.

대상 파일: src/SimpleLinkedRecords.java

src/SimpleLinkedRecords.java
public class SimpleLinkedRecords {
    record GameRecord(String playerId, int score) {}
    static final class Node {
        GameRecord value;
        Node next;
        Node(GameRecord value, Node next) { this.value = value; this.next = next; }
    }
    private Node head;

    void addFirst(GameRecord value) { head = new Node(value, head); }

    GameRecord find(String playerId) {
        for (Node node = head; node != null; node = node.next) {
            if (node.value.playerId().equals(playerId)) return node.value;
        }
        return null;
    }

    public static void main(String[] args) {
        SimpleLinkedRecords list = new SimpleLinkedRecords();
        list.addFirst(new GameRecord("P1", 800));
        list.addFirst(new GameRecord("P2", 1100));
        System.out.println(list.find("P1"));
    }
}

2. PowerShell에서 컴파일·실행

실행 환경: Windows PowerShell

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: src/SimpleLinkedRecords.java가 저장되었고 out 폴더에는 삭제해도 되는 컴파일 결과만 있는지 확인합니다.

대상: src/SimpleLinkedRecords.java와 out 아래 생성되는 class 파일

Windows PowerShell
Set-Location C:\dev\game-ranking-algorithms
New-Item -ItemType Directory -Force .\out | Out-Null
javac -Xlint:all -d .\out .\src\SimpleLinkedRecords.java
java -cp .\out SimpleLinkedRecords

예상 결과: GameRecord[playerId=P1, score=800]이 출력됩니다.

실행 시간은 PC의 CPU·메모리, JDK 버전, JVM 워밍업, 백그라운드 작업과 입력 분포에 따라 달라질 수 있습니다. 측정값은 같은 조건에서 여러 번 비교하고 Big-O 분석과 함께 해석합니다.

5. 코드와 알고리즘이 동작하는 이유

addFirst는 새 노드의 next를 기존 head로 연결하고 head만 바꾸므로 O(1)입니다. find는 최선 O(1), 평균·최악 O(n)이며 노드마다 값과 참조를 저장해 O(n) 공간을 사용합니다.

6. 자주 하는 실수와 해결법

7. 직접 실습

8. 이해 점검 질문 3개

9. 핵심 요약

MINI QUIZ