선형 자료 구조란 요소가 일렬로 나열되어 있는 자료 구조를 의미한다.
연결 리스트
연결 리스트는 데이터를 감싼 노드를 포인터로 연결해 공간적인 효율성을 극대화시킨 자료구조 이다. 삽입과 삭제에는 O(1)이 걸리며 탐색에는 O(n)이 걸린다.
연결리스트 종류로는 싱글 연결 리스트, 이중 연결 리스트, 원형 이중 연결 리스트가 있다. 싱글 연결 리스트는 next 포인터만 가지고, 이중 연결 리스트는 next 포인터와 prev 포인더를 가진다. 원형 이중 연결 리스트는 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리키는 것을 의미한다.
배열
배열은 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있는 집합이다. 배열은 O(1)에 탐색이 가능하고 삽입과 삭제는 O(n)이 걸린다. 따라서 데이터 추가와 삭제를 많이 하는 것은 연결 리스트, 탐색을 많이 하는 것은 배열로 하는 것이 좋다.
배열과 연결 리스트 비교
배열은 상자를 순서대로 나열한 데이터 구조이며 몇번 째 상자인지만 알면 해당 상자의 요소를 끄집어낼 수 있다. 반면 연결 리스트는 상자를 선으로 연결한 구조이며상자 안의 요소를 알기 위해서는 하나씩 상자 내부를 확인해봐야 한다는 점이 다르다.
벡터
벡터는 쿠기가 정확하게 정해져 있지 않을 때, 중복을 허용하고 랜덤 접근을 하고 싶을 때 쓰인다. 탐색과 맨 뒤의 요소를 삭제와 삽입 하는데 O(1)이 걸리며, 맨 뒤나 앞이 아닌 요소를 삭제하고 삽입하는데에는 O(n)이 걸린다.
벡터에는 뒤부터 요소를 더하는 push_back(), 맨 뒤에서부터 지우는pop_back(), 지우는 erase(), 요소를 찾는 find(), 배열을 초기화하는 clear()가 있다.
스택
스택은 가장 마지막으로 들어간 데이터가 가장 첫번째로 나오는 성질을 가지고 있다. 재귀적인 함수, 알고리즘에 사용되며 삽입과 삭제에는 O(1), 탐색에는 O(n)이 걸린다.
큐
큐는 가장 먼저 집어 넣은 데이터가 가장 먼저 나오는 성질을 가진 구조이며 나중에 집어 넣은 데이커가 먼저 나오는 스택과는 반대되는 개념을 가졌다. 삽입 및 삭제에는 O(1), 탐색에는 O(n)이 걸린다. 보통 행렬, 너비 우선 탐색, 캐시 등에서 사용된다.
