# 연결 리스트(linked-list)
## 목차
1. 연결 리스트란?
2. 장점
3. 단점
4. 종류
5. 구현
## 1. 연결 리스트란?
연결 리스트란 노드(`node`)의 연결로 이루어진 리스트이다. (리스트: 공백없는 데이터의 나열)
![Imgur](https://i.imgur.com/SoqvrjB.png)
## 2. 장점
1. 데이터의 삽입 삭제 연산이 빠름. `O(1)` <---> 배열: O(n)
2. 리스트 내, 데이터 이동 없음.
3. 큰 메모리공간 필요하지 않음.
## 3. 단점
1. n번째 노드 접근시 `O(n)` 지연 발생. <---> 배열: O(1)
2. 포인터로 인한 메모리 낭비.
## 4. 종류
1. singly linked-list
![Imgur](https://i.imgur.com/SoqvrjB.png)
2. doubly linked-list
![Imgur](https://i.imgur.com/ElsBdWD.png)
3. circularly linked-list
![Imgur](https://i.imgur.com/D5UZnnv.png)
## 5. 구현
아래 명세서를 만족하는 단일 연결 리스트(`Singly Linked List`)를 구현해보자.
### 5.1 명세
단일 연결 리스트는 아래의 명세를 만족한다.
+ 데이터를 순서 기준(0부터 시작)으로 다룬다.
+ 데이터의 시작점을 `head`로 가리킨다.
+ 데이터는 노드(`node`)에 담아 보관한다.
+ i번째 위치에 데이터를 추가 및 삭제 할 수 있다.
+ 모든 노드를 차례대로 출력한다.
### 5.2 설계
![Imgur](https://i.imgur.com/RsHYtUq.png)
### 5.3 코드
코드는 아래의 실습문제를 통해 연습해보자.