CSㅣ선형 자료 구조 - 연결리스트, 배열, 벡터, 스택, 큐

선형 자료 구조

선형 자료 구조

'선형 자료 구조'란, 요소가 일렬로 나열되어 있는 자료 구조를 말한다.

연결 리스트

연결 리스트

'연결 리스트'는 데이터를 감싼 노드를 포인터로 연결해 공간적인 효율성을 극대화시킨 자료 구조이다. 삽입과 삭제가 O(1)이 걸리고, 탐색에는 O(n)이 걸린다.

연결리스트는 prev 포인터와 next 포인터로 앞과 뒤의 노드를 연결시킨다. 또한, 연결 리스트는 싱글 연결 리스트, 이중 연결 리스트, 원형 이중 연결 리스트가 있다. 맨 앞에 있는 노드를 '헤드(head)'라고 한다.

• 싱글 연결 리스트 : next 포인터만 가진다.
• 이중 연결 리스트 : next포인터와 prev포인터를 가진다
• 원형 이중 연결 리스트 : 이중 연결 리스트와 같지만, 마지막 노드의 next 포인터가 헤드 노드를 가리킨다.

이중 연결 리스트를 기반으로 이 글에서는 설명을 해보겠다.
이중 연결 리스트는 앞에서부터 요소를 넣는 push_front(), 뒤에서부터 요소를 넣는 push_back(), 중간에 요소를 넣는 insert() 등의 함수가 있다.
예시 코드로는 아래와 같다.

C++

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
*/

배열

배열

'배열(array)'은, 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있고, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합이다. 또한, 중복을 허용하고 순서가 있다.
지금 설명하는 배열은 '정적 배열'을 기반으로 설명한다. 탐색에 O(1)이 되어 랜덤접근(random access)이 가능하다. 삽입과 삭제에는 O(n)이 걸린다. 따라서 데이터 추가와 삭제를 많이 하는 것은 연결 리스트, 탐색을 많이 하는 것은 배열로 하는 것이다 좋다.

배열은 인덱스에 해당하는 원소를 바르게 접근해야 하거나 간단하게 데이터를 쌓을 때 사용하면 좋다.

랜덤 접근과 순차적 접근

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

배열과 연결 리스트 비교

'배열'은, 상자를 순서대로 나열한 데이터 구조이고, 몇 번재 상자인지만 알면 해당 상자의 요소를 끄집어낼 수 있다.

'연결 리스트'는, 상자를 선으로 연결한 형태의 데이터 구조이고, 상자 안의 요소를 알기 위해 하나씩 상자 내부를 확인해봐야 한다는 것이 좀 다르다.

따라서, 탐색은 배열이 빠르고 연결 리스트는 느리다. 배열의 경우에는 상자 위에 있는 요소를 탐색하면 되는데, 연결 리스트는 상자를 열고 주어진 선을 기반으로 순차적으로 열어봐야 한다.

하지만 데이터 추가 및 삭제는 연결 리스트가 더 빠르고 배열은 느리다. 배열은 모든 상자를 앞으로 옮겨야 추가가 가능하지만, 연결 리스트는 선을 바꿔서 연결해주기만 하면 된다.

C++

#incloude<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
*/

벡터

벡터

'벡터(vector)'는, 동적으로 요소를 할당할 수 있는 동적 배열이다. 컴파일 시점에 개수를 모르면 벡터를 써야한다. 또한, 중복을 허용하고 순서가 있고, 랜덤 접근이 가능하다. 탐색과 맨 뒤의 요소를 삭제하거나 삽입하는데 O(1)이 걸리고, 맨 뒤나 맨 앞이 아닌 요소를 삭제하고 삽입하는데는 O(n)의 시간이 걸린다.

뒤에서부터 삽입하는 push_back()의 경우에는 O(1)이 걸리는, 벡터의 크기가 증가되는 시간 복잡도가 amortized 복잡도, 즉, 상수 시간 복잡도 O(1)과 비슷한 시간 복잡도를 가지기 때문이다.

벡터에 대해서 좀 더 자세히 설명하고 싶지만, 본인도 이해가 어려워 조금 더 공부한 뒤에 자세하게 다른 글에서 다뤄보겠다.

스택

스택

스택은, 가장 마지막으로 들어간 데이터가 가장 첫 번재로 나오는 성질인 LIFE(Last In First Out)를 가진 자료 구조이다. 재귀적인 함수, 알고리즘에 사용되고, 웹 브라우저 방문 기록 등에도 쓰인다. 삽입 및 삭제에 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
*/

큐

큐(queue)는, 먼저 집어넣은 데이터가 먼저 나오는 성질인 FIFO(First In First Out) 성질을 가진 자료 구조이고, 나중에 집어넣는 데이터가 먼저 나오는 스택과는 반대되는 개념을 가졌다. 삽입 및 삭제에 O(1), 탐색에 O(n)이 걸린다.

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

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