선형 자료 구조

👣 개요

말 그대로 자료 구조가 일렬로 나열되어 있는 자료 구조를 일컫느다.

👣 배열

물리적으로 메모리에 나열되어 있는 데이터 집합.
요소들의 크기가 정해져 있고 같은 변수 타입으로 이뤄져 있다.
중복을 허용하고 순서가 존재.

	Random Read	Sequential Read	Insert	Delete
시간 복잡도	O(1)	O(n)	O(n)	O(n)

👣 연결 리스트

논리적으로 나열되어 있는 데이터 집합.
각 요소를 포함한 노드 앞단에 포인터가 존재해 다음 포인터를 표시할 수 있다.

싱글 연결 리스트
Next 포인터만 포함.

이중 연결 리스트
Next 포인터와 Prev 포인터를 포함.

원형 이중 연결 리스트
이중 연결 리스트와 같지만 마지막 노드와 첫 노드가 포인터로 연결된 형태.

	Random Read	Sequential Read	Insert	Delete
시간 복잡도	O(n)	O(n)	O(1)	O(1)

👣 벡터

배열과 같이 물리적으로 메모리에 나열되어 있는 데이터 집합지만
배열의 길이가 +1 될 때마다 새로운 배열의 크기를 늘리는 것이 아니라
2의 제곱승마다 크기를 2배로 늘리는 방식을 가지고 있다.

👣 스택

LIFO의 성질을 가지고 있는 자료 구조.

	Random Read	Sequential Read	Insert	Delete
시간 복잡도	O(n)	O(n)	O(1)	O(1)

Random Read가 O(n)인 이유는 원하는 데이터가 나올 때까지 pop해야 하기 때문이다.

👣 스택

FIFO의 성질을 가지고 있는 자료 구조.

	Random Read	Sequential Read	Insert	Delete
시간 복잡도	O(n)	O(n)	O(1)	O(1)