연결 리스트는 값을 담은 노드들이 다음 또는 이전 노드를 가리키는 연결로 순서를 표현하는 자료구조이다.
원리
노드가 메모리에 연속해서 놓일 필요가 없다. 단일 연결과 이중 연결이 대표적이며, 위치를 찾는 순회와 연결을 바꾸는 작업의 비용을 따로 계산한다.
예시
A→B→C에서 A 다음에 X를 넣으려면 X가 B를 가리키고 A가 X를 가리키도록 바꾼다. 이미 A를 알고 있다면 뒤의 모든 원소를 복사할 필요가 없다.
주의할 점
삽입 위치를 처음부터 찾는 데에는 O(n)이 걸릴 수 있다. 삭제에 필요한 이전 노드도 알고 있어야 한다. 포인터 공간과 캐시 접근 특성 때문에 배열보다 항상 유리한 것은 아니다.