[Algorithm] Unrolled Linked List

 

한국어로 찾았을 때 아무결과도 안나오는거 보면 좀 마이너한듯??

 

linear data structure이고, linked list와 array의 장점을 모두 살린 자료구조이다.

 

링크드 리스트 장점: 삽입하는데 O(1)걸린다. 근데 단점 - search시간이 O(n)이다...

Q) search시간을 줄일 수 없을까???

 

unrolled linked list는 array와 linked list의 장점을 모두 갖고 있다 - 한 노드에 여러개를 보관해서 search시간 낮아지고, insertion과 deletion이 linked list만큼 빠르다.

 

일반적인 구현으로는 꽉 채우지 않고 3/4정도만 채워준다고 한다. 

 

https://www.geeksforgeeks.org/unrolled-linked-list-set-1-introduction/

 

장점) pointer/refernece를 위한 storage down. linked list는 하나의 data마다 포인터 저장해야 하니까 공간이 더 많이 필요하다. 

 

linear search 훨씬 빠르다.

그림처럼 9개 원소중에 7번째를 찾아야한다면 node 2개를 점프해서 3번째 노드에서 1번째 원소를 보면 된다. 

 

단점) node마다 overhead가 커진다. (node의 크기가 커진다)

 

현대 캐시에 적용하기 더 좋다고 한다??

 

 

[출처]

https://www.geeksforgeeks.org/unrolled-linked-list-set-1-introduction/