5.2 선형 자료 구조
선형 자료 구조란 요소가 일렬로 나열되어 있는 자료 구조를 말한다.
5.2.1 연결 리스트(Linked List)
연결 리스트란,
- 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조이다.
- 삽입과 삭제가 O(1)이 걸리며 탐색에는 O(n)이 걸린다.
데이터의 삽입과 삭제가 빈번하게 일어나는 경우에는 유용하게 이용될 수 있으나, 특정 노드에 빠르게 접근하는 것이 어렵기 때문에 빠른 검색이 중요한 상황에서는 다른 자료 구조를 고려할 필요가 있다.
연결 리스트의 종류
노드들 간의 연결 방식과 구성에 따라 크게 세 가지로 나뉜다.
싱글 연결 리스트 : next 포인터만 가진다.
이중 연결 리스트 : next 포인터와 prev 포인터를 가진다.
원형 이중 연결 리스트 : 마지막 노드의 next 포인터가 헤드 노드를 가리킨다.
5.2.2 배열(Array)
배열이란,
- 같은 타입의 변수들로 이루어져 있다.
- 크기가 정해져있다.
- 인접한 메모리 위치에 있는 데이터를 모아놓은 집합이다.
- 중복을 허용하고 순서가 있다.
- 탐색에는 O(1)이 걸리고 삽입과 삭제에는 O(n)이 걸린다.
연결 리스트와 반대되는 특징으로, 데이터 삽입과 삭제가 빈번하게 일어나는 경우에는 연결 리스트를 탐색이 빈번하게 일어나는 경우에는 배열을 사용하는 것이 좋다.
랜덤 접근과 순차적 접근
- 랜덤 접근은 임의의 인덱스에 해당하는 데이터에 직접 접근할 수 있는 기능이다.
- 순차적 접근은 데이터를 저장된 순서대로 검색할 수 있는 기능이다.
배열과 연결 리스트 비교
- 배열은 탐색이 빠르고, 데이터 추가 및 삭제는 느리다.
- 연결리스트는 탐색이 느리나, 데이터 추가 및 삭제는 빠르다.
5.2.3 벡터(Vector)
벡터란,
- 동적으로 요소를 할당할 수 있는 동적 배열이다.
- 중복을 허용하고 순서가 있으며 랜덤 접근이 가능하다.
- 탐색과 맨 뒤의 요소를 삽입하고 삭제하는 데 O(1)이 걸린다.
- 맨 앞과 맨 뒤가 아닌 요소를 삽입하고 삭제하는 데 O(n)이 걸린다.
데이터의 삽입과 삭제가 맨 앞이나 맨 뒤에 이루어지는 경우에는 빠른 성능을 보이지만, 중간에 요소를 삽입하거나 삭제하는 경우에는 성능이 떨어질 수 있다.
5.2.4 스택(Stack)
스택이란,
- LIFO(Last In First Out) 성질을 가진 자료 구조이다.
- 삽입 및 삭제에 O(1)이 걸리고 탐색에 O(n)이 걸린다.
- 재귀적인 함수, 알고리즘에 사용되며 웹 브라우저 방문 기록 등에 쓰인다.
5.2.5 큐(Queue)
큐란,
- FIFO(First In First Out) 성질을 지닌 자료 구조이다.
- 삽입 및 삭제에 O(1)이 걸리고 탐색에 O(n)이 걸린다.
- CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시 등에 사용된다.
