文章基本信息

标题：Skip Ring/Circular Skip List: Circular Linked List Based New Data Structure
本地全文：下载
作者：Mustafa AKSU ; Ali KARCI
期刊名称：Computer Engineering and Intelligent Systems
印刷版ISSN：2222-1727
电子版ISSN：2222-2863
出版年度：2015
卷号：6
期号：5
页码：35-41
语种：English
出版社：International Institute for Science, Technology Education
摘要：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.
其他摘要：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.
关键词：Skip Ring; Circular Skip List; Circular Linked List; Skip List; Data Structure.