> For the complete documentation index, see [llms.txt](https://krjaeh0.gitbook.io/j-log/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://krjaeh0.gitbook.io/j-log/programming/cs-fundamentals/overviews/datastructuresalgorithms/lineardatastructureoverview.md).

# LinearDataStructureOverview

## 선형 자료 구조(Linear Data Structure)란?

* 데이터가 순차적으로 배치되어 있으며, 한 방향으로만 탐색이 가능한 구조를 의미
* 데이터가 직선 형태로 저장되며, 인접한 요소 간 관계를 유지하는 구조

✔ 데이터가 선형(순차적)으로 연결됨\
✔ 인접한 요소 간 관계가 명확하여 탐색이 용이함\
✔ 배열, 연결 리스트, 스택, 큐 등이 대표적인 선형 자료 구조

***

## 선형 자료 구조의 종류

| 자료 구조 유형                      | 설명                             | 접근 방식                |
| ----------------------------- | ------------------------------ | -------------------- |
| 배열 (Array)                    | 고정된 크기의 연속된 메모리 블록에 데이터를 저장    | 인덱스 기반 접근 (O(1))     |
| 연결 리스트 (Linked List)          | 각 요소가 다음 요소를 가리키는 포인터를 포함하는 구조 | 순차적 접근 (O(n))        |
| 스택 (Stack)                    | 후입선출(LIFO) 방식의 자료 구조           | 마지막 요소만 접근 가능 (O(1)) |
| 큐 (Queue)                     | 선입선출(FIFO) 방식의 자료 구조           | 처음 요소만 접근 가능 (O(1))  |
| 덱 (Deque, Double-ended Queue) | 양쪽에서 삽입/삭제가 가능한 큐              | 양방향 접근 가능 (O(1))     |

배열과 연결 리스트는 기본적인 선형 자료 구조이며, 스택과 큐는 배열 또는 연결 리스트를 활용하여 구현됨

***

## 배열 (Array)

* 연속된 메모리 블록에 동일한 자료형의 데이터를 저장하는 구조
* 인덱스를 사용하여 O(1)의 빠른 데이터 접근이 가능
* 배열 크기는 선언 시 고정되어 있으며, 삽입/삭제가 비효율적(O(n))

배열의 주요 연산

| 연산                   | 시간 복잡도 |
| -------------------- | ------ |
| 검색 (Access by Index) | O(1)   |
| 탐색 (Search)          | O(n)   |
| 삽입 (Insert)          | O(n)   |
| 삭제 (Delete)          | O(n)   |

{% code title="C 예시" %}

```c
int arr[5] = {10, 20, 30, 40, 50};
printf("%d", arr[2]);  // 30 출력
```

{% endcode %}

{% hint style="info" %}
장점: 인덱스를 사용하여 빠르게 데이터 접근 가능 (O(1))\
단점: 크기가 고정적이며, 삽입/삭제가 비효율적 (O(n))
{% endhint %}

***

## 연결 리스트 (Linked List)

* 각 노드(Node)가 데이터와 다음 노드를 가리키는 포인터를 포함하는 동적 자료 구조
* 동적 할당이 가능하여 크기가 가변적
* 배열보다 삽입/삭제가 빠르지만, 탐색 속도가 느림 (O(n))

연결 리스트의 주요 연산

| 연산                     | 시간 복잡도 |
| ---------------------- | ------ |
| 탐색 (Search)            | O(n)   |
| 삽입 (Insert, Head/Tail) | O(1)   |
| 삭제 (Delete, Head/Tail) | O(1)   |

{% code title="C 구조체 예시" %}

```c
typedef struct Node {
    int data;
    struct Node* next;
} Node;
```

{% endcode %}

{% hint style="info" %}
장점: 크기가 가변적이며, 삽입/삭제가 빠름 (O(1))\
단점: 탐색 속도가 느림 (O(n)), 추가적인 포인터 메모리 사용
{% endhint %}

***

## 스택 (Stack)

* 후입선출(LIFO, Last In First Out) 방식의 자료 구조
* 마지막에 삽입된 요소가 가장 먼저 제거됨
* 배열 또는 연결 리스트로 구현 가능

스택의 주요 연산

| 연산          | 시간 복잡도 |
| ----------- | ------ |
| 삽입 (Push)   | O(1)   |
| 삭제 (Pop)    | O(1)   |
| 탐색 (Search) | O(n)   |

{% code title="C 예시" %}

```c
#define SIZE 100
int stack[SIZE], top = -1;

void push(int value) {
    stack[++top] = value;
}
int pop() {
    return stack[top--];
}
```

{% endcode %}

{% hint style="info" %}
장점: 빠른 삽입/삭제 (O(1)), 메모리 효율적\
단점: 중간 요소 접근이 불가능 (O(n))
{% endhint %}

***

## 큐 (Queue)

* 선입선출(FIFO, First In First Out) 방식의 자료 구조
* 먼저 들어온 데이터가 먼저 제거됨
* 배열 또는 연결 리스트로 구현 가능

큐의 주요 연산

| 연산           | 시간 복잡도 |
| ------------ | ------ |
| 삽입 (Enqueue) | O(1)   |
| 삭제 (Dequeue) | O(1)   |
| 탐색 (Search)  | O(n)   |

{% code title="C 예시" %}

```c
#define SIZE 100
int queue[SIZE], front = 0, rear = 0;

void enqueue(int value) {
    queue[rear++] = value;
}
int dequeue() {
    return queue[front++];
}
```

{% endcode %}

{% hint style="info" %}
장점: 빠른 삽입/삭제 (O(1)), 일정한 처리 순서 유지\
단점: 중간 요소 접근이 불가능 (O(n))
{% endhint %}

***

## 덱 (Deque, Double-ended Queue)

* 큐와 비슷하지만, 양쪽 끝에서 삽입과 삭제가 가능
* 배열 또는 연결 리스트로 구현 가능
* 일반 큐보다 더 유연한 구조

덱의 주요 연산

| 연산                | 시간 복잡도 |
| ----------------- | ------ |
| 앞 삽입 (Push Front) | O(1)   |
| 뒤 삽입 (Push Back)  | O(1)   |
| 앞 삭제 (Pop Front)  | O(1)   |
| 뒤 삭제 (Pop Back)   | O(1)   |

{% hint style="info" %}
장점: 큐보다 더 유연한 데이터 처리 가능\
단점: 구현이 더 복잡함
{% endhint %}

***

## 선형 자료 구조 비교

| 자료 구조                | 접근 속도 | 삽입 속도 | 삭제 속도 | 특징           |
| -------------------- | ----- | ----- | ----- | ------------ |
| 배열 (Array)           | O(1)  | O(n)  | O(n)  | 고정 크기, 빠른 접근 |
| 연결 리스트 (Linked List) | O(n)  | O(1)  | O(1)  | 동적 크기, 느린 탐색 |
| 스택 (Stack)           | O(n)  | O(1)  | O(1)  | 후입선출(LIFO)   |
| 큐 (Queue)            | O(n)  | O(1)  | O(1)  | 선입선출(FIFO)   |
| 덱 (Deque)            | O(n)  | O(1)  | O(1)  | 양방향 큐        |

***

## 정리

* 선형 자료 구조는 데이터가 순차적으로 배치되는 구조
* 배열은 빠른 접근이 가능하지만 크기가 고정됨
* 연결 리스트는 동적 크기를 가지지만 탐색 속도가 느림
* 스택과 큐는 특정한 데이터 처리 방식(LIFO, FIFO)을 따름
* 덱은 양쪽 끝에서 삽입/삭제가 가능한 확장된 큐


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://krjaeh0.gitbook.io/j-log/programming/cs-fundamentals/overviews/datastructuresalgorithms/lineardatastructureoverview.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.