단일/이중 연결 리스트의 구조적 장단점

중간 삽입/삭제가 많은 문제에서는 배열보다 연결 리스트가 더 자연스러울 때가 있습니다. 연결 리스트는 값을 연속 메모리에 두지 않고, 노드끼리 링크로 이어 관리합니다. 그래서 값 이동 대신 링크 변경으로 수정할 수 있습니다.

단점도 분명합니다. 인덱스로 바로 접근할 수 없고, 링크를 잘못 바꾸면 버그가 크게 납니다. 아래에서는 단일/이중 연결 리스트를 어떤 상황에서 선택할지 기준으로 정리합니다.

핵심 개념: 단일/이중 연결 리스트

연결 리스트는 값을 옮기지 않고 링크만 바꿔 수정할 수 있다는 점이 핵심입니다. 아래 설명을 읽으면서 노트에 10 -> 20 -> 30 그림을 직접 그리고 링크가 어떻게 바뀌는지 표시해 보세요.

노드(node)는 값과 다음 위치 정보를 함께 담는 작은 상자입니다. 정확히는 데이터 필드와 링크 필드(next, 필요하면 prev)로 구성된 기본 단위입니다. 10 -> 20 -> 30에서 가운데 20 노드는 값 20과 다음 노드 주소를 들고 있습니다.

단일 연결 리스트는 각 노드가 다음 노드만 알고 있는 한 방향 체인입니다. 이 구조는 역방향 이동을 직접 지원하지 않아서 삭제 시 앞 노드를 우선 찾아야 합니다. 값 30을 지우려면 20을 찾아 20.next를 30.next로 바꾸는 순서로 처리합니다.

이중 연결 리스트는 앞뒤 이웃 링크를 모두 유지하는 구조입니다. prev와 next를 함께 관리해서 양방향 이동과 중간 삭제를 더 단순하게 만듭니다. 삭제 대상 노드를 이미 알고 있다면 prev.next와 next.prev 두 링크만 갱신해 바로 제거할 수 있습니다.

연결 리스트 선택이 운영에 미치는 영향

연결 리스트를 선택하는 이유는 중간 변경 비용 때문입니다.
노드 위치만 알고 있으면 배열처럼 대량 이동 없이 연결만 바꾸면 됩니다.

반면 탐색은 여전히 선형입니다.
연결 리스트는 수정 비용을 줄여야 하는 상황에서 특히 강점을 보입니다. 지금 문제에서 중간 수정 횟수와 임의 인덱스 조회 횟수를 각각 적어 비교해 보세요.

포인터 연결 디버깅 시나리오

여기서는 오답 -> 디버깅 -> 교정 -> 검증 흐름으로 추적해, 어디서 불변식이 깨지는지 단계별로 확인합니다.

단일 연결 리스트에서 삭제 과정을 짧게 따라가 보겠습니다.

초기 상태: 10 -> 20 -> 30 -> 40
작업: 값 30 삭제

head부터 순회하며 30의 이전 노드(20)를 찾습니다.
20.next를 30.next(=40)로 변경합니다.
연결 변경은 O(1)이지만, 이전 노드 탐색 과정이 O(N)입니다.

단일 연결 리스트 삽입/삭제

문제 의도: 단일 연결 리스트에서 삽입/삭제 기본 동작과 탐색 비용을 확인합니다.
입력 예시: 초기 노드 10 -> 20 -> 40, 중간에 30 삽입 후 20 삭제
출력 예시: 단계별 리스트 상태 출력 push_front는 맨 앞 삽입, remove_first는 처음 만난 값 1개 삭제를 뜻합니다.

main.cpp

#include <iostream>
#include <vector>
using namespace std;

struct SNode {
    int value;
    SNode* next;
    explicit SNode(int v) : value(v), next(nullptr) {}
};

class SinglyList {
public:
    SNode* head = nullptr;

    void pushFront(int value) {
        SNode* node = new SNode(value);
        node->next = head;
        head = node;
    }

    bool removeFirst(int target) {
        SNode* prev = nullptr;
        SNode* cur = head;
        while (cur) {
            if (cur->value == target) {
                if (!prev) head = cur->next;
                else prev->next = cur->next;
                delete cur;
                return true;
            }
            prev = cur;
            cur = cur->next;
        }
        return false;
    }

