단일 연결리스트

5 min read

단일 연결리스트 (Singly Linked List)

각 노드가 다음 노드를 가리키는 포인터를 가진 자료구조

구조

+-------+    +-------+    +-------+    +-------+
| data  | -> | data  | -> | data  | -> | data  | -> null
| next  |    | next  |    | next  |    | next  |
+-------+    +-------+    +-------+    +-------+
  head                                    tail

노드 구조

class Node {
    int data;       // 저장할 데이터
    Node next;      // 다음 노드를 가리키는 포인터
 
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

핵심 연산

1. 삽입 (Insert)

맨 앞 삽입 - O(1)

Before:  head -> [A] -> [B] -> [C] -> null

Insert X at head:
1. newNode.next = head
2. head = newNode

After:   head -> [X] -> [A] -> [B] -> [C] -> null

void insertFirst(int data) {
    Node newNode = new Node(data);
    newNode.next = head;
    head = newNode;
}

맨 뒤 삽입 - O(n)

1. tail까지 순회
2. tail.next = newNode

// tail 포인터 유지 시 O(1) 가능

void insertLast(int data) {
    Node newNode = new Node(data);
    if (head == null) {
        head = newNode;
        return;
    }
    Node current = head;
    while (current.next != null) {
        current = current.next;
    }
    current.next = newNode;
}

중간 삽입 - O(n)

Before:  [A] -> [B] -> [C]
Insert X after B:

1. prev = B (탐색 필요)
2. newNode.next = prev.next
3. prev.next = newNode

After:   [A] -> [B] -> [X] -> [C]

2. 삭제 (Delete)

맨 앞 삭제 - O(1)

void deleteFirst() {
    if (head == null) return;
    head = head.next;
}

특정 값 삭제 - O(n)

void delete(int data) {
    if (head == null) return;
 
    // 첫 노드가 삭제 대상
    if (head.data == data) {
        head = head.next;
        return;
    }
 
    // 이전 노드를 추적하며 탐색
    Node prev = head;
    while (prev.next != null && prev.next.data != data) {
        prev = prev.next;
    }
 
    // 찾으면 연결 변경
    if (prev.next != null) {
        prev.next = prev.next.next;
    }
}

3. 탐색 (Search) - O(n)

Node search(int data) {
    Node current = head;
    while (current != null) {
        if (current.data == data) {
            return current;
        }
        current = current.next;
    }
    return null;  // 못 찾음
}

4. 순회 (Traverse) - O(n)

void printAll() {
    Node current = head;
    while (current != null) {
        System.out.print(current.data + " -> ");
        current = current.next;
    }
    System.out.println("null");
}

전체 구현

public class SinglyLinkedList {
    private Node head;
    private int size;
 
    public void addFirst(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
        size++;
    }
 
    public void addLast(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
        size++;
    }
 
    public void removeFirst() {
        if (head != null) {
            head = head.next;
            size--;
        }
    }
 
    public int get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        Node current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.data;
    }
 
    public int size() {
        return size;
    }
}

장단점

장점

  • 동적 크기 - 필요한 만큼만 메모리 사용
  • 앞쪽 삽입/삭제 O(1)
  • 메모리 재할당 불필요

단점

  • 인덱스 접근 O(n) - 순차 탐색 필요
  • 포인터 저장 공간 추가 필요
  • 캐시 지역성 낮음 (노드가 흩어져 있음)
  • 역방향 탐색 불가능

활용 예시

  1. 스택 구현 - 앞쪽에서만 삽입/삭제
  2. LIFO 큐 - 단방향 처리
  3. 다항식 표현 - 각 항을 노드로
  4. 희소 행렬 - 0이 아닌 값만 저장

면접 빈출 문제

1. 연결리스트 뒤집기

Node reverse(Node head) {
    Node prev = null;
    Node current = head;
 
    while (current != null) {
        Node next = current.next;  // 다음 노드 저장
        current.next = prev;       // 방향 뒤집기
        prev = current;            // prev 전진
        current = next;            // current 전진
    }
 
    return prev;  // 새로운 head
}

2. 사이클 탐지 (Floyd’s Algorithm)

boolean hasCycle(Node head) {
    Node slow = head;
    Node fast = head;
 
    while (fast != null && fast.next != null) {
        slow = slow.next;          // 1칸 이동
        fast = fast.next.next;     // 2칸 이동
 
        if (slow == fast) {
            return true;  // 사이클 존재
        }
    }
 
    return false;
}

3. 중간 노드 찾기

Node findMiddle(Node head) {
    Node slow = head;
    Node fast = head;
 
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
 
    return slow;  // slow가 중간에 위치
}

면접 포인트

  1. 배열 vs 연결리스트 차이점은?

    • 메모리 구조, 접근 방식, 삽입/삭제 효율성

  2. 연결리스트의 시간복잡도는?

    • 접근: O(n), 삽입/삭제: O(1) (위치를 알 때)

  3. 언제 연결리스트를 사용하는가?

    • 잦은 삽입/삭제, 크기 예측 불가, 앞쪽 작업 많을 때

Backlinks