Data Structure(2) Linked List

1. Linked List

'"연결 리스트"는 Node들로 구성이 되어있다.
Ex. [Node] - [Node] - [Node] - [Node]

"연결 리스트" : 강강수월래를 일자로 편 것과 같다. 
* 사용 예시 : 플레이 리스트, 이미지 뷰어, 등등. 
* 검색 키워드 : linked list real life example

Node : 자료구조를 구성하는 요소

Node의 구성 :

1. value

2. next Node

→ next Node : 리스트에 다음으로 연결되는 노드이다.

Node 구성

---

Linked List : Methods :

* 링크(포인터)를 통해서 데이터 추가/삭제/탐색이 가능하다.
* 포인터란 : 각 노드를 연결해주는 화살표 (예시: 강강수월래 할 때 각 사람의 손)

아래 코드는 Linked List의 Method들을 구현하기 위해 Linked List를 Class로 만들어준 것이다.

Linked List 구성

다음, Lined List에 사용되는 Method들을 모두 직접 아래와 같이 구현해봤다.

1. addToTail(value) : Linked List 마지막에 데이터를 추가한다.

AddToTail 예시

2. insertInPosition(position, value) : 원하는 위치에 데이터를 추가한다.

InsertInPosition 예시

3. getNodeAt(index) - 주어진 인덱스의 노드를 찾아서 반환합니다.

*값이 아니라 노드를 반환해야 하는 것에 주의. 해당 인덱스에 노드가 없다면 undefined를 반환한다.

getNodeAt 예시

4. contains(value) : 해당 값이 Linked List에 있는지 Boolean으로 반환한다.

Contains(value) 예시

5. indexOf(value) : 해당 값이 어떤 인덱스에 있는지 인덱스 값과 -1로 반환한다.

IndexOf(value) 예시

6. remove(value): 해당하는 Linked List의 값을 지운다.

Remove(value) 예시

7. size() : Linked List의 사이즈를 반환한다.

Size 예시

Linked List에 원하는 value들을 넣고나면 아래와 같이 출력이 될 것이다.

Lined List 출력 예시

---

Speed

Method	Big O Complexity
addToTheEnd(value)	n
insertInPosition(value, position) | at the end or beginning*	n or 1
getNodeByPosition(position)	n
removeFromPosition(position) | from the end or beginning*	n or 1
getIndexOf(value)	n
removeElementByValue(value)	n
getLength()	1
isEmpty()	1
print()	n

 

* Big O Notation 관련 유용한 정리글 : 링크

---

Types of Linked List :

1. Singly Linked List (일방향 연결 리스트)

다음 노드를 가리키는 링크(포인터)가 한 개인 연결 리스트이다.

이 리스트의 장점 : 노드당 포인터 데이터를 4 바이트만 차지한다.

* 단, 일방통행이기 때문에 현재 노드는 이전 노드로 돌아가는 법을 모른다.

 

2. Doubly Linked List (이중 연결 리스트)

노드에 포인터가 두 개 있는 리스트이다.

이 리스트의 단점 : 포인터가 두 개가 생겼으니 데이터도 두 배로 먹어버려 총 8 바이트를 차지한다.

* 현재 노드의 이전으로 갈 수도, 이후로도 갈 수도 있다.

 

3. Circular Linked List (환형 연결 리스트)

tail 부분의 포인터가 null을 가리키고 있는 것이 아닌 head를 가리키고 있는 것이 다르다.

유용한 환형 예시 : 지하철 2호선.

* 아래 이미지 참고

Linked List Types

---

Linked List VS Array

Linked List	Array
메모리상에 데이터들이 연속적으로 위치하지 않는다.	메모리를 연속적으로 할당한다.
배열에 비해 데이터의 추가/삽입이 용이하다.	동일한 데이터 타입을 연속적으로 저장할 수 있다.
배열에 비해 메모리를 더 효율적으로 사용할 수 있다.	데이터 탐색이 용이하다.
특정 위치의 데이터를 찾기 위해 처음부터 끝까지 순회 해야한다.	고정된 크기로서, 배열의 처음이나 중간에서 추가 및 제거가 어렵다.
추가/삭제에 용이하다.	탐색/정렬에 용이하다.

 

---

 

* 이 영상은 내가 찾아본 Linked List에 대한 명강의여서 같이 올려본다...

Linked List에 대해서 이해하는데 더 도움이 되길 바란다.