선형 자료 구조

1. 선형 자료 구조

1-1. 정의

선형 자료구조란 요소가 일렬로 나열되어 있는 자료구조를 말한다.

데이터가 선형적으로 연결되어 있기 때문에 데이를 쉽게 삽입하고 삭제할 수 있으며, 순차적으로 데이터에 접근하는데 유리하다.

선형 자료구조의 종류로는 연결 리스트, 배열, 백터(동적 배열), 스택, 큐, 덱 등이 있다.

2. 연결 리스트(Linked List)

2-1. 정의

각 노드가 데이터와 다음 요소의 주소값을 가리키는 포인터로 연결되어 있는 구조다.

2-2. 종류

연결리스트의 종류로는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 있다.

단일 연결 리스트 (Singly Linked List)

• 각 노드가 데이터와 다음 노드의 주소값를 가리키는 포인터(next)로 연결되어 있다.
• 마지막 노드의 포인터는 NULL 값이다.

이중 연결 리스트 (Doubly Linked List)

• 각 노드가 데이터와 이전 노드의 주소값을 가리키는 포인터(prev)와 다음 노드의 주소값을 가리키는 포인터(next)로 연결되어 있다.
• 역방향으로 노드에 접근할 수 있다.

원형 연결 리스트 (Circular Linked List)

• 각 노드가 데이터와 다음 노드의 주소값을 가리키는 포인터(next)로 연결되어 있으며, 마지막 노드는 헤드 노드의 주소값을 가리킨다.

2-3. 시간복잡도

[접근] Access and Search
n번째 인덱스에 해당하는 값에 접근

[탐색] Traversal 

원소 탐색 및 접근 O(n)

• 우리는 헤드 노드의 값만 알고 있는 상태기 때문에 다음 노드가 어디에 위치하는지 포인터를 타고 들어가야 한다.

원소 삽입 및 삭제 O(1) or O(n)

• 단 해당 원소의 주소값을 알고 있는 경우에만 O(1)이다. 해당 원소의 주소값을 알고 있는 경우 원소의 next 포인터가 가리키는 주소만 변경해주면 되기 때문이다.

• 해당 원소의 주소값을 모르는 경우 원소에 접근하는 시간도 고려해야 하기 때문에 O(n)이 나온다.

따라서 연결리스트는 원소의 삽입과 삭제가 빈번한 경우 유용하게 사용될 수 있다는 것을 알 수 있다.

3. 배열 (Array)

3-1. 정의

배열은 동일한 데이터 타입을 가진 요소를 일렬로 나열해 메모리에 연속적으로 저장하는 구조다.

메모리에 연속적으로 데이터가 배치되기 때문에 인덱스를 통해 빠른 접근이 가능하다. 그러나 크기가 고정되어 있기 때문에 요소를 추가하거 삭제할 경우 데이터의 이동이 필요해 연결리스트보다 많은 비용이 든다.

코딩 테스트에서 내가 주로 사용하는 파이썬이라는 언어는 처음부터 배열의 길이를 정해놓지 않는다.
이는 동적 배열(Dynamic Array)로, 밑에서 따로 다룰 것이다.

3-2. 시간 복잡도

원소 접근 O(1)

• 찾고자 하는 값이 몇 번째 인덱스에 있는지 알고 있다면 빠르게 탐색할 수 있다.

원소 탐색 O(n)

• 찾고자 하는 값의 인덱스를 알지 못할 때 순차적으로 검색해 나가야 한다.

원소 삽입 및 삭제 O(n) or O(1)

• 배열의 원소는 메모리상에 연속적으로 배치되어 있기 때문에 삽입 또는 삭제가 발생하면 해당 위치에 있는 모든 원소를 한 칸씩 이동시켜야 한다.

• 추가 및 삭제하려는 데이터의 위치가 맨 뒤이고 배열에 공간이 남아있다면 O(1)이다.

따라서 배열은 해당하는 원소를 빠르게 접근해야 하는 경우 배열 쓰면 연결 리스트보다 훨씬 효율적이다.

4. 순차 접근과 직접 접근

4-1. 순차 접근 (Sequential Access)

데이터를 순서대로 하나씩 접근하는 방식이다.

순차 접근은 데이터가 메모리에 연속적으로 배치되지 않은 연결 리스트와 같은 자료구조에서 사용된다. 헤드 노드부터 순차적으로 탐색해야 원하는 위치의 값을 얻을 수 있기 때문이다.

4-2. 직접 접근 (Direct Access)

인덱스나 주소를 통해 원하는 위치의 데이터에 바로 접근하는 방식이다.

데이터의 인덱스를 알고있을 때, 해당 인덱스를 이용해 빠르게 접근할 수 있다.

직접 접근은 주로 배열과 메모리에 연속적으로 데이터가 배치되어 있는 자료구조에 사용된다. 데이터가 연속적으로 배치되어 있기 때문에 인덱스만 알면 원하는 데이터에 바로 접근할 수 있기 때문이다.

5. 동적 배열, 벡터(Vector)

5-1. 정의

