연결 리스트 (Linked List)

연결 리스트 (Linked List)

노드들이 포인터로 연결된 선형 자료구조로, 각 노드는 데이터와 다음 노드의 주소를 저장하며 비연속 메모리에 동적으로 할당되어 삽입·삭제가 효율적

목적: 동적 크기, 효율적 삽입·삭제, 메모리 유연성

특징: 포인터 기반, 비연속 메모리, 동적 할당, 순차 접근

구성요소: 노드(데이터+포인터), 헤드(head), 테일(tail)

종류

• •단일 연결 리스트(Singly): next 포인터만, 단방향
• •이중 연결 리스트(Doubly): prev+next 포인터, 양방향
• •원형 연결 리스트(Circular): 마지막 노드가 첫 노드를 가리킴

시간 복잡도

• •접근(Access): O(n) - 순차 탐색 필요
• •검색(Search): O(n)
• •삽입(Insert): O(1) - 위치 알고 있을 때, O(n) - 검색 포함
• •삭제(Delete): O(1) - 위치 알고 있을 때, O(n) - 검색 포함

공간 복잡도: O(n) - 포인터 추가 메모리(단일 n×ptr, 이중 n×2ptr)

장점: 동적 크기, 빠른 삽입·삭제(O(1)), 메모리 유연성, 오버플로우 없음

단점: 느린 접근(O(n)), 추가 메모리(포인터), 캐시 비효율, 역방향 탐색 어려움(단일)

적용사례: 스택, 큐, 해시 충돌 체이닝, LRU 캐시, 음악 재생목록

비교: 연결 리스트(비연속/동적/O(1)삽입) vs 배열(연속/고정/O(1)접근)

연관: 노드, 포인터, 이중 연결 리스트, 동적 메모리