Quick Comparison
| 구조 | 접근 | 알고 있는 노드 삭제 | 앞뒤 삽입 | 메모리 |
|---|---|---|---|---|
| 배열·동적 배열 | O(1) | O(n) 이동 | 뒤 삽입 유리 | 연속 공간 |
| 연결 리스트 | O(n) | O(1) | 앞뒤 삽입 유리 | 노드별 참조 |
var list = new LinkedList<int>();
var node = list.AddLast(10);
list.AddAfter(node, 20);
list.Remove(node);중간 노드가 이미 손에 있고 삽입·삭제가 중심이면 연결 리스트를 검토합니다. index 접근과 캐시 친화적 순회는 배열·List<T>가 보통 더 낫습니다.
구조
연결 리스트는 값과 다음 노드의 참조를 가진 노드들이 이어진 구조입니다. 배열처럼 i번째 위치를 바로 계산할 수 없어서 임의 접근은 O(n)입니다.
[value | next] -> [value | next] -> [value | null]단방향 연결 리스트는 다음 노드만 알고, 양방향 연결 리스트는 이전 노드와 다음 노드를 모두 압니다.
class Node
{
public int Value;
public Node? Next;
}C++에서 raw pointer로 직접 구현하면 연결뿐 아니라 소유권도 관리해야 합니다. 노드를 지울 때는 다음 주소를 먼저 보존하고 head·tail을 갱신한 뒤 정확히 한 번 해제해야 합니다. 실제 제품 코드에서는 특별한 이유가 없다면 표준 container나 명확한 smart pointer 소유권을 우선합니다.
if (head != nullptr) {
Node* removed = head;
head = head->next;
if (head == nullptr) tail = nullptr;
delete removed;
}.NET의 LinkedList<T>는 양방향 연결 리스트입니다. LinkedListNode<T>가 어느 LinkedList<T>에 속하는지 유지하므로, AddBefore·AddAfter·Remove(node)는 그 리스트가 소유한 노드를 받아야 합니다. 값으로 Remove(value)를 호출하면 첫 일치 노드를 찾는 O(n) 비용이 먼저 듭니다.
삽입·삭제가 빠른 조건
연결 리스트의 삽입·삭제가 O(1)이라는 말은 삽입·삭제할 위치의 노드를 이미 알고 있을 때만 맞습니다. 위치를 찾기 위해 처음부터 순회해야 한다면 탐색 O(n)이 먼저 듭니다.
찾기 O(n) + 삭제 O(1) = 전체 O(n)그래서 코테에서는 연결 리스트 자체보다 스택, 큐, 덱처럼 목적이 뚜렷한 구조를 더 자주 씁니다.
선택 기준
| 상황 | 판단 |
|---|---|
| 인덱스 접근이 많음 | 배열 또는 List<T> |
| 앞뒤 삽입·삭제만 필요 | 큐, 덱 계열 검토 |
| 현재 노드 기준 삽입·삭제 | 연결 리스트 가능 |
| 캐시 효율과 단순 구현 중요 | 배열 쪽이 유리한 경우 많음 |
| 인터뷰형 노드 문제 | 직접 노드 구조 구현 가능 |
연결 리스트 문제는 포인터 연결을 끊고 다시 잇는 순서가 핵심입니다.
// current 다음 노드 삭제
if (current.Next != null)
{
current.Next = current.Next.Next;
}주의할 점
연결 리스트는 중간 삽입·삭제가 항상 빠른 자료구조가 아닙니다. 위치를 찾는 비용까지 포함하면 O(n)이 됩니다.
또 노드 참조를 잘못 갱신하면 일부 노드가 끊기거나 순환 구조가 생길 수 있습니다. 삭제 전후에는 head, tail, null 경계를 별도로 확인해야 합니다.
Raw pointer 구현에서는 memory leak, double delete, use-after-free도 함께 검사해야 합니다. 삭제한 노드를 가리키는 외부 pointer는 자동으로 무효 표시되지 않습니다.
한 리스트에서 제거한 LinkedListNode<T>는 다른 리스트에 다시 넣을 수 있지만, 아직 연결된 노드를 두 리스트에 동시에 넣을 수는 없습니다.
참고 링크
2 sources