선형 자료 구조
기술노트
선형 자료 구조
--- > 데이터 요소가 일렬로 나열되어 있는 자료 구조 > 데이터의 삽입, 삭제, 검색 등이 순차적으로 이루어지는 구조
데이터 추가, 삭제를 많이 하는 것 -> 연결 리스트로 구현 탐색을 많이 하는 것 -> 배열로 구현
1. 연결 리스트
--- > 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조
시간 복잡도
- 삽입, 삭제 - O(1)
- 탐색 - O(n)
- prev 포인터와 next 포인터로 앞과 뒤의 노드를 연결시킨 것이 연결 리스트이다.
- 맨 앞에 있는 노드 : 헤드(head)
- 싱글 연결 리스트 : next 포인터만 가진다.
- 다음 노드에 대한 참조만 가지고 있기 때문에 노드를 단방향으로 밖에 탐색하지 못한다.
- 이중 연결 리스트 : next 포인터와 prev 포인터를 가진다.
- 다음 노드 뿐만 아니라 이전 노드의 참조까지 추가하여 양방향으로 탐색이 가능하도록 하여 검색 속도를 향상 시킬 수 있는 방법을 제공한다.
- 원형 이중 연결 리스트 : 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리킨다.
2. 배열
--- > 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합
- 인덱스에 해당하는 원소를 빠르게 접근해야 하거나 간단하게 데이터를 쌓고 싶을 때 사용
- 중복 허용, 순서 O
시간 복잡도 (정적 배열 기반)
- 삽입, 삭제 : O(n)
- 탐색 : O(1) -> 랜덤 접근 가능
랜덤 접근과 순차적 접근
---
- 랜덤 접근 : 직접 접근이라고 하며, 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능
- 순차적 접근 : 데이터를 저장된 순서대로 검색해야 하는 기능
배열과 연결 리스트 비교
--- 배열
- 상자를 순서대로 나열한 데이터 구조이다.
- 몇 번째 상자인지만 알면 해당 상자의 요소를 끄집어낼 수 있다.
- 랜덤 접근 가능O - O(1)
- 탐색이 빠르다.
- 데이터 추가 및 삭제가 느리다. (모든 상자를 앞으로 옮겨야 추가가 가능하므로)
연결 리스트
- 상자를 선으로 연결한 형태의 데이터 구조이다.
- 상자 안의 요소를 알기 위해서는 하나씩 상자 내부를 확인해야 한다.
- 랜덤 접근 불가능X - O(n)
- 탐색이 느리다.
- 데이터 추가 및 삭제가 빠르다. (선을 바꿔서 연결해주기만 하면 되므로)
3. 벡터(vector)
--- > 동적으로 요소를 할당할 수 있는 동적 배열
- 컴파일 시점에 개수를 모를 때 사용
- 중복 허용, 순서 O
- 랜덤 접근 가능
시간 복잡도
- 탐색, 맨 뒤의 요소 삭제 또는 삽입 - O(1)
- 맨 뒤나 맨 앞이 아닌 요소 삭제 또는 삽입 - O(n)
뒤에서부터 삽입하는 경우 O(1)의 시간이 걸리는데, 벡터의 크기가 증가되는 시간 복잡도가 amortized 복잡도, 즉 상수 시간 복잡도 O(1)과 유사한 시간 복잡도를 가지기 때문이다.
4. 스택
--- > 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 LIFO(Last In First Out) 성질을 가진 자료 구조
- 재귀적인 함수, 알고리즘에 사용되며 웹 브라우저 방문 기록 등에 쓰인다.
시간 복잡도
- 삽입 및 삭제 - O(1)
- 탐색 - O(n)
함수
- push()
- pop()
5. 큐
> 먼저 집어넣은 데이터가 먼저 나오는 FIFO(First In First Out) 성질을 가진 자료 구조
- CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시 등에 사용
시간 복잡도
- 삽입 및 삭제 - O(1)
- 탐색 - O(n)
함수
- enqueue()
- dequeue()