[cs 스터디] 5-2. 선형 자료 구조

선형 자료 구조
: 요소가 일렬로 나열되어 있는 자료 구조

연결 리스트

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

삽입:$O(1)$
탐색: $O(n)$

싱글 연결 리스트, 이중 연결 리스트, 원형 이중 연결 리스트

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

---

배열

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

(정적 배열을 기반으로 설명)
접근(참조): $O(1)$
삽입과 삭제: $O(n)$

데이터의 추가와 삭제가 많다 -> 연결리스트
접근(참조)를 많이 한다 -> 배열

랜덤 접근과 순차적 접근

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

배열과 연결 리스트 비교

배열은 몇 번째 상자인지만 알면 랜덤 접근이 가능
연결 리스트는 불가능

---

벡터

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

컴파일 시점에 개수를 모른다 -> 벡터 사용
중복을 허용함, 순서가 있음, 랜덤 접근이 가능함
탐색, 맨 뒤 요소 삭제와 삽입: $O(1)$
맨 뒤 요소가 아닌 요소 삭제와 삽입: $O(n)$

---

스택

가장 마지막에 들어간 데이터가 가장 첫 번째로 나오는 성질(LIFO, Last In First Out)을 가진 자료 구조

재귀적인 함수, 알고리즘에 사용
웹브라우저 방문 기록

삽입과 삭제: $O(1)$
탐색: $O(n)$

---

큐

먼저 집어넣은 데이터가 먼저 나오는 성질(FIFO, First In First Out)을 가진 자료 구조

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

삽입: $O(1)$
삭제: $O(n)$