Double Linked List의 생김새는 다음과 같다.
prev 라는 포인터가 생기므로 사용하는 자원은 늘어났다.
공간을 더 사용함에도 분명한 장점이 있다.
double Linked list를 초기화 하면 더미노드를 다음과 같이 2개를 갖게 된다.
Linked List에서 맨 마지막에 값을 하나 추가하는게 O (n) 의 시간이 걸렸지만
double Linked List에서는 Tail 의 노드가 있기 때문에 O (1) 만에 뒤에 값을 추가할 수 있게 된다.
또한 double Linked list는 값을 검색할때 TAIL에서도 시작 가능하기 때문에 뒤에 가까운 값들은 TAIL로 부터 시작하여 값을 검색하여 가지고 온다. 따라서 O (1/2 * n) 이지만, 점근법을 쓰면 O (n)임
Double Linked List의 추가
Double Linked list의 삭제
'자료구조&알고리즘' 카테고리의 다른 글
| HASH와 HASH Collision 그리고 Chaining (해시 자료구조) (0) | 2022.04.07 |
|---|---|
| 스택과 큐에 대하여 (0) | 2022.04.07 |
| 리스트 - LinkedList (0) | 2022.04.07 |
| 자료구조 & 알고리즘을 왜 공부해야 할까? (0) | 2022.04.07 |
| 알고리즘은 뭘까? (0) | 2022.04.06 |