선형 자료 구조란 요소가 일렬로 나열되어 있는 자료 구조를 말합니다.
연결 리스트
연결 리스트는 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조입니다. 삽입과 삭제가 O(1), 탐색에는 O(n)이 걸립니다.
- 싱글(단순) 연결 리스트 : next 포인터만 가집니다.
- 원형 이중 연결 리스트 : 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리킵니다.
- 이중 연결 리스트 : next 포인터와 prev 포인터를 가집니다.
배열
배열은 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합입니다. 중복을 허용하고 순서가 있습니다.
삽입과 삭제에는 O(n), 탐색에 O(1)이 걸립니다.
배열은 인덱스에 해당하는 원소를 빠르게 접근해야 하거나 간단하게 데이터를 쌓고 싶을 때 사용합니다.
랜덤 접근과 순차적 접근
랜덤 접근은 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능으로, 직접 접근이라고도 합니다.
순차적 접근은 데이터를 저장된 순서대로 검색해야하는 접근 방식을 말합니다.
배열 vs 연결 리스트
배열은 순서대로 나열한 데이터 구조이고 연결 리스트는 선으로 연결한 형태의 데이터 구조입니다.
배열의 경우 상자 위에 있는 요소를 탐색하면 되지만, 연결 리스트는 상자를 열어서 내부를 확인해봐야 하고 주어진 선을 기반으로 순차적으로 열어야 합니다.
이처럼 탐색은 배열이 빠르고 연결 리스트는 느립니다.
하지만 데이터 추가 및 삭제는 연결 리스트가 더 빠르고 배열은 느립니다.
배열은 모든 상자를 앞으로 옮겨야 추가가 가능하지만, 연결 리스트는 선을 바꿔서 연결해주기만 하면 되기 때문이죠.
벡터
벡터는 동적으로 요소를 할당할 수 있는 동적 배열입니다. 컴파일 시점에 개수를 모른다면 벡터를 써야 합니다. 중복을 허용하고 순서가 있고 랜덤 접근이 가능합니다. 탐색과 맨 뒤의 요소를 삭제하거나 삽입하는 데 O(1)이 걸리며, 맨 뒤나 맨 앞이 아닌 요소를 삭제하고 삽입하는데 O(n)의 시간이 걸립니다.
스택
스택은 후입선출(LIFO, Last In First Out)의 성질을 가진 자료 구조입니다.
재귀적인 함수, 알고리즘에 사용되며 웹 브라우저 방문 기록 등에 쓰입니다. 삽입 및 삭제에 O(1), 탐색에 O(n)이 걸립니다.
큐
큐는 선입선출(FIFO, First In First Out)의 성질을 지닌 자료 구조입니다.
CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시 등에 사용됩니다. 삽입 및 삭제에 O(1), 탐색에 O(n)이 걸립니다.
