연결 리스트

자료 하나하나(노드)가 다음 자료의 위치(참조)를 들고 줄줄이 이어진 자료구조다. 기차 칸들이 다음 칸과 연결 고리로만 이어져 있는 것과 비슷하다. 배열과 달리 중간에 자료를 끼워 넣거나 뺄 때 뒤의 자료를 전부 밀 필요가 없지만, 몇 번째 자료인지 바로 찾아가려면 앞에서부터 하나씩 따라가야 한다.