연결 리스트

연결 리스트 (Linked List)

연결 리스트는 데이터를 저장하는 노드들이 포인터(링크)를 통해 선형적으로 연결된 자료구조이다. 각 노드는 데이터와 하나 이상의 포인터를 가지고 있으며, 이 포인터를 통해 노드들이 서로 연결되어 리스트를 형성한다.

노드 기반 구조 연결 리스트는 여러 개의 노드로 구성되며, 각 노드들은 데이터와 포인터를 포함한다.
비연속적인 메모리 공간 배열과 달리 노드들이 메모리 상에서 연속적으로 배치될 필요가 없으며, 각 노드는 포인터를 통해 논리적으로만 연결된다.
헤드(Head) 포인터 리스트의 시작점을 가리키는 헤드 포인터가 존재하며, 탐색 등의 연산을 수행할 경우 일반적으로 헤드에서 시작한다.
동적 메모리 할당 연결 리스트는 노드가 필요할 때마다 메모리를 동적으로 할당받으므로, 프로그램 실행 중에도 크기가 유동적으로 변할 수 있다.
유연한 크기 조절 포인터를 통해 각 노드들이 논리적으로만 연결되어 있어, 리스트의 크기를 제한 없이 조절할 수 있다.
빠른 삽입/삭제 포인터 조정을 통해 노드의 삽입/삭제 연산을 수행하므로, 중간 삽입/삭제 시에도 O(1)에 가까운 시간 복잡도를 가진다.
추가 메모리 사용 각 노드는 데이터 외에도 포인터 정보를 저장해야하므로, 비슷한 크기라면 배열보다 메모리 사용량이 많을 수 있다.
임의 접근 불가 배열과 달리 인덱스를 통한 임의 접근이 불가능하며, 원하는 위치의 노드에 접근하려면 헤드부터 순차적으로 탐색하며 이 경우 O(n)의 시간이 소요된다.

각 노드가 데이터와 다음 노드를 가리키는 포인터만을 가지는 기본적인 연결 리스트이다. 리스트의 처음, 헤드부터 끝까지 한 방향으로만 순회할 수 있다.