연결 리스트 (Linked List)

Jeonghwan Yoon·2025년 3월 30일

jungle_TIL

연결 리스트란?

연결 리스트는 데이터를 일렬로 저장하되,

각 노드(Node)가 다음 노드의 주소를 저장해 연결되는 구조의 자료구조이다.

배열과 달리 메모리가 연속적이지 않아도 됨
데이터 삽입/삭제가 유연함

기본 구성

Node: 데이터 값 + 다음 노드를 가리키는 포인터(next)
LinkedList: 노드들을 연결한 구조

연결 리스트 종류

종류	설명
단일 연결 리스트	다음 노드만 가리킴 (`next`)
이중 연결 리스트	이전(`prev`), 다음(`next`) 노드를 모두 가리킴
환형 연결 리스트	마지막 노드가 첫 번째 노드를 가리킴

왜 사용하는가?

이유	설명
유연한 삽입/삭제	중간 삽입/삭제가 포인터만 수정하면 되어 빠름
동적 메모리 구조	필요할 때마다 메모리 할당, 배열처럼 고정 크기 아님
다양한 자료구조의 기반	스택, 큐, 트리, 해시 등 내부 구현에 사용

단일 연결 리스트 구현

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

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

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = new_node

    def display(self):
        curr = self.head
        while curr:
            print(curr.data, end=" → ")
            curr = curr.next
        print("None")

시간 복잡도

연산	시간복잡도	설명
탐색	O(N)	순차 탐색만 가능
맨 앞 삽입	O(1)	head 변경만
맨 뒤 삽입	O(N)	끝까지 순회 필요
중간 삽입	O(1) (노드 참조 시)	포인터만 수정
삭제	O(1) (노드 참조 시)	포인터 끊기만 하면 됨

배열과 비교

항목	연결 리스트	배열 (리스트)
메모리 구조	불연속	연속
삽입/삭제	빠름	느림 (데이터 이동 필요)
접근 방식	순차 접근	인덱스 접근 가능
크기 조절	유동적	고정 또는 재할당 필요

C언어 구현 시 유의사항

항목	설명
클래스 없음	`struct`로 구현
동적 할당	`malloc()`, `free()` 필요
포인터 연산	`->`, `*`, `&` 직접 사용
예외 처리	NULL 체크 필수
메모리 해제	메모리 누수 방지 위해 `free()` 필요

주요 용어

용어	설명
Node	데이터 + 다음 노드 포인터
Head	연결 리스트의 시작 노드
Tail	마지막 노드 (`next`가 None)
next	다음 노드 가리키는 포인터
prev	이전 노드 가리키는 포인터 (이중 연결 리스트)

자주 등장하는 문제 유형

유형	설명
연결 리스트 뒤집기	포인터 방향을 반대로 변경
중복 제거	순회하면서 중복된 값 제거
K번째 노드 찾기	K만큼 순회
루프 감지	slow/fast 포인터 방식 사용
LRU 캐시 구현	해시맵 + 이중 연결 리스트 조합