이중 연결 리스트 (Doubly Linked List)

이중 연결 리스트 (Doubly Linked List)

각 노드가 이전 노드(prev)와 다음 노드(next)를 모두 가리키는 포인터를 가진 연결 리스트로, 양방향 탐색이 가능하고 삭제 연산이 더 효율적

목적: 양방향 탐색, 효율적 삭제, 유연한 순회

특징: 양방향 포인터, 역방향 탐색, 삭제 효율, 더 많은 메모리

구성요소: 노드(prev+data+next), 헤드(head), 테일(tail)

시간 복잡도

• •접근: O(n)
• •검색: O(n)
• •삽입: O(1) - 위치 알 때
• •삭제: O(1) - 위치 알 때(prev 직접 접근)

공간 복잡도: O(n) - 단일보다 2배 포인터 메모리

장점: 양방향 순회, 빠른 삭제(prev 접근), 역방향 탐색, 유연성

단점: 추가 메모리(prev 포인터), 복잡한 구현, 포인터 유지보수

적용사례: LRU 캐시(해시+이중연결), 브라우저 앞/뒤로, 텍스트 에디터 Undo/Redo, LinkedHashMap

비교: 이중(양방향/빠른삭제/2배메모리) vs 단일(단방향/적은메모리)

연관: 연결 리스트, LRU 캐시, 포인터, 동적 메모리