선형자료구조

youngkyu MIn·2023년 12월 9일

선형자료구조

선형 자료구조는 데이터 요소들이 순차적이고 연속적인 형태로 구성되어 있는 자료구조다. 이러한 자료구조에서는 각 데이터 요소가 선형적으로 나열되며, 각 요소는 정확히 하나의 이전 요소와 하나의 다음 요소(1:1)와 연결되어 있다. 선형 자료구조는 데이터를 저장하고 처리하는 데 있어서 단순하고 효율적인 방법을 제공한다. 선형 자료구조의 대표적인 예로는 배열, 연결 리스트, 스택, 큐 등이 있다.

빠른 인덱스 기반의 접근이 필요한 경우 배열을 사용할 수 있고, 데이터의 추가 및 제거가 빈번한 경우 연결 리스트나 덱을 사용할 수 있다.

배열

장점

고정 크기: 배열은 고정된 크기를 가지며, 이는 메모리 관리를 용이하게 한다. 배열이 메모리에 연속적으로 할당되기 때문에, 고정된 크기를 통해 메모리를 효율적으로 사용할 수 있다.
빠른 접근: 배열의 각 요소는 인덱스를 통해 빠르게 접근할 수 있다. 이는 배열이 연속적인 메모리 공간에 저장되기 때문에, 인덱스를 사용하여 O(1) 시간 복잡도로 특정 요소에 접근할 수 있다.
단순성과 효율성: 배열은 사용하기 쉽고, 이해하기 쉬운 자료구조다. 기본적인 데이터 저장 및 접근 방법을 제공하므로, 다양한 알고리즘과 프로그램에서 활용된다.

단점

고정된 크기: 배열은 크기가 고정되어 있어, 크기를 동적으로 변경할 수 없다. 배열이 꽉 찼을 때 추가 데이터를 저장하려면, 더 큰 배열을 생성하고 기존 데이터를 새 배열로 복사해야 한다.
메모리 낭비: 때때로 배열의 모든 공간을 사용하지 않을 수 있다. 이는 배열이 최대 크기만큼의 메모리를 할당받기 때문에, 실제 사용되지 않는 공간에 대한 메모리가 낭비될 수 있다.
복잡한 삽입/삭제 작업: 배열에서 요소를 삽입하거나 삭제하는 작업은 복잡할 수 있다. 특히, 배열의 중간에 요소를 삽입하거나 삭제할 경우, 나머지 요소들을 이동시켜야 한다.

연결 리스트 (Linked List)

장점

동적 크기: 연결 리스트는 동적으로 크기가 조정된다. 즉, 프로그램 실행 중에 요소를 추가하거나 제거함으로써 리스트의 크기를 변경할 수 있다. 이는 배열과 대조적으로, 배열은 고정된 크기를 가진다.
효율적인 삽입 및 삭제: 연결 리스트에서 요소를 삽입하거나 삭제하는 작업은 매우 효율적이다. 리스트의 중간에 요소를 삽입하거나 제거할 때, 해당 노드의 포인터만 조정하면 된다. 배열에서는 요소를 삽입하거나 삭제할 때 나머지 요소들을 이동시켜야 하는 반면, 연결 리스트에서는 이런 작업이 필요 없다.
메모리 효율성: 연결 리스트는 필요할 때마다 메모리를 할당한다. 따라서 사용하지 않는 메모리를 미리 할당할 필요가 없어 메모리를 효율적으로 사용할 수 있다.

단점

느린 검색 시간: 연결 리스트에서 특정 요소에 접근하기 위해서는 처음부터 해당 요소까지 순차적으로 탐색해야 한다. 이는 O(n)의 시간 복잡도를 가지며, 배열의 빠른 인덱스 접근(O(1))과 비교된다.
추가적인 메모리 사용: 각 요소(노드)는 데이터 뿐만 아니라 다음 노드를 가리키는 포인터도 저장해야 한다. 이로 인해 연결 리스트는 배열에 비해 더 많은 메모리를 사용한다.
메모리 할당의 오버헤드: 연결 리스트의 각 요소는 독립적으로 메모리에 할당되므로, 메모리 할당과 해제에 대한 오버헤드가 발생할 수 있다. 배열은 처음에 한 번에 메모리가 할당되지만, 연결 리스트는 각 노드마다 개별적으로 메모리 할당이 이루어진다.

