# 연결 리스트(Linked List)

---

## 연결 리스트(Linked List)

데이터 구조의 한 종류로 여러개의 값을 저장하기 위한 구조 
데이터와 포인터가 한 쌍으로 구성된 것이 특징으로, 포인터가 다음 데이터의 메모리 위치를 가리킨다. 

![linked_list](linked_list.png) 

리스트에선 데이터가 메모리상의 떨어진 영역에 흩어져서 저장된다. 
흩어져 저장돼 있으므로 포인터를 처음부터 순서대로 따라가야만 원하는 데이터에 접근할 수 있다. 

데이터의 추가는 추가할 위치의 앞뒤 포인터를 변경만 하면 되므로 간단하다고 볼 수 있다. 

### 시간복잡도

| | Linked List |
| :------------------------------: | :---------: |
| **Access** | O(n) |
| **Insert/Remove from beginning** | O(1) |
| **Insert/Remove from end** | O(n) |
| **Insert/Remove from middle** | O(n) |

## ref

- [pngwing](https://www.pngwing.com/en/free-png-czavz)
- [McKenzie - Arrays, Linked Lists, and Big O Notation](https://medium.com/@mckenziefiege/arrays-linked-lists-and-big-o-notation-486727b6259b)
- [알고리즘 도감](https://apps.apple.com/kr/app/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8F%84%EA%B0%90/id1047532631)

자료구조 - 연결 리스트(Linked List)

연결 리스트(Linked List)

# 큐(Queue)

---

## 큐(Queue)

데이터 구조의 한 종류, **대기행렬**이라 불리며 줄 서있는 행렬을 생각하면 이해하기 쉽다. 
행렬에서는 새롭게 온 사람이 가장 뒤에 서며 가장 앞에 있는 사람부터 순서대로 처리된다. 

![queue](queue.png) 

큐에 데이터를 추가하면 가장 뒤에 추가된다. 큐에 데이터를 추가하는 작업을 **엔큐(enqueue)** 라고 한다. 
큐에 데이터를 꺼낼 때는 가장 늦게 추가된 데이터부터 꺼낸다. 큐에서 데이터를 꺼내는 작업을 **디큐(dequeue)** 라고 한다. 
먼저 넣는 것을 먼저 꺼내는 구조를 "First In First Out"이라고 하며 앞글자만 따서 "FIFO"라고도 한다. 

### 시간복잡도

| Operation | Average | Worst |
| :--------: | :-----: | :---: |
| **Access** | O(n) | O(n) |
| **Search** | O(n) | O(n) |
| **Insert** | O(1) | O(1) |
| **Delete** | O(1) | O(1) |

## ref

- [sbinha - 스택, 큐(Stack, Queue)](https://velog.io/@sbinha/%EC%8A%A4%ED%83%9D-%ED%81%90)
- [Hongwoo - [자료구조] 스택(Stack)](https://propercoding.tistory.com/18)
- [알고리즘 도감](https://apps.apple.com/kr/app/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8F%84%EA%B0%90/id1047532631)

큐(Queue)

# 스택(Stack)

---

## 스택(Stack)

데이터 구조의 한 종류, 물건을 세로로 쌓는다고 생각하면 이해하기 쉬운 구조이다. 
세로로 쌓인 물건들 중에 하나를 꺼내려면 위에서부터 차례대로 꺼내야한다.

스택에 데이터를 추가할 때는 가장 위에 추가된다. 
스택에 데이터를 추가하는 작업을 푸시(push)라고 한다. 
 

![push](push.png)

<center>push</center>

스택에서 데이터를 꺼내는 경우 가장 위, 즉 가장 최근에 추가된 데이터부터 차례대로 꺼낸다. 
스택에서 데이터를 꺼내는 작업을 팝(pop)이라고 한다. 
 

![pop](pop.png)

<center>pop</center>

이처럼 나중에 넣은 것을 먼저 꺼내는 구조를 "Last In First Out"이라고 하며, 앞글자만 따서 "LIFO"라고 한다. 

### 시간복잡도

| Operation | Average | Worst |
| :--------: | :-----: | :---: |
| **Access** | O(n) | O(n) |
| **Search** | O(n) | O(n) |
| **Insert** | O(1) | O(1) |
| **Delete** | O(1) | O(1) |

## ref

- [sbinha - 스택, 큐(Stack, Queue)](https://velog.io/@sbinha/%EC%8A%A4%ED%83%9D-%ED%81%90)
- [Hongwoo - [자료구조] 스택(Stack)](https://propercoding.tistory.com/17)
- [알고리즘 도감](https://apps.apple.com/kr/app/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8F%84%EA%B0%90/id1047532631)