The week's pick
Reseach Article
A New Improved Circular Skip List with Priority Search
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 161 - Number 2 |
| Year of Publication: 2017 |
| Authors: Upinder Kaur, Pushpa Rani Suri |
10.5120/ijca2017913112
|
Upinder Kaur, Pushpa Rani Suri . A New Improved Circular Skip List with Priority Search. International Journal of Computer Applications. 161, 2 ( Mar 2017), 7-14. DOI=10.5120/ijca2017913112
Abstract
Skip list is a data structure with an ordered sequence of elements. It consists of layer of linked list. They consist of a layered structure and all nodes are in the bottom layer. These nodes are reduced to half towards upper layers and thus a pyramid-like structure is formed, which facilitates search, insertion and removal operations. A circular linked list is a type of linked list in which the last node of the list points back to the first node. In this paper we proposed a new data structure improved circular skip list (ICSL). ICSL is created with the help of circular linked list and skip list data structures. In circular linked list, operations are performed on a single round robin list. However, our new data structure consists of circular link lists formed in layers which are linked in a conical way with improved priority search feature. Time complexity of search, insertion and deletion equals to O (log N) in an N-element improved circular skip list data structure. Improved circular skip list data structure is employed more effectively (O(log N)) in circumstances where circular linked lists (O(N)) are used with improved priority searching technique.
References
- Aksu, M.; Karcı, A.; Yılmaz, ¸ S.: Level optimization in Skip List data structure. In: Proceedings of the 1st International Symposium on Innovative Technologies in Engineering and Science (ISITIES2013). pp. 389-396 (2013)
- Aksu, M.; Karcı, A.; Yılmaz, ¸ S.: Effects of P threshold values in creation of random level and to the performance of skip list data structure. Bitlis Eren Univ. J. Sci. 2(2), 148–153 (2013)
- Cormen, T.; Leiserson, C.; Rivest, R.; Stein, C.: Introduction to Algorithms. MIT Press, London (2009)
- McMillan, M.: Data Structures and Algorithms Using C#. Cambridge University Press, New York (2007)
- Shaffer, C.A.: Data Structures & Algorithm Analysis in C++. Dover Publications, Mineola (2011)
- Colvin, R.; Groves, L.; Luchangco, V.; Moir, M.: Formal verification of a lazy concurrent list-based set. In: Proceedings of the Computer Aided Verification, Lecture Notes in Computer Science. 4144, 475–488 (2006)
- Herlihy, M.; Lev, Y.; Luchangco, V.; Shavit, N.: A simple optimistic skiplist algorithm. In: Proceedings of the Structural Information and Communication Complexity. Lecture Notes in Computer Science. 4474, pp. 124–138 (2007)
- Pugh, W.: Skip lists: a probabilistic alternative to balanced trees. Commun. ACM 33(6), 668–676 (1990)
- Kirschenhofer, P.; Prodinger, H.: The path length of random skip lists. Acta Inf. 31(8), 775–792 (1994)
- Papadakis, T.: Skip lists and probabilistic analysis of algorithms. PhD Thesis. University of Waterloo. Tech. Report CS-93-28, (1993)
- Poblete, P.V.; Munro, J.I.; Papadakis, T.: The binomial transform and the analysis of skip lists. Theor.Comput. Sci. 352, 136–158 (2006)
- Munro, J. I.; Papadakis, T.; Poblete, P.V.: Deterministic skip lists. In: Proceedings of the SODA ’92 Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms. pp. 367–375 (1992)
- Pugh, W.: A Skip List Cookbook. Dept. of Computer Science, University of Maryland. College Park. Technical report. CS–TR– 2286.1. (1990)
- Pugh, W.: Concurrent Maintenance of Skip Lists. Dept. of Computer Science. University of Maryland. College Park. Technical report. TR–2222.1. (1989)
- Lotan, I.; Shavit, N.: SkipList-Based Concurrent Priority Queues. In: Proceedings of International Parallel and Distributed Processing Symposium. Mexico, pp. 263–268 (2000)
Index Terms
Keywords