[JS|자료구조] 자바스크립트(javascript)의 Linked List(연결리스트) 알아보기

 

배열이 연속된 메모리에 저장하고, 인덱스를 사용한 자료구조라면

연결리스트는 떨어진 메모리에 저장한 뒤 링크를 사용한 자료구조라고 할 수 있다.

 

배열과 연결리스트 차이

인덱스를 사용하기에 Arr[1] 와 같은 명령으로 검색에 O(1)의 복잡도가 드는 배열과 달리

Head에서부터 차례대로 검색해야하는 연결리스트의 검색 복잡도는 O(n)이다.

 

연결리스트의 종류

1. 단순 연결리스트 : Node 1개에 링크 1개가 있다.
2. 이중 연결리스트 : Node 1개에 링크 2개가 있다. (이전 Node 링크 1개, 이후 Node 링크 1개)
3. 원형 연결리스트 : 마지막 Node(tail)의 링크가 첫 Node(head)를 가리킨다.
4. 이중 원형 연결리스트 : 이중 + 원형의 연결리스트

---

연결리스트의 종류

1. 단순 연결리스트 :Node 1개에 링크 1개가 있다.

 

 

2. 이중 연결리스트: Node 1개에링크 2개가 있다. (이전 Node 링크1개,이후 Node 링크1개)

 

3. 원형 연결리스트 : 마지막 Node(tail)의링크가첫 Node(head)를 가리킨다.

 

4. 이중 원형 연결리스트 : 이중+원형의 연결리스트