정의

연결 리스트(Linked List)는 각 노드가 데이터와 다음 노드를 가리키는 포인터를 가진 자료구조입니다. 배열과 달리 메모리에 연속적으로 저장되지 않아, 중간 삽입/삭제가 효율적입니다.

핵심 특성

• ✓동적 크기: 배열과 달리 크기가 고정되지 않고 필요에 따라 늘어납니다.
• ✓노드 구조: 각 노드는 [데이터 | next 포인터]로 구성됩니다.
• ✓head/tail: 리스트의 시작(head)과 끝(tail)을 가리키는 포인터가 있습니다.
• ✓순차 접근: 인덱스로 바로 접근할 수 없고, head부터 순서대로 탐색해야 합니다.

시간 복잡도