[Data Structure] 선형 자료구조

선형 자료구조를 시작하기 앞서 자료구조가 뭔지 알아보자

자료구조 란?

자료(데이터)를 저장하는 도구로 삽입/삭제/탐색 연산을 적절한 상황에 알맞게 사용하기 위해 사용한다.

 

---

배열 (Array)

• 같은 종류의 자료 여러개를 저장하기 위한 선형 자료구조
• 원소들이 메모리의 연속된 위치에 저장된다 => 캐시의 효율성과 연결
• 주어진 위치의 원소를 반환하거나 변경하는 동작이 O(1)로 가능
• 삽입, 삭제 연산 후 shift 비용이 발생하기 때문에 O(n)의 시간복잡도를 가짐
• 크기가 제한적이다 => 이를 보완한 것으로 동적 배열(Dynamic Array)가 있다

 

---

링크드리스트 (Linked List)

• 논리적 저장 순서와 물리적 저장 순서 비일치 (포인터로 연결)
• 특정 위치에서의 삽입과 삭제를 상수 시간에 할 수 있게 해줌
• 메모리 여기저기에 노드들이 흩어져 있어, 특정 위치의 값을 찾기가 힘들다 => access는 O(n)
• 노드의 구성
  1. 데이터 필드
  2. 다음 노드 참조 포인터

 

동적 배열과 링크드리스트의 차이점?

• 삽입, 삭제, 임의의 원소에 접근(access)하는 시간이 다르다
• 삽입과 삭제를 할일이 없거나, 배열의 끝에서만 하면 될 경우 => 동적 배열이 더 좋음
  • 빠르게 원소에 접근할 수 있고, 원소들이 메모리에 연속되어 배치되어있기 때문에 CPU 캐시 효율도가 높다
• 모든 원소들을 순회하며 삽입/삭제를 한다면 연결리스트가 더 좋은 선택

 

---

Vector (C++)

• 배열과 vector의 가장 큰 차이점: 배열은 크기가 고정, vector는 동적
• 특징
  1. 저장할 데이터 개수가 가변적일 때 사용
  2. 중간에 데이터 삽입/삭제가 없다
  3. index를 통해 랜덤 접근 가능

vector와 list 비교

	vector	list
크기변경	O	O
중간 삽입, 삭제	X	O
순차 접근	O	O
랜덤 접근	O	X

 

---

스택 (Stack)

• LIFO (Last In First Out), FILO (First In Last Out)
• 자료를 순서대로 쌓아서 보관하고 위에서 부터 빼서 사용
• push: 스택에 요소를 집어넣음
• pop: 맨 위의 요소 삭제
• top: 맨 위에 저장되어 있는 요소 반환
• Push, Pop 연산 모두 O(1)
• 제일 위에 쌓인 데이터(top) 정보만 알 수 있고, 스택 내용물은 절대 알 수 없기 때문에 알고싶다면 top부터 특정 데이터까지 모두 pop해야한다

 

---

큐 (Queue)

• LILO (Last In Last Out), FIFO (First In First Out)
• 자료를 순서대로 나열하고, 순서대로 빼서 사용
• enqueue(push): 큐에 요소를 집어넣음
• dequeue(pop): 맨 앞의 요소가 삭제
• front: 맨 앞에 저장되어 있는 요소의 값을 반환
• Enqueue, Dequeue 연산 모두 O(1)
• 제일 앞에 있는 데이터(Front) 정보만 알 수 있고, 중간의 데이터는 절대 알 수 없기 때문에 알고싶다면 특정 데이터까지 모두 dequeue 해야함
• 원형 큐 (Circular Queue)
  1. 논리적으로 배열의 처음과 끝이 연결되어 있는 것으로 간주
  2. 초기 공백 상태에는 front = rear = 0
  3. 공백, 포화 상태를 쉽게 구분하기위해 자리 하나를 항상 비워놓는 구조
  4. (index + 1) % size로 순환

 

---

덱 (deque)

• 큐의 확장형으로 양방향으로 데이터 삽입/삭제가 가능한 자료구조
• 특징
  1. 앞과 뒤에서 삽입, 삭제가 모두 가능해서 스택, 큐에 비해 자유도가 높다
  2. 사용방법이 vector와 비슷하지만, vector는 앞에서 삽입이 불가능하지만 덱은 삽입이 가능하다는 장점을 갖고 있다.