선형 자료구조(Linear Data Structure)

 

선형 자료구조(Linear Data Structure)

선형 자료구조는 데이터 요소들이 일렬로 배치되어 있는 자료구조를 의미합니다. 이러한 자료구조에서 데이터 요소는 순서를 가지며, 각각의 요소는 바로 이전 요소와 바로 다음 요소와 관련이 있습니다. 선형 자료구조는 데이터를 순차적으로 접근하고 조작하는데 유용하며, 간단한 구조로서 다양한 알고리즘과 응용 분야에서 활용됩니다.

여러 가지 선형 자료구조의 예시와 특징을 살펴보겠습니다

1. 배열 (Array)
   - 가장 기본적인 선형 자료구조로, 동일한 데이터 타입의 요소들을 순차적으로 저장합니다.
   - 인덱스를 사용하여 각 요소에 접근하고, 특정 위치에 요소를 삽입, 삭제할 수 있습니다.
   - 데이터 검색과 접근이 빠르지만, 중간에 요소를 삽입하거나 삭제할 경우 데이터 이동이 필요하므로 비효율적일 수 있습니다.

2. 연결 리스트 (Linked List)
   - 노드(Node)들이 연결된 구조로 데이터를 저장합니다.
   - 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성됩니다.
   - 데이터의 삽입과 삭제가 빠르며, 동적으로 크기를 조정할 수 있습니다.
   - 하지만 특정 위치의 요소에 접근하려면 처음부터 순회해야 하므로 검색이 상대적으로 느릴 수 있습니다.

3. 스택 (Stack)
   - 후입선출(LIFO, Last-In-First-Out) 원칙을 따르는 자료구조입니다.
   - 요소를 스택의 맨 위에 삽입하거나 삭제할 수 있습니다.
   - 주로 함수 호출, 재귀 알고리즘 등에서 사용됩니다.

4. 큐 (Queue)
   - 선입선출(FIFO, First-In-First-Out) 원칙을 따르는 자료구조입니다.
   - 요소를 큐의 뒤에 삽입하고 앞에서 삭제할 수 있습니다.
   - 프로세스 스케줄링, 작업 대기열 등에서 사용됩니다.

5. 데크 (Deque, Double-Ended Queue)
   - 양쪽 끝에서 삽입과 삭제가 가능한 자료구조입니다.
   - 큐와 스택의 특성을 결합한 것으로, 다양한 상황에서 유용합니다.

6. 선형 배열 (Vectors)
   - 배열과 유사하지만 동적으로 크기를 조정할 수 있는 동적 배열 자료구조입니다.
   - 배열의 장점과 연결 리스트의 장점을 조합한 것으로, 요소의 삽입, 삭제, 검색이 효율적입니다.

선형 자료구조는 데이터의 순서를 중요하게 다루며, 각각의 특징과 장단점에 따라 다양한 상황에서 적절한 선택이 필요합니다.

 

 

 

선형 자료구조의 삽입/삭제/검색

선형 자료구조인 배열, 연결 리스트, 스택, 큐 등을 삽입/삭제/검색의 측면에서 비교하면서 각각의 장단점을 살펴보겠습니다.

1. 배열 (Array)
   - 장점
     - 인덱스를 사용하여 빠르게 요소에 접근 가능 (O(1)).
     - 메모리가 연속적으로 할당되므로 캐시 활용에 유리할 수 있음.
   - 단점
     - 요소의 삽입/삭제 시 해당 위치의 요소를 이동해야 하므로 비효율적 (최악의 경우 O(n)).
     - 크기가 고정되어 동적으로 크기를 조정하기 어려움.

2. 연결 리스트 (Linked List)
   - 장점
     - 삽입/삭제가 빠르고 효율적 (O(1)), 노드만 수정하면 되므로 데이터 이동 없음.
     - 동적으로 크기를 조정 가능.
   - 단점
     - 검색 시 처음부터 순회해야 하므로 느릴 수 있음 (O(n)).
     - 추가적인 메모리를 사용하여 포인터로 인한 오버헤드가 발생.

3. 스택 (Stack)
   - 장점
     - 후입선출(LIFO)으로 삽입/삭제가 빠르고 간단 (O(1)).
     - 함수 호출, 재귀 등에서 활용 가능.
   - 단점
     - 스택의 맨 위에 있는 요소에만 접근 가능하므로 중간의 요소에 접근하기 어려움.
     - 크기 제한이 있는 경우 메모리 오버플로우 가능성 있음.

4. 큐 (Queue)
   - 장점
     - 선입선출(FIFO)로 삽입/삭제가 빠르고 간단 (O(1)).
     - 프로세스 스케줄링, 작업 대기열 등에서 활용 가능.
   - 단점
     - 큐의 앞부분에 있는 요소에만 접근 가능하므로 중간의 요소에 접근하기 어려움.
     - 크기 제한이 있는 경우 메모리 오버플로우 가능성 있음.

5. 데크 (Deque, Double-Ended Queue)
   - 장점
     - 양쪽 끝에서 삽입/삭제가 빠르고 간단 (O(1)).
     - 큐와 스택의 특성을 결합하여 다양한 상황에 활용 가능.
   - 단점
     - 중간의 요소에 접근하기 어려울 수 있음.
     - 데크의 구현에 따라 메모리 사용량이 증가할 수 있음.