선형 자료 구조란 요소가 일렬로 나열되어 있는 자료 구조를 말한다.
연결 리스트는 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조다.
삽입과 삭제가 O(1)이 걸리며 탐색에는 O(n)이 걸린다.
prev 포인터와 next 포인터로 앞과 뒤의 노드를 연결시킨 것이 연결 리스트이며, 연결 리스트는 싱글 연결 리스트, 이중 연결 리스트, 원형 이중 연결 리스트가 있다. 참고로 맨 앞에 있는 노드를 헤드(head)라고 한다.
배열은 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합이다. 또한, 중복을 허용하고 순서가 있다.
여기서 설명하는 배열은 “정적 배열”을 기반으로 설명한다. 탐색에 O(1)이 되어 랜덤 접근(random access)이 가능하다. 삽입과 삭제에는 O(n)이 걸린다.
따라서 데이터 추가와 삭제를 많이 하는 것은 연결 리스트, 탐색을 많이 하는 것은 배열로 하는 것이 좋다.
배열은 인덱스에 해당하는 원소를 빠르게 접근해야 하거나 간단하게 데이터를 쌓고 싶을 때 사용한다.