[자료구조] 선형 자료 구조

선형 자료 구조

선형 자료 구조란 요소가 일렬로 나열되어 있는 자료 구조를 의미하며, 연결 리스트, 배열, 벡터, 스택, 큐 등이 있다.

연결 리스트(Linked List)

연결 리스트는 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료구조를 의미한다. 시간 복잡도 상 삽입과 삭제는 O(1)이 걸리고 탐색에는 O(n)이 걸린다.

 

앞의 그림처럼 prev 포인터와 next 포인터로 앞과 두의 노드를 연결시킨 것을 연결 리스트라고 하며, 연결 리스트는 싱글 연결 리스트, 이중 연결 리스트, 원형 이중 연결 리스트가 있다.

싱글 연결 리스트는 next 포인터만을 이중 연결 리스트는 next 포인터와 prev포인터를 원형 이중 연결 리스트는 마지막 노드의 next 포인터가 헤드 노드(맨 앞에 있는 노드)를 가리키는 것을 의미한다.

배열(Array)

배열(Array)이란 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓는 집합이다. 그리고 중복을 허용하고 순서가 존재한다.

정적 배열은 접근에 O(1)의 시간 복잡도를 가지며 랜덤 접근(Random Access)가 가능하다. 삽입과 삭제는 O(n)이 걸린다. 따라서 데이터 추가와 삭제를 많이 하는 것은 연결 리스트, 접근(참조)을 많이 하는 것은 배열로 하는 것이 좋다.

랜덤 접근과 순차적 접근

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

<그림>

배열과 연결 리스트의 차이점은 무엇일까?

배열은 상자를 순서대로 나열한 데이터 구조이며, 몇 번째 상자이지만 알면 해당 상자의 요소를 끄집어 낼 수 있다. 연결 리스트는 상자를 선으로 연결한 형태의 데이터 구조이며, 상자 안의 요소를 알기 위해서는 하나씩 상자 내부를 확인해봐야 한다는 점이 다르다.

n번째 요소의 접근(참조)은 배열이 빠르고 연결 리스트는 느리다. 왜냐하면 배열의 경우에는 그저 상자 위에 있는 요소를 접근하면 되기 때문에 O(1)의 시간 복잡도를 가지고, 연결 리스트는 매번 상자를 열어야 하고 주어진 선을 기반으로 순차적으로 열어야 하기 때문에 접근(참조)의 경우 O(n)의 시간 복잡도를 가진다.

즉 참조가 많이 일어나는 작업의 경우 배열이 빠르고 연결 리스트가 느리다.

하지만 데이터 추가 및 삭제는 연결 리스트가 더 빠르고 배열은 느리다. 배열은 모든 상자를 앞으로 옮겨야 추가가 가능하지만, 연결 리스트는 선을 바꿔서 연결해주기만 하면 된다.

벡터(Vector)

벡터(Vector)는 동적으로 요소를 할당할 수 있는 동적 배열이다. 컴파일 시점에서 개수를 모른다면 벡터를 써야 한다.

중복을 허용하고 순서가 있고 랜덤 접근이 가능하다. 탐색과 맨 뒤의 요소를 삭제하거나 삽입하는데 O(1)이 걸리며, 맨 뒤가 아닌 요소를 삭제하고 삽입하는 데 O(n)의 시간이 걸린다.

스택(Stack)

스택(Stack)은 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질(LIFO, Last In Firest Out)을 가진 자료구조이다. 재귀적인 함수, 알고리즘에 사용되며 웹 브라우저 방문 기록등에서 사용된다. 시간 복잡도로는 삽입 및 삭제에서 O(1)과 탐색에서는 O(n)이 걸린다.

큐(Queue)

큐(Queue)는 먼저 집어넣은 데이터가 먼저 나오는 성질(FIFO, First In First Out)을 지닌 자료구조이다. 나중에 집어넣은 데이터가 먼저 나오는 스택과는 반대되는 개념을 가졌다. 시간 복잡도로는 삽임 및 삭제에서 O(1)과 탐색에서는 O(n)이 걸린다. CPU 작업을 기다리는 프로세스나 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시 등에서 사용된다.