    vector<int> toList() const {
        vector<int> out;
        SNode* cur = head;
        while (cur) {
            out.push_back(cur->value);
            cur = cur->next;
        }
        return out;
    }
};

int main() {
    SinglyList lst;
    for (int x : {3, 2, 1}) lst.pushFront(x);
    for (int v : lst.toList()) cout << v << " ";
    cout << "\n";
    cout << boolalpha << lst.removeFirst(2) << "\n";
    for (int v : lst.toList()) cout << v << " ";
    cout << "\n";
    return 0;
}

Main.java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class SNode {
        int value;
        SNode next;
        SNode(int value) { this.value = value; }
    }

    static class SinglyList {
        SNode head;

        void pushFront(int value) {
            SNode node = new SNode(value);
            node.next = head;
            head = node;
        }

        boolean removeFirst(int target) {
            SNode prev = null;
            SNode cur = head;
            while (cur != null) {
                if (cur.value == target) {
                    if (prev == null) head = cur.next;
                    else prev.next = cur.next;
                    return true;
                }
                prev = cur;
                cur = cur.next;
            }
            return false;
        }

        List<Integer> toList() {
            List<Integer> out = new ArrayList<>();
            SNode cur = head;
            while (cur != null) {
                out.add(cur.value);
                cur = cur.next;
            }
            return out;
        }
    }

    public static void main(String[] args) {
        SinglyList lst = new SinglyList();
        for (int x : new int[]{3, 2, 1}) lst.pushFront(x);
        System.out.println(lst.toList());
        System.out.println(lst.removeFirst(2));
        System.out.println(lst.toList());
    }
}

main.py

class SNode:
    def __init__(self, value):
        self.value = value
        self.next = None

class SinglyList:
    def __init__(self):
        self.head = None

    def push_front(self, value):
        node = SNode(value)
        node.next = self.head
        self.head = node

    def remove_first(self, target):
        prev = None
        cur = self.head

        while cur:
            if cur.value == target:
                if prev is None:
                    self.head = cur.next
                else:
                    prev.next = cur.next
                return True
            prev = cur
            cur = cur.next
        return False

    def to_list(self):
        out = []
        cur = self.head
        while cur:
            out.append(cur.value)
            cur = cur.next
        return out

lst = SinglyList()
for x in [3, 2, 1]:
    lst.push_front(x)
print(lst.to_list())          # [1, 2, 3]
print(lst.remove_first(2))    # True
print(lst.to_list())          # [1, 3]

main.rs

struct SinglyList {
    data: Vec<i32>,
}

impl SinglyList {
    fn new() -> Self {
        Self { data: Vec::new() }
    }

    fn push_front(&mut self, value: i32) {
        self.data.insert(0, value);
    }

    fn remove_first(&mut self, target: i32) -> bool {
        let mut i = 0usize;
        while i < self.data.len() {
            if self.data[i] == target {
                self.data.remove(i);
                return true;
            }
            i += 1;
        }
        false
    }

    fn to_vec(&self) -> Vec<i32> {
        self.data.clone()
    }
}

fn main() {
    let mut lst = SinglyList::new();
    for x in [3, 2, 1] {
        lst.push_front(x);
    }
    println!("{:?}", lst.to_vec());
    println!("{}", lst.remove_first(2));
    println!("{:?}", lst.to_vec());
}

연결 리스트 구조 동작 인덱스 끝점 확인

앞쪽 삽입은 포인터 한 번 연결로 끝나므로 O(1)입니다.
삭제는 대상 노드를 찾는 과정이 필요해 O(N)입니다.
단일 리스트는 이전 노드를 모르면 역방향 처리나 임의 노드 삭제가 불편합니다.

평균 시간복잡도: 탐색/삭제 O(N)
최악 시간복잡도: 탐색/삭제 O(N)
공간복잡도: O(N)

이중 연결 리스트 양방향 삭제

문제 의도: prev/next를 모두 가진 구조에서 삭제가 어떻게 단순해지는지 비교합니다.
입력 예시: 초기 리스트 [10, 20, 30, 40], 삭제 값 30
출력 예시: [10, 20, 40]

