Kakkot List- An Improved Variant of Skip List
subject: Merging; Performance Analysis; SortingBasis algorithms; Tree Data Structure
description: Kakkot list is a new data structure used for quick searching in a well ordered sequence of list like Skip list. This ordered sequence of list is created using linked list data structure and the maximum number of levels here will be limited to log n in all input behavioral cases. The maximum number of items in each level is halved to that of previous levels and thus guarantees a fast searching in a list. The basic difference between Kakkot list and Skip list lies in the creation of levels and decision of when an item has to be included in the higher levels. In skip list the levels are created and items are added to each level during the insertion of an item where as in Kakkot list this will be done at the time of searching an item. This modification have made drastic impact in searching time complexity in the Kakkot list. Another issue in Skip list is that it is not cache friendly and does not optimize locality of reference wherein this problem is also addressed in Kakkot List. 2020 IEEE.
creator: Rajesh R.
source: Proceedings - IEEE 2020 2nd International Conference on Advances in Computing, Communication Control and Networking, ICACCCN 2020, pp. 915-920.
publisher: Institute of Electrical and Electronics Engineers Inc.
date: 2020-01-01
rights: Restricted Access
relation: ISBN: 978-172818337-4
format: Online
language: English
type: Conference paper
coverage: Rajesh R., CHRIST (Deemed to Be University), Department of Computer Science, Bangalore, India