Skip Ring/Circular Skip List: Circular Linked List Based New Data Structure

Abstract

A linked list is a data structure consisting of a group of nodes which together represent a sequence. Linked lists are used in skip list data structures. 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. Our new data structure, skip ring, 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. Time complexity of search, insertion and deletion equals to O (lg N) in an N-element skip ring data structure. Therefore, skip ring data structure is employed more effectively (O(lg N)) in circumstances where circular linked lists (O(N)) are used.

Keywords: Skip Ring, Circular Skip List, Circular Linked List, Skip List, Data Structure.