main.cpp

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> dl = {10, 20, 30, 40};
    for (auto it = dl.begin(); it != dl.end(); ++it) {
        if (*it == 30) {
            dl.erase(it);
            break;
        }
    }
    for (int x : dl) cout << x << " ";
    cout << "\n";
    return 0;
}

Main.java

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<Integer> dl = new LinkedList<>();
        dl.add(10);
        dl.add(20);
        dl.add(30);
        dl.add(40);

        dl.remove(Integer.valueOf(30));
        System.out.println(dl); // [10, 20, 40]
    }
}

main.py

class DNode:
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None

class DoublyList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, value):
        node = DNode(value)
        if self.tail is None:
            self.head = self.tail = node
            return
        node.prev = self.tail
        self.tail.next = node
        self.tail = node

    def remove_node(self, node):
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next

        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev

    def find(self, target):
        cur = self.head
        while cur:
            if cur.value == target:
                return cur
            cur = cur.next
        return None

    def to_list(self):
        out = []
        cur = self.head
        while cur:
            out.append(cur.value)
            cur = cur.next
        return out

dl = DoublyList()
for x in [10, 20, 30, 40]:
    dl.append(x)
node = dl.find(30)
dl.remove_node(node)
print(dl.to_list())  # [10, 20, 40]

main.rs

use std::collections::LinkedList;

fn main() {
    let mut dl: LinkedList<i32> = LinkedList::new();
    for x in [10, 20, 30, 40] {
        dl.push_back(x);
    }

    let mut filtered: LinkedList<i32> = LinkedList::new();
    for x in dl {
        if x != 30 {
            filtered.push_back(x);
        }
    }
    println!("{:?}", filtered); // [10, 20, 40]
}

연결 리스트 구조 동작 포인터 흐름 추적

이중 리스트는 노드를 이미 알고 있을 때 삭제가 O(1)입니다.
양방향 포인터 덕분에 앞뒤 연결을 동시에 갱신할 수 있습니다.
대신 prev/next를 모두 관리해야 하므로 실수 가능성이 늘어납니다.

평균 시간복잡도: 탐색 O(N), 노드 삭제 O(1)
최악 시간복잡도: 탐색 O(N)
공간복잡도: O(N)

배열 참조 구현으로 삭제 결과 검증

문제 의도: 연결 리스트 삭제 코드를 디버깅할 때, 기대 결과를 빠르게 만드는 참조 코드를 준비합니다.
입력 예시: values=[10,20,30,20,40], target=20
출력 예시: [10,30,40]

연결 리스트 코드는 포인터 버그가 나기 쉽습니다. 그래서 우선 쉬운 배열 코드로 정답 형태를 만들고, 연결 리스트 결과와 비교하면 디버깅이 빨라집니다.

main.cpp

#include <iostream>
#include <vector>
using namespace std;

vector<int> removeValueReference(const vector<int>& values, int target) {
    vector<int> out;
    for (int v : values) {
        if (v != target) out.push_back(v);
    }
    return out;
}

int main() {
    vector<int> ans = removeValueReference({10, 20, 30, 20, 40}, 20);
    for (int x : ans) cout << x << " ";
    cout << "\n";
    return 0;
}

Main.java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static List<Integer> removeValueReference(List<Integer> values, int target) {
        List<Integer> out = new ArrayList<>();
        for (int v : values) {
            if (v != target) out.add(v);
        }
        return out;
    }

    public static void main(String[] args) {
        List<Integer> ans = removeValueReference(List.of(10, 20, 30, 20, 40), 20);
        System.out.println(ans); // [10, 30, 40]
    }
}

main.py

def remove_value_reference(values, target):
    out = []
    for v in values:
        if v != target:
            out.append(v)
    return out

print(remove_value_reference([10, 20, 30, 20, 40], 20))  # [10, 30, 40]

main.rs

fn remove_value_reference(values: &[i32], target: i32) -> Vec<i32> {
    let mut out = Vec::new();
    for &v in values {
        if v != target {
            out.push(v);
        }
    }
    out
}

fn main() {
    let ans = remove_value_reference(&[10, 20, 30, 20, 40], 20);
    println!("{:?}", ans); // [10, 30, 40]
}