Skip ring: A new data structure based on circular and skip lists

Linked lists are used in skip list data structure. Skip list data structure consists of layered structure and all nodes are in the lowest layer. These nodes are reduced by half towards upper layers and are formed a pyramid-shaped structure. Thus, it is aimed to enable searching, insertion and deletion. Besides, this data structure can be improved further. The purpose of our study is to identify problems in data structure by analyzing skip list data structure, to make improvements in skip list data structure by resolving the identified problems and to implement and then to apply these improvements to the new data structure that we proposed. New data structure that we proposed by considering improvements in skip list is formed by utilizing skip ring, circular linked list and skip list data structure. New data structure that we proposed composes of circular linked list in cone-shaped cohesive layers. Thus, time complexity of search, insertion and deletion progress is O(lgN) in N-Element skip list data structure. Proposed new data structure was compared practically with binary search trees, red-black trees and skip list data structures and the results was evaluated. Moreover, a new sorting based on skip ring and search algorithm were proposed. These proposed algorithms were compared practically with current sorting and search algorithms. Consequently, skip ring data structure which was improved by utilizing the properties of skip list and circular linked lists was compared with some tree-based data structures and good results were obtained. And also, effective applicability in some areas such as sorting and searching was demonstrated.