[TIL] 자료구조 - Linked List

What I learned today

✨ Linked List 📌

✨ Hash Table

---

✨ Linked List

Linked List란

Linked List는 연속적인 자료 구조로, 그 크기가 동적인 구조라고 할 수 있으며, 
연속적인 자료구조라 함은 `node`라고 불리는 요소들이 링크를 통해 연결되는 것이다. 
`node`안에는 1)value 2)pointer로 이루어져 있다. 

위의 그림의 첫번째 node는 value=12, 화살표부분 칸= 다음 node를 가르키는
pointer로 이루어진 address로 이루어져 있다. 
배열과는 다른 구조임을 주의하도록 하자.

Linked List 종류

a. 단일 Linked List

single Linked List라고 하며, node들은 다음 node에만 연결(링크)한다.
참고로 다음 node를 연결하고자 할 때 다음 node는 저거에요!(referencing)
라고 안내표지처럼 지목하는 기능이 있는데 이것을 pointer라고 부른다. 

위의 그림을 보면 head라는 것이 있는데, 이 head는 이 자체가 pointer이다. 
생활코딩의 비유를 인용하자면
하나의 리스트를 건물로 예를 들 때, head는 건물의 출입문이라고 볼 수 있다고 한다. 
따라서 Linked List를 사용하기 위해서는 이 head가 가리키는 첫번째 노드를 찾아야 한다.

이해하기 쉽게 본인은 단일 Linked List를 순자적으로 연결된 연을 떠올렸다. 

한참 연날리다 연줄이 끊겨 연들이 하늘로 사라지는 것과 같이
각 노드의 Pointer가 null	을 지목하고 있을 때 
그와 동시에 단일 linked list 도 종료된다. 

만약 head pointer에 null 혹은 undefined를 주면 
모든 node와의 링크가 끊어져 모든 node를 가비지 컬렉터가 순차적으로 없애준다.
(1번의 실행으로 모든 node를 지울 수 있게 된다.)

단!! 단일 Linked List는 링크되기 전의 node에 대해 알 방법이 없다. 
node1 -> node2가 링크되면 node2은 아예 `노빠꾸`라는 말이다. 

b. 이중 Linked List

이중 linked list에서는 단일 linked list와 달리 각 node들은 이전 node들에 대한 reference를 가지고 있다는 장점이 있다. 따라서 각 node에 두 개의 포인터가 존재하고 그 포인터들은 자신의 앞 뒤를 가리키는게 큰 특징이다.
단일 리스트와 동일하게 value를 가지고 있다.

c. 원형 Linked List
(사진 출처:https://burger-and-fries.tistory.com/13)

✨ 단일 Linked List 구현

연결리스트에서 node의 insert & remove는 항상 순서가 공통적으로 있는데 특정 node와의 연결이다.

노드 삽입(insert)

새로운 노드 생성 -> 새로운 노드를 연결(link) 

노드 삭제(remove)

삭제 대상 node 탐색(0번째부터 찾아야하므로 while문 혹은 for문을 써주면 좋다.) 
->  대상 node의 앞과 뒤의 node를 연결한다. -> 삭제 대상 node를 삭제한다.

아래와 같이 코드로 단일 Linked List를 구현할 수 있다.

스프린트 완료하는대로 추가하기 

Linked List vs 배열
L vs 객체