Singly & Doubly Linked List

Linked List 란? 

 A sequential list of nodes that holds data which point to other nodes also containing data

데이터를 가지고 있는 노드들의 연속적인 리스트

 

어디에 사용될까?

List, Queue & stack, circular list

separate chaining, hashtable 등등

 

▶ Singly Linked List와 Doubly Linked List 비교

	장점	단점
Singly Linked List	사용하기 용이함 메모리를 덜 사용함	이전의 요소에 쉽게 접근하기 어려움
Doubly Linked List	역방향 순회가 가능함	2배의 메모리가 소요됨

 

Source: https://kodr.me/en/linked-list-intro

 

 

 

▶ Singly Linked List와 Doubly Linked List 사용 방법

 Singly Linked List 에서 중간에 노드 삽입하는 법

예시_ [1,2,3,4]의 2와 3 사이에 7을 넣으려 할 때

1. Head를 지정한다 -> 1
2. Next로 간다 -> 2
3. 새로운 노드를 만든다 -> 7
4. 새로운 노드가 3과 연결된다 7->3
5. 이전의 노드가 새로운 노드에 연결된다 2->7 

 

 Doubly Linked List 에서 중간에 노드 삽입하는 법

예시_ [1,2,3,4]의 2와 3 사이에 7을 넣으려 할 때

1. Head를 지정한다 -> 1
2. Next로 간다 -> 2
3. 새로운 노드를 만든다 -> 7
4. 새로운 노드가 3과 연결된다 7->3
5. 새로운 노드가 이전의 노드에 연결된다 7->2 
6. Next가 새로운 노드와 연결된다 3 ->7
7. 이전의 노드가 새로운 노드에 연결된다 2->7

Singly 와 방법은 유사하지만 양방향을 다루기 때문에 과정이 추가된다  

 

 

▶ Singly Linked List와 Doubly Linked List 의 Complexity Analysis

	Singly Linked	Doubly Linked
Search	O(n)	O(n)
Insert at head	O(1)	O(1)
Insert at tail	O(1)	O(1)
Remove at head	O(1)	O(1)
Remove at tail	O(n)	O(1)
Remove in middle	O(n)	O(n)

 

 

 

https://psygo22.tistory.com/34

Linked List 총정리

(위 글에서 자세히 다뤘지만 복습겸 간단하게 짚고 넘어가겠습니다)

 

 

 

 

(이 글은 freeCodeCamp의 Data Structures Easy to Advanced Course -Full Tutorial from google engineer을 바탕으로 정리한 내용입니다.)