배열과 마찬가지로 요소들을 순차적으로 저장하며, 크기가 동적으로 조정될 수 있는 구조다.

동적 배열은 동적인 크기를 갖기 때문에 요소를 추가하거나 삭제할 때 메모리를 적절하게 관리해 메모리를 효율적으로 사용할 수 있다.

5-2. 시간복잡도

원소 접근 O(1)

• 찾고자 하는 값이 몇 번째 인덱스에 있는지 알고 있다면 빠르게 탐색할 수 있다.

원소 탐색 O(n)

• 찾고자 하는 값의 인덱스를 알지 못할 때 순차적으로 검색해 나가야 한다.

원소 삽입 및 삭제

• 마지막에 값을 삽입하거나 삭제하는 경우 O(1)의 시간이 걸린다.

• 첫 번째에 값을 삽입하거나 삭제하는 경우 O(n)의 시간이 걸린다.

• i번 째에 값을 삽입하거나 삭제하는 경우 O(n)의 시간이 걸린다.

5-3. Amortized 복잡도

추가 작업이 발생하는 경우, 추가 작업을 고려해 전체 작업을 진행할 때 평균적으로 얼마나 오랜 시간이 걸리는지 평가하는 것이다.

동적 배열에서 뒤에서부터 원소를 추가하는 경우 O(1)의 시간 복잡도를 갖는다.

뒤에서 원소를 삽입할 때 할당된 공간을 모두 소모한 경우 더 큰 새로운 배열을 할당하고 기존 배열의 원소를 새로운 배열로 복사해야 하는 작업이 필요하다. 이러한 경우 배열의 크기에 비례하여 작업 시간이 증가하는데, 동적 배열의 경우 이러한 추가 작업 시간에 드는 비용이 모든 작업에 분산되어 결론적으로 삽입 작업당 필요한 추가적인 시간이 크게 늘지 않는다.

결론적으로 원소를 추가할 때 보통은 할당된 공간에 원소를 추가하는 작업을 진행하고 할당된 공간을 모두 사용해 새로운 배열을 할당받고 기존 원소를 복사하는 작업은 빈번하게 일어나지 않기 때문에 전체 삽입 작업 시간을 고려했을 때 시간복잡도가 크게 증가하지 않는다.

6. 스택 (Stack)

6-1. 정의

가장 마지막에 들어간 원소가 가장 처음으로 나오는 후입선출, LIFO (Last In First Out) 자료구조다.

6-2. 시간복잡도

원소 접근 O(1)

• 스택은 후입선출 구조기 때문에 원소의 접근은 맨 위에 위치한 원소에 대해서만 이루어진다.

원소 탐색 O(n)

• 스택은 데이터를 임시적으로 저장하고 처리하는 용도기 때문에 탐색 연산이 허용되지 않는다. 만약 스택에서 특정 원소를 찾는다면 pop()을 통해 원소를 하나씩 빼가면서 확인해야 한다.

원소 삽입 및 삭제 O(1)

• 스택의 맨 위의 원소를 삭제하고, 맨 위에 원소를 추가할 수 있다.

7. 큐 (Queue)

6-1. 정의

가장 처음에 들아간 원소가 가장 처음으로 나오는 선입선출, FIFO (First In First Out) 자료구조다.

큐의 뒤쪽에 데이터를 넣는 작업을 Enqueue, 큐의 앞쪽 데이터를 제거하는 작업을 Dequeue라고 한다. 큐가 비어있는 경우 Dequeue 작업은 실패한다.

6-2. 시간복잡도

원소 접근 O(1)

• 큐는 선입선출 구조기 때문에 원소의 접근은 맨 앞에 위치한 원소에 대해서만 이루어진다.

원소 탐색 O(n)

• 스택에 이어 큐도 데이터를 임시적으로 저장하고 처리하는 용도기 때문에 탐색 연산이 허용되지 않는다. 큐에서 특정 원소를 찾기 위해서는 큐를 모두 순회해야 한다.

원소 삽입 및 삭제 O(1)

• 큐의 맨 앞의 원소를 삭제하고, 맨 뒤에 원소를 추가할 수 있다.

8. 덱 (Deque)

8-1. 정의

Double-Ended Queue의 약어로 양쪽 끝에서 삽입과 삭제가 모두 가능한 선형 자료구조다.

덱은 큐와 스택의 특징을 결합한 자료구조로, 선입선출과 후입선출을 모두 지원한다.

8-2. 시간복잡도

원소 접근 O(n)

• 특정 위치의 원소에 직접 접근하는 기능을 제공하지 않는다. 따라서 원소 접근을 하기 위해서는 덱의 앞과 뒤에서 원소를 하나씩 빼가면서 찾아야 한다.

원소 탐색 O(n)

• 스택, 큐와 마찬가지로 원소를 탐색하는 연산은 일반적으로 지원되지 않는다. 원소를 탐색하려면 덱을 모두 순회해야 한다.

원소 삽입 및 삭제 O(1)

• 앞과 뒤 양쪽에서 원소를 삽입하거나 삭제할 수 있다.