연결 리스트(Linked List)는 데이터 구조의 일종으로, 각 요소가 포인터를 통해 서로 연결된 형태로 구성된다. 연결 리스트는 배열과 달리 고정된 크기를 가지지 않으며, 동적으로 메모리를 할당하고 해제할 수 있는 장점이 있다.

연결 리스트는 기본적으로 두 가지 주요 구성 요소로 이루어진다. 첫 번째는 노드(Node)로, 각 노드는 데이터와 다음 노드를 가리키는 포인터를 포함한다. 두 번째는 헤드(Head)로, 연결 리스트의 첫 번째 노드를 가리키는 포인터로 사용된다. 연결 리스트의 구조는 단순 연결 리스트(Singly Linked List), 이중 연결 리스트(Doubly Linked List), 원형 연결 리스트(Circular Linked List) 등 여러 형태로 나뉜다.

단순 연결 리스트는 각 노드가 다음 노드에 대한 참조만 가진다. 이중 연결 리스트는 각 노드가 다음 노드뿐만 아니라 이전 노드에 대한 참조를 가지고 있어 양방향으로 탐색이 가능하다. 원형 연결 리스트는 마지막 노드가 첫 번째 노드를 가리키는 구조로, 리스트의 끝과 시작이 연결된 형태를 가진다.

연결 리스트의 주요 장점은 삽입 및 삭제가 용이하다는 것이다. 특히 리스트 중간에 요소를 추가하거나 제거할 때 배열에 비해 성능이 뛰어나며, 메모리 사용에 있어 유연성을 제공한다. 그러나 각 노드가 포인터를 추가로 가지고 있어 메모리 오버헤드가 발생하며, 임의 접근이 어려워 탐색 속도는 배열에 비해 느리다.

연결 리스트는 주로 스택, 큐, 해시 테이블, 그래프 등 다양한 데이터 구조의 기초로 사용되며, 프로그래밍 언어 및 환경에 따라 적절한 구현 방식이 다를 수 있다.