5.2 선형 자료 구조

윤·2023년 10월 11일

CS

목록 보기

20/23

5.2.1 연결 리스트

데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료
삽입, 삭제 : O(1)
탐색 : O(n)

맨 앞에 있는 노드 : 헤드(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); 
	for (int i = 0; i < 10; i++)a.push_front(i); 
	auto it = a.begin(); it++; 
	a.insert(it, 1000); 
	for (auto it : a) cout << it << " ";
	cout << ’\n '; 
	a.pop_front();
    a.pop_back(); 
	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 
*/

5.2.2 배열

배열(array) : 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합
중복을 허용하고 순서가 있음
여기서는 정적 배열을 기반으로 설명!
탐색 : O(1). 랜덤 접근 가능
삽입, 삭제 : O(n)
따라서, 데이터 추가와 삭제 많이 하는 것은 연결 리스트, 탐색을 많이 하는 것은 배열로 하는게 좋음!
배열은 인덱스에 해당하는 원소를 빠르게 접근해야 하거나 간단하게 데이터를 쌓고 싶을 때 사용

랜덤 접근과 순차적 접근

랜점 접근
- 직접 접근이라고도 함
- 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능
- 데이터를 저장된 순서대로 검색해야 하는 순차적 접근과는 반대

배열과 연결 리스트 비교

배열 : 상자를 순서대로 나열한 데이터 구조. 몇 번째 상자인지만 알면 해당 상자 요소 끄집어낼 수 있음
연결 리스트 : 상자를 선으로 연결한 형태의 데이터 구조. 상자 안의 요소를 알기 위해 하나씩 상자 내부를 확인
탐색 : 배열이 더 빠름
데이터 추가 및 삭제 : 연결 리스트가 더 빠름

5.2.3 벡터

벡터(vector) : 동적으로 요소를 할당할 수 있는 동적 배열
컴파일 시점에 개수를 모른다면 벡터를 써야 함!
중복을 허용하고 순서가 있고 랜덤 접근이 가능
탐색, 맨 뒤 요소 삭제/삽입 : O(1)
맨 뒤나 맨 앞 아닌 요소 삭제/삽입 : O(n)
그림처럼 매번 크기가 증가하는게 아니라 2의 제곱승 + 1 마다 크기를 2배로 늘림

#include <bits/stdc++.h) 
using namespace std; 
vector<int) v; 
int main() {
	for (int i = 1; i <= 10; i++)v.push_back(i); 
	for (int a : v) cout << a << " ";
	cout << "\n";
	v.pop_back();
    
    for (int a : v) cout << a << " ";
    count << "\n";
    
    v.erase(v.begin(), v.begin() + 1); 
    
    for (int a : v) cout << a << " ";
    count << "\n";
    
    auto a = find(v.begin(), v.end(), 100); 
	if (a == v .end()) cout << "not found" << "\n";
    
    fill(v.begin() , v.end() , 10); 
	for (int a : v) cout << a << " "; 
	cout << "\n"; 
	v.clear(); 
	for (int a : v) cout << a << " "; 
	cout << "\n";
    
    return 0;
}
/* 
1 2 3 4 5 6 7 8 9 10 
1 2 3 4 5 6 7 8 9 
2 3 4 5 6 7 8 9 
not found 
10 10 10 10 10 10 10 10 
*/

5.2.4 스택

스택(stack) : LIFO.
재귀적 함수, 알고리즘에 사용
삽입, 삭제 : O(1)
탐색 : O(n)

#include <bits/stdc++.h> 
using namespace std; 
stack<int> stk; 
int main() { 
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	for (int i = 0; i < 10; i++)stk.push(i); 
	while (stk.size()) { 
		cout << stk.top() << " "; 
		stk.pop(); 
    }
}
/* 
9 8 7 6 5 4 3 2 1 0 
*/

5.2.5 큐

큐(queue) : FIFO.
나중에 집어넣은 데이터가 먼저 나오는 스택과는 반대
삽입, 삭제 : O(1)
탐색 : O(n)
CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속 기다리는 행렬, 너비 우선 탐색, 캐시 등에 사용

#include <bits/stdc++.h> 
using namespace std; 
int main() { 
	queue<int> q; 
	q.push(1); 
	cout < < q.front () < < "\n"; 
	q.pop(); 
	cout << q.size() << "\n"; 
	return 0; 
}
/*
1
0
*/