[CS 스터디] 5.2 선형 자료 구조 (배열, 연결리스트, 벡터, 스택, 큐)

목차

[면접을 위한 CS 전공지식 노트] 는 C++ 기반의 자료구조를 다루고 있다.

---

자료구조는 크게 선형과 비선형의 구조로 나뉜다. 

💡 선형 자료 구조란?
: 자료를 구성하는 데이터를 일렬로 나열되어 있는 자료 구조를 말한다.

 

대표적인 자료구조

• 선형구조 : 배열, 연결리스트, 스택, 큐, 데크
• 비선형구조 : 트리, 그래프

 

1. 연결 리스트(Linked List)

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

• 삽입/삭제 : O(1)
• 탐색 : O(n)

연결리스트는 크게 세 가지로 구분 된다.

1. 싱글 연결 리스트
2. 이중 연결 리스트
3. 원형 이중 연결 리스트

연결리스트의 가장 큰 장점은 리스트의 길이가 가변적이란 것이다. 메모리 할당이 따로 필요가 없기 때문에 삽입이나 삭제가 많은 문제에 활용하기 적당하다. 하지만, 어떤 노드를 탐색하거나 데이터를 변경할 때애는 한 번에 찾아낼 수 없고, 반드시 연결리스트를 전부 탐색해야 한다. 

장점	단점
삽입/삭제가 빠르고 용이하다 . O(1)	자료 수정 및 탐색이 느리다. O(n)

 

2. 배열(Array)

💡 배열
: 인덱스를 갖고 있어 순차적으로 데이터가 삽입/삭제될 수 있는 형태의 자료구조

• 삽입/삭제 : O(n)
• 탐색 : O(1)

배열의 특징

1. 같은 타입의 변수들로 구성 되어 있음
2. 크기가 정해져 있음
3. 인접한 메모리 위치에 있는 데이터를 모아놓은 집합
4. 중복을 허용하고 순서가 있음

배열은 인덱스에 해당하는 원소를 빠르게 접근해야 하거나, 간단하게 데이터를 샇고 싶을 때 사용한다. 반대로 배열은 초기에 선언할 때 메모리의 크기가 정해져 있으므로 중간에 삽입/삭제를 하려면 크기를 새로 할당해줘야 하며, 값들의 위치를 하나하나 변경해줘야하기 때문에 오랜 시간이 걸린다.

장점	단점
인덱스를 활용하기에 원하는 값에 쉽게 접근할 수 있다. O(1)	중간에 삽입/삭제하기 어렵다. O(n)

 

2.1 랜덤 접근과 순차적 접근

배열의 경우 랜덤접근(random access)이 가능하다.

• 랜덤 접근(직접접근) : 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능
• 순차적 접근 : 저장된 순서대로 검색해야 하는 접근법

2.2 배열과 연결리스트 비교

	배열(Array)	연결리스트(Linked List)
장점	인덱스를 통한 빠른 접근 가능	삽입/삭제 용이
단점	삽입/삭제 오래 걸림	랜덤 접근 불가능, 처음부터 탐색을 진행해야 함.
용도	빠른 접근이 요구되고, 데이터의 삽입/삭제가 적을 때 사용	삽입/삭제 연산이 잦고, 검색 빈도가 적을 때 사용

 

3. 벡터(Vector)

💡 벡터
: 동적으로 요소를 할당할 수 있는 동적 배열

• 삽입/삭제 
  - 맨 앞과 마지막 요소 : O(1)
  - 그 외 중간값 : O(n)
• 탐색 : O(1)

벡터의 특징

1. 동적으로 요소를 할당할 수 있는 동적 배열
2. 중복을 허용하며 순서가 있음
3. 랜덤 접근 가능

벡터가 랜덤 접근이 가능한 이유는 벡터가 배열을 이용해 만든 자료구조이기 때문이다. 따라서 원소들은 메모리의 연속된 위치에 저장된다. 배열과 마찬가지로 인덱스를 사용하여 접근하기 땨문에 주어진 위치의 원소를 반환하거나 변경하는 동작을 O(1)에 할 수 있다.

 

 

4. 스택(Stack)

💡 스택
: 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질(LIFO)를 가진 자료 구조이다.

• 삽입/삭제 : O(1)
• 탐색 : O(n)

스택 사용 사례

1. 재귀 알고리즘
   - 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다.
   - 재귀함수를 빠져 나와 backtracking을 할 때는 스택에 넣어 두었던 임시 데이터를 빼줘야 한다.
   - 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다.
2. 웹 브라우저 방문기록 (뒤로가기)
3. 실행 취소(undo)

장점	단점
구조가 단순해서 구현이 쉽다. 데이터 저장/읽기 속도가 빠르다.	top 위치 이외의 데이터에 접근할 수 없기 때문에 탐색이 불가능하다. 탐색하려면 모든 데이터를 떠내면서 진행해야 한다.

 

5. 큐(Queue)

💡 큐
: 먼저 집어 넣은 데이터가 먼저 나오는 성질(FIFO)을 지닌 자료 구조이다.

• 삽입/삭제 : O(1)
• 탐색 : O(n)

큐 사용 사례

1. CPU 작업을 기다리는 프로세스
2. 스레드 행렬 또는 네트워크 접속을 기다리는 행렬
3. BFS 알고리즘
4. 캐시

장점	단점
데이터의 접근, 삽입, 삭제가 빠르다.	큐 역시 스택과 마찬가지로 중간에 위치한 데이터에 대한 접근이 불가능하다.

 

 

[참고자료]

https://allg.tistory.com/29

https://dnf-lover.tistory.com/entry/자료구조-자료구조의-선형-비선형-분류에-따른-각-종류와-자료구조별-특징-간단-정리

https://gmlwjd9405.github.io/2018/08/03/data-structure-stack.html

https://velog.io/@nnnyeong/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9D-Stack-%ED%81%90-Queue-%EB%8D%B1-Deque