[자료구조] 선형 자료 구조 - 연결 리스트 / 배열 / 벡터 / 스택 / 큐

선형 자료 구조란 요소가 일렬로 나열되어 있는 자료 구조를 말함

- 연결 리스트

- 연결 리스트는 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조

- 삽입 삭제가 O(1) 

- 탐색 O(n)

 

앞의 그림처럼 prev 포인터와 next 포인터로 앞과 뒤의 노드를 연결 시킨 것이다.

 

싱글 연결 리스트

- next 포인터만 가짐

싱글 연결 리스트

이중 연결 리스트

- next 포인터와 prev 포인터를 가짐

이중 연결 리스트

원형 이중 연결 리스트

- 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리키는 것을 말함

원형 이중 연결 리스트

 

이중 연결 리스트는 앞에서부터 요소를 넣는 push_front(), 뒤에서부터 요소를 넣는 push_back(), 중간에 요소를 넣는 insert() 함수가 있다.

 

#include <bits/stdc++.h>

using namespace std;
vector<int> v;

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++;  // it 은 1
    a.insert(it, 1000); // 1 위치에 1000 삽입 //9 1000 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9
    for(auto it : a) cout << it << " ";
    cout << '\n';
    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 
*/

 

- 배열

- 같은 타입의 변수들로 이루어져 있다.

- 크기가 정해져 있다 

- 인접한 메모리 위치에 있는 데이터를 모아놓은 집합이다.

- 중복을 허용하고 순서가 있다

- 탐색 O(1)이 되어 랜덤 접근이 가능

- 삽입 삭제에는 O(n)이 걸린다.

- 데이터 추가와 삭제를 많이 하는 것은 연결리스트, 탐색을 많이 하는 것은 배열로 하는 것이 좋다.

 

배열 vs 연결 리스트

배열은 상자를 순서대로 나열한 데이터 구조이다. 연결리스트는 상자를 선으로 연결한 형태의 데이터 구조이다. 

-> 상자 안의 요소를 알기 위해선 하나씩 상자 내부를 확인해야한다.

따라서 배열은 랜덤 접근이 가능 O(1) 하지만 연결리스트는 랜덤 접근이 불가능 O(n) 하다.

 

#include <bits/stdc++.h>

using namespace std;
int a[10];
int main()
{
    for(int i = 0; i < 10; i++) a[i] = i;
    for(auto it : a) cout << it << " ";
    cout << '\n';

    return 0;
}

//0 1 2 3 4 5 6 7 8 9

-  벡터

- 동적으로 요소를 할당할 수 있는 동적 배열

- 컴파일 시점에 개수를 모른다면 벡터를 써야 한다.

- 중복 허용 , 순서 O, 랜덤 접근 가능

- 탐색과 맨 뒤의 요소를 삭제하거나 삽입하는데  O(1)이 걸리며, 맨 뒤나 맨 앞이 아닌 요소를 삭제하고 삽입하는데 O(n) 걸림

- push_back을 해서 뒤에다가 데이터를 삽입하면 매번 크기가 증가 하는 것이 아니라 2의 제곱승 +1 마다 2배로 늘린다

 

push_back 할 떄 드는 비용 c1은 1 또는 1+ 2^k 이다.

n 번 push_back을 하면 다음과 같은 식이 나온다.

T(n)을 n 번 나누면 평균적으로 드는 비용을 알 수 있다.

push_bak은 O(1)의 시간 복잡도를 가진다

#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 << " "; //1 2 3 4 5 6 7 8 9 10 
    cout << '\n';
    v.pop_back(); //마지막 10 지움 
    
    for(int a : v) cout << a << " "; //1 2 3 4 5 6 7 8 9 
    cout << '\n';
    
    v.erase(v.begin(), v.begin()+1);  //start는 포함하고 end는 포함 하지 않는다 -> 0번 인덱스 지움
    for(int a : v) cout << a << " "; //2 3 4 5 6 7 8 9 
    cout << '\n';
    
    auto a = find(v.begin(), v.end(), 100);  //not found
    if(a == v.end()) cout << "not found" << '\n';
    
    fill(v.begin(),v.end(),10); //처음 부터 끝까지 10으로 채우기
    for(int a : v) cout << a << " "; //10 10 10 10 10 10 10 10  
    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 
*/

push_back() : 뒤부터 요소 더하기 / pop_back(): 맨 뒤부터 지우기 / erase() : 지우기 / find() : 요소 찾기 / clear() : 배열 초기화

 

벡터 v에 pair라는 값이 들어간다면 아래와 같은 방식으로 순회해야함

for( pair<int,int> a:v)

 

-  스택

- 스택은 가장 마지막으로 들어간 데이터가 가장 첫 번쨰로 나오는 성질 (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

-  큐

- 큐는 먼저 집어넣은 데이터가 먼저 나오는 성질(FIFO)

- 삽입 및 삭제에 O(1), 탐색에 O(n)

- CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시 등에 사용된다.

- enqueue()는 push(), dequeue()는 pop()

#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