단순 연결리스트

개념

•

단순 연결리스트(Singly Linked List) 는 각 노드가 데이터(data) 와 다음 노드를 가리키는 참조(next) 를 갖는 선형 자료구조입니다.

•

배열과 달리 메모리가 연속일 필요가 없고, 노드들이 포인터(참조)로 연결됩니다.

•

보통 다음과 같은 참조를 유지합니다.

◦

head: 리스트의 첫 노드

◦

(선택) tail: 리스트의 마지막 노드(추가 연산 최적화)

장단점(시간 복잡도)

•

장점

◦

중간 삽입/삭제가 포인터 변경으로 가능(노드를 이미 찾았다는 전제에서 O(1))

◦

크기 변경이 자유로움(필요한 만큼 노드를 동적 생성)

•

단점

◦

인덱스 접근 불가 → k번째 접근은 순차 탐색 O(n)

◦

노드마다 참조를 저장하므로 추가 메모리 오버헤드 존재

자주 쓰는 연산의 평균적 비용(단순 연결리스트):

•

맨 앞 삽입(pushFront): O(1)

•

맨 앞 삭제(popFront): O(1)

•

탐색(search): O(n)

•

맨 뒤 삽입(pushBack): tail 이 있으면 O(1), 없으면 O(n)

Java로 직접 구현 예시

public class SinglyLinkedList<E> {
    private static class Node<E> {
        E data;
        Node<E> next;
        Node(E data) { this.data = data; }
    }

    private Node<E> head;
    private Node<E> tail; // 없애도 되지만, 있으면 맨 뒤 추가가 빨라짐
    private int size;

    public int size() { return size; }
    public boolean isEmpty() { return size == 0; }

    // 맨 앞에 삽입
    public void addFirst(E value) {
        Node<E> node = new Node<>(value);
        node.next = head;
        head = node;
        if (tail == null) tail = head;
        size++;
    }

    // 맨 뒤에 삽입
    public void addLast(E value) {
        Node<E> node = new Node<>(value);
        if (head == null) {
            head = tail = node;
        } else {
            tail.next = node;
            tail = node;
        }
        size++;
    }

    // 첫 원소 삭제 후 반환
    public E removeFirst() {
        if (head == null) throw new IllegalStateException("empty");
        E val = head.data;
        head = head.next;
        if (head == null) tail = null;
        size--;
        return val;
    }

    // value가 있는지 순차 탐색
    public boolean contains(E value) {
        for (Node<E> cur = head; cur != null; cur = cur.next) {
            if ((value == null && cur.data == null) ||
                (value != null && value.equals(cur.data))) return true;
        }
        return false;
    }
}
Java
복사

Mermaid로 “노드(포인터)” 표현하기

Mermaid에서는 연결리스트를 보통 방향 그래프 로 표현합니다.

•

노드: 사각형(또는 원하는 모양)

•

next 포인터: 화살표 -->

•

null: 종단 노드를 null 로 연결해서 끝을 표현

예시 1) 기본 연결

flowchart LR
    head((head)) --> n1["Node 1<br>data: 10"]
    n1 --> n2["Node 2<br>data: 20"]
    n2 --> n3["Node 3<br>data: 30"]
    n3 --> null((null))
Mermaid
복사

예시 2) head가 가리키는 “참조(변수)”까지 명시

flowchart LR
    headRef["head"] --> n1["data: A"]
    n1 -- next --> n2["data: B"]
    n2 -- next --> n3["data: C"]
    n3 -- next --> null((null))
Mermaid
복사

예시 3) tail을 함께 표현(선택)

flowchart LR
    headRef["head"] --> n1["data: 1"]
    n1 --> n2["data: 2"]
    n2 --> n3["data: 3"]
    tailRef["tail"] --> n3
    n3 --> null((null))
Mermaid
복사

팁:

•

노드 안에서 줄바꿈은 \n 대신 
 를 쓰면 안정적으로 렌더링됩니다.

•

연결 방향을 왼→오로 보려면 flowchart LR, 위→아래면 flowchart TD 를 사용합니다.