정의
연결 리스트(Linked List)는 각 노드가 데이터와 다음 노드를 가리키는 포인터를 가진 자료구조입니다. 배열과 달리 메모리에 연속적으로 저장되지 않아, 중간 삽입/삭제가 효율적입니다.
핵심 특성
- ✓동적 크기: 배열과 달리 크기가 고정되지 않고 필요에 따라 늘어납니다.
- ✓노드 구조: 각 노드는 [데이터 | next 포인터]로 구성됩니다.
- ✓head/tail: 리스트의 시작(head)과 끝(tail)을 가리키는 포인터가 있습니다.
- ✓순차 접근: 인덱스로 바로 접근할 수 없고, head부터 순서대로 탐색해야 합니다.
활용 사례
이런 상황에서 사용됩니다:
🔄
빈번한 삽입/삭제
중간에 데이터를 자주 넣거나 빼야 할 때 배열보다 효율적입니다.
📚
스택/큐 구현
연결 리스트로 스택(LIFO)과 큐(FIFO)를 효율적으로 구현할 수 있습니다.
🎵
음악 재생 목록
이전/다음 곡으로 이동하는 재생 목록에 적합합니다 (이중 연결 리스트).
↩️
Undo 기능
편집기의 되돌리기 기능 구현에 연결 리스트가 사용됩니다.
주요 연산
주요 연산들:
append(value)
O(1)리스트 끝(tail)에 새 노드를 추가합니다.
prepend(value)
O(1)리스트 앞(head)에 새 노드를 추가합니다.
insert(index, value)
O(n)특정 인덱스 위치에 새 노드를 삽입합니다. 해당 위치까지 탐색이 필요합니다.
delete(index)
O(n)특정 인덱스의 노드를 삭제합니다. 이전 노드의 포인터를 수정합니다.
search(value)
O(n)특정 값을 가진 노드를 찾습니다. head부터 순차적으로 탐색합니다.
복잡도
시간 복잡도
최선
O(1)
평균
O(n)
최악
O(n)
공간 복잡도
O(n)
시각화로 더 깊이 이해하기
단계별 애니메이션과 코드 실행을 통해 알고리즘이 어떻게 동작하는지 직접 확인하세요.
시각화 시작하기