2. 선형 자료 구조
✨ 선형 자료 구조
요소가 일렬로 나열되어 있는 자료 구조를 말함
1. 연결 리스트
데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조
앞의 그림처럼 prev 포인터와 next 포인터로 앞과 뒤의 노드를 연결시킨 것이 연결 리스트이며,
연결 리스트는 싱글 연결 리스트, 이중 연결 리스트, 원형 이중 연결 리스트 등이 있다.
참고로 맨 앞에 있는 노드를 헤드(head)라고 한다.
• 싱글 연결 리스트: next 포인터만 가짐
• 이중 연결 리스트: next 포인터와 prev 포인터를 가짐
• 원형 이중 연결 리스트: 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리키는 것
이 책에서는 이중 연결 리스트를 기반으로 설명하겠습니다. 이중 연결 리스트는 앞에서부터 요소를 넣는 push_front(), 뒤에서부터 요소를 넣는 push_back(), 중간에 요소를 넣는 insert() 등의 함수가 있습니다.
#include <bits/stdc++.h>
using namespace std;
int main() {
list<int> a;
for (int i = 0; i < 10; i++)a.push_back(i); //0 1 2 3 4 5 6 7 8 9
for (int i = 0; i < 10; i++)a.push_front(i); //9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9
auto it = a.begin(); it++; //0번째 9, it++ > 1 번째
a.insert(it, 1000); //1번째에 1000 넣기
for (auto it : a) cout << it << " ";
cout << '\n'; //9 1000 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9
a.pop_front(); //1000 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9
a.pop_back(); //1000 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8
for (auto it : a) cout << it << " ";
cout << '\n';
return 0;
}
/*
9 1000 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9
1000 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8
*/2. 배열 (array)
같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합
중복을 허용하고 순서가 있음
‘정적 배열’은 탐색에 O(1)이 되어 랜덤 접근(random access)이 가능합니다. 삽입과 삭제에는 O(n)이 걸립니다.
따라서 데이터 추가와 삭제를 많이 하는 것은 연결 리스트, 탐색을 많이 하는 것은 배열로 하는 것이 좋습니다.
배열은 인덱스에 해당하는 원소를 빠르게 접근해야 하거나 간단하게 데이터를 쌓고 싶을 때 사용합니다.
랜덤 접근과 순차적 접근
순차적 접근
순서가 정해진 원소 그룹을 저장된 순서대로 접근하는 방법
랜덤 접근(비순차 접근, 직접 접속)
동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능
요소의 개수와 무관하게 모든 요소에 대하여 쉽고 효율적으로 동일한 시간에 접근할 수 있다는 특징
배열과 연결 리스트 비교
배열은 상자를 순서대로 나열한 데이터 구조이며 몇 번째 상자인지만 알면 해당 상자의 요소를 끄집어낼 수 있다.
연결 리스트는 상자를 선으로 연결한 형태의 데이터 구조이며, 상자 안의 요소를 알기 위해서는 하나씩 상자 내부를 확인해봐야 한다는 점이 다르다.
배열 |
연결 리스트 |
| - 탐색이 빠르다 - 상자에 담긴 순서대로 하나씩 열면서 탐색 - 데이터 추가 및 삭제는 느리다 - 모든 상자를 앞으로 옮기면서 데이터 추가 가능 |
- 탐색이 느리다 - 주어진 선을 기반으로 순차적으로 상자를 열면서 탐색 - 데이터 추가 및 삭제는 삐르다 - 선을 바꿔서 연결만 하면 데이터 추가 가능 |
3. 백터 (vector)
동적으로 요소를 할당할 수 있는 동적 배열
컴파일 시점에 개수를 모른다면 벡터를 써야 함
중복을 허용하고 순서가 있고 랜덤 접근이 가능
탐색과 맨 뒤의 요소를 삭제하거나 삽입하는 데 O(1)이 걸리며, 맨 뒤나 맨 앞이 아닌 요소를 삭제하고 삽입하는 데 O(n)의 시간이 걸림
참고로 뒤에서부터 삽입하는 push_back()의 경우 O(1)의 시간이 걸리는데, 벡터의 크기가 증가되는 시간 복잡도가 amortized 복잡도, 즉 상수 시간 복잡도 O(1)과 유사한 시간 복잡도를 가지기 때문
4. 스택
가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질(LIFO, Last In First Out)을 가진 자료 구조
삽입 및 삭제에 O(1), 탐색에 O(n)이 걸림
ex ) 재귀적인 함수, 알고리즘에 사용되며 웹 브라우저 방문 기록 등에 쓰임
5. 큐 (queue)
먼저 집어넣은 데이터가 먼저 나오는 성질(FIFO, First In First Out)을 지닌 자료 구조
나중에 집어넣은 데이터가 먼저 나오는 스택과는 반대되는 개념
삽입 및 삭제에 O(1), 탐색에 O(n)이 걸림
ex) CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시 등에 사용