스택 (Stack)

자바에서 스택(Stack)은 후입선출(LIFO, Last In First Out) 원칙을 따른다. 이는 가장 마지막에 삽입된 요소가 가장 먼저 제거된다는 의미로 일상생활에서 책을 쌓아 놓은 것과 같은 형태로 생각할 수 있다. 새로운 요소는 맨 위에 추가되고, 요소는 항상 맨 위에서 제거된다.

주요 연산

push: 스택의 맨 위에 요소를 추가한다.
pop: 스택의 맨 위에서 요소를 제거하고 반환한다.
peek: 스택의 맨 위에 있는 요소를 반환하지만, 제거하지는 않는다.
isEmpty: 스택이 비어 있는지 확인한다.

자바에서는 java.util.Stack 클래스를 사용하여 스택을 구현할 수 있다. 하지만, Stack 클래스는 Vector를 상속받기 때문에 성능 면에서 비효율적일 수 있다. 그래서 실제로는 Deque 인터페이스를 구현한 ArrayDeque 클래스를 스택으로 사용하는 것이 더 권장된다.

큐 (Queue)

자바에서 큐(Queue)는 선입선출(First In First Out, FIFO) 원칙을 따르는 선형 자료구조다. 이 원칙에 따라, 큐에 먼저 추가된 요소가 먼저 제거된다. 큐는 일상 생활에서 줄을 서는 것과 유사한 개념으로, 첫 번째로 줄을 선 사람이 첫 번째로 서비스를 받는 것과 같다.

주요 연산

offer: 큐의 끝에 요소를 추가한다.
poll: 큐의 첫 번째 요소를 제거하고 반환한다. 큐가 비어 있으면 null을 반환한다.
peek: 큐의 첫 번째 요소를 반환하지만, 제거하지는 않는다.
isEmpty: 큐가 비어 있는지 확인한다.

자바에서는 java.util.Queue 인터페이스를 사용하여 큐를 구현한다. 이 인터페이스는 LinkedList, PriorityQueue 등 다양한 클래스에 의해 구현된다. 일반적인 사용을 위해서는 LinkedList가 자주 사용되며, 우선순위가 중요한 경우 PriorityQueue를 사용할 수 있다.

덱 (Deque, Double-Ended Queue)

주요 연산

addFirst / offerFirst: 덱의 앞쪽에 요소를 추가한다.
addLast / offerLast: 덱의 뒤쪽에 요소를 추가한다.
removeFirst / pollFirst: 덱의 앞쪽에서 요소를 제거하고 반환한다.
removeLast / pollLast: 덱의 뒤쪽에서 요소를 제거하고 반환한다.
getFirst / peekFirst: 덱의 첫 번째 요소를 확인한다.
getLast / peekLast: 덱의 마지막 요소를 확인한다.

자바에서는 java.util.Deque 인터페이스를 통해 덱을 구현한다. 이 인터페이스는 ArrayDeque, LinkedList 등과 같은 클래스에 의해 구현된다. ArrayDeque는 배열 기반의 덱 구현체이며, LinkedList는 연결 리스트 기반의 덱 구현체다.

활용

덱은 스택 또는 큐로 사용될 수 있으며, 양쪽 끝에서의 유연한 작업으로 인해 다양한 알고리즘과 데이터 구조 문제에 적용될 수 있다. 예를 들어, 스크롤링 버퍼, 탐색 알고리즘, 캐시 구현 등에서 덱을 사용할 수 있다.

자바에서는 ArrayDeque 클래스를 사용하는 것이 일반적이다. 이 클래스는 내부적으로 동적 배열을 사용하여 요소를 관리하며, 배열 기반의 덱으로서 높은 성능을 제공한다. LinkedList 또한 덱을 구현하지만, 일반적으로 ArrayDeque가 더 빠른 성능을 보인다.