In this paper, two basic data storage structures are introduced, and the linked list and a new data structure, skip list, which is optimized based on these two data structures are introduced. The content and code sections refer to skip lists.
preface
For an ordered set of integer data, the first relatively simple data structures that come to mind are arrays and linked lists. The following will explain the basic operation of ordered data.
An array of
Arrays are the most common collection of ordered data, analyzed by the following operations.
To find the
A dichotomous lookup of an array takes the time O(logn).
Insert, delete
On the basis of dichotomy, it takes O(logn) to find the target position, while it takes O(n) to perform insert and delete operations (because after insert or delete, it takes O(n) to move the element behind the target position, so the total time is O(n+ LGN)=>O(n)).
disadvantages
Binary lookups reduce the time complexity to O(logn), but arrays are of constant length, and even if you reach a point where you can expand, it takes a lot of time.
The list
Linked list data structure is a chain structure in which nodes store data. It is also analyzed from the following operations.
To find the
Query operations in linked lists can only be accessed one node at a time, so the time complexity is O(n).
Insert, delete
After the target location is found, the time complexity of insert and delete operations is only O(1), but the search operation takes O(n), so the total operation takes O(n).
The advantages and disadvantages
The disadvantage of linked lists is that, unlike arrays, lookups must be accessed node by node, affecting insert and delete operations. The advantages are also obvious: when a node is needed, it will apply for the space of a node, which will not cause the waste of space. Besides, the time complexity of insertion and deletion is O(1), regardless of the search process.
Code implementation (Java+GO)
Java version
class Node<T>{
public T val;
public Node<T> next;
Node(){
this.val = null;
this.next = null;
}
Node(T val){
this.val = val;
this.next = null; }}// Node structure
public class myList<T>{
private Node<T> Head;
private int length;
myList(){
this.Head = new Node();
this.length = 0;
}
myList(T val){
this.Head = new Node(val);
this.length = 1;
}
public Node<T> getHead(a){
return this.Head;
}
public void addAtTail(T data){
Node<T> tmpNode=new Node(data);
Node<T> point = this.Head;
if (this.length == 0) {
point.val = tmpNode.val;
this.length++;
System.out.printf("%d",point.val);
}else{
Node<T> prePoint = point;
point = point.next;
while(point! =null){
prePoint = point;
point = point.next;
}
prePoint.next = tmpNode;
System.out.printf("->%d",prePoint.next.val);
this.length++; }}// Tailplug
public void addAtHead(T data){
Node<T>tmpNode = new Node(data);
if (this.length == 0) {this.Head.val = tmpNode.val;
this.length++;
}else{
tmpNode.next=this.Head;
this.Head = tmpNode;
this.length++; }}// Head insert operation
public void addAtIndex(int index, T data){
Node<T>tmpNode = new Node(data);
Node<T>point = this.Head;
if(index==0) {/ / head node
tmpNode.next = this.Head;
this.Head = tmpNode;
this.length++;
}else {
int count = 0;
Node<T>prePoint = point;
point = point.next;
while(count<index-1){ prePoint = point; point = point.next; count++; } prePoint.next = tmpNode; tmpNode.next = point; }}// Position insert
public void delete(int index){
if(index==0) {
this.Head = this.Head.next;
this.length--;
return;
}
Node<T> prePoint = this.Head;
Node<T> point = this.Head;
for(int i=0; i<index; i++) { point = prePoint.next;if(i==index-1){
prePoint.next = point.next;
this.length--; } prePoint = prePoint.next; }}// Delete a node at a location
public int search(T val){
int index = 0;
Node<T> point = this.Head;
while(point! =null) {
if(point.val == val)return index;
point = point.next;
index++;
}
return -1;
}// Find a value
public T get(int index) {
Node<T> point = this.Head;
for(int i=0; i<index; i++) { point = point.next; }return point.val;
}// Get the position of the ith node
public int getLength(a) {
return this.length;
}// Get the position of the ith node
public boolean isEmpty(a){
return this.length==0;
}/ / found empty
public static<T> void printList(myList<T> list) {
System.out.println("\nList Data:");
Node<T>point = list.getHead();
System.out.printf("%d",point.val);
point = point.next;
while(point! =null){
System.out.printf("->%d",point.val);
point = point.next;
}
System.out.println();
}
public static void main(String[] args) {
// TODO Auto-generated method stub
myList<Integer> list = new myList();
System.out.printf("Now list is Empty? %s \n",list.isEmpty());
int[] a = new int[] {1.2.3.4.5.6.7.8.9};
for (int num:a){
list.addAtTail(num);
}
/ / list. AddAtIndex (2, 1);
printList(list);
System.out.printf("Now list is Empty? %s \n",list.isEmpty());
System.out.printf("the data in the index 2 of list is %d \n",list.get(2));
System.out.printf("the length of list is %d \n",list.getLength());
System.out.printf("search 3 in the list,index is %d \n",list.search(3));
list.delete(list.search(2));
System.out.println("After deleting data:2..........");
printList(list);
System.out.printf("the length of list is %d \n",list.getLength());
System.out.printf("search 3 in the list,index is %d \n",list.search(3)); }}Copy the codeGo version
package main
import (
"fmt"
)
// Node structure
type Node struct {
Data interface{}
Next *Node
}
// List structure
type List struct {
Head *Node
Length int
}
// Method interface
type Method interface {
addAtIndex(i int,data interface{})// Insert data at a specific location
addAtTail(data interface{})/ / end plug
addAtHead(data interface{})/ / head
get(index int)interface{}// Get the node data of index
search(data interface{}) int
delete(i int)
getLength() int
isEmpty() bool
}
// Create a node
func createNode(data interface{})*Node{
return &Node{data,nil}}// Create a linked list
func createList(a) *List{
return &List{createNode(nil),0}}// Insert the node from the head
func(list *List)addAtIndex(i int,data interface{}){
tmpNode:=createNode(data)
point := list.Head
if i==0{/ / head node
tmpNode.Next = list.Head
list.Head = tmpNode
list.Length++
}else {
count:=0
prePoint := point
point = point.Next
for count<i- 1 {
prePoint = point
point = point.Next
count++
}
prePoint.Next = tmpNode
tmpNode.Next = point
}
}
// Insert the node from the tail
func(list *List)addAtTail(data interface{}){
tmpNode:=createNode(data)
point := list.Head
if list.Length == 0 {
point.Data = tmpNode.Data
list.Length++
fmt.Printf("%d",point.Data)
}else{
prePoint := point
point = point.Next
forpoint! =nil {
prePoint = point
point = point.Next
}
prePoint.Next = tmpNode
fmt.Printf("->%d",prePoint.Next.Data)
list.Length++
}
}
// Insert the node from the head
func(list *List)addAtHead(data interface{}){
tmpNode:=createNode(data)
if list.Length == 0 {
list.Head.Data = tmpNode.Data
list.Length++
}else{
tmpNode.Next=list.Head
list.Head = tmpNode
list.Length++
}
}
// Get the I node
func(list *List)get(i int) interface{}{
point := list.Head
for index:=0; index<i; index++{ point = point.Next }return point.Data
}
// Find the node, if not
func(list *List)search(data interface{}) int{
point := list.Head
index:=0
forpoint! =nil{
if point.Data == data{
return index
}
index++
point = point.Next
}
return - 1
}
// delete the node at I
func(list *List)delete(i int){
if i==0{/ / head node
list.Head = list.Head.Next
list.Length--
return
}
prePoint := list.Head
for count:=0; count<=i- 1; count++{ point := prePoint.Nextif count==i- 1{
prePoint.Next = point.Next
list.Length--
}
prePoint = prePoint.Next
}
}
// Get the list length
func(list *List)getLength(a)int{
return list.Length
}
// List null
func(list *List)isEmpty(a)bool{
point := list.Head
if(point.Data==nil) {return true
}else{
return false}}func printList(list *List){
fmt.Println("\nList Data:")
point := list.Head
fmt.Printf("%d",point.Data)
point = point.Next
forpoint! =nil{
fmt.Printf("->%d",point.Data)
point = point.Next
}
fmt.Println()
}
func main(a){
list := createList()
fmt.Printf("Now list is Empty? %t \n",list.isEmpty())
a :=[]int{1.2.3.4.5.6.7.8.9}
for _,num := range a{
list.addAtTail(num)
}
list.addAtIndex(2.1)
printList(list)
fmt.Printf("Now list is Empty? %t \n",list.isEmpty())
fmt.Printf("the data in the index 2 of list is %d \n",list.get(2))
fmt.Printf("the length of list is %d \n",list.getLength())
fmt.Printf("search 3 in the list,index is %d \n",list.search(3))
list.delete(list.search(2))
fmt.Printf("After deleting data:2..........")
printList(list)
fmt.Printf("the length of list is %d \n",list.getLength())
fmt.Printf("search 3 in the list,index is %d \n",list.search(3))}Copy the codeJump table
introduce
On the basis of considering the advantages of linked list, and the advantages of array in search, insert and delete, that is, based on improving the speed of basic operations, the data structure of skip list is designed.
To find the
Take the following linked list for example:
To find element 8, a normal single linked list needs to traverse eight nodes to find element 8. Since elements are ordered, it can be considered to extract some nodes from the base list and add list paths to speed up the search. For example, new links are added every other node.
As shown in the figure above, a double-layer linked list is established. When searching for element 8, start from the second layer and combine with the original linked list, only five nodes need to be visited according to the red path in the figure above to find element 8.
Establish a three-layer linked list. When searching for element 8, start from the third layer and combine with the original linked list, only four nodes need to be accessed according to the red path in the figure above to find element 8.
With four layers, finding element 8 doesn’t seem to help, but if you look for element 9, you only visit two nodes to find that element.
This method based on each layer relative to the previous layer to establish a new link, similar to the binary array search method. Finally, it takes order logn.
insert
After the search process is finished, the next step is the insertion operation, which is the same with linked list insertion but somewhat different. The same place is the same with linked list insertion. If the insertion operation is required for each layer, it only takes O(1), but the difference is that multiple links may need to be inserted.
So, how many layers does the inserted node span or what link path does it insert into?
Coin toss strategy: the layer to insert the new node is determined by the coin toss – each time the node is inserted, the coin toss continues until there is a negative stop, the number of heads as the number of layers the node spans.
Take the following linked list as an example: when inserting 3 and 4 elements, according to the coin flip strategy, 3=>0,4=>2.
3=>0 means crossing layer 0, that is, adding 3 to the original list path.
4=>2 means crossing 2 levels, i.e. adding 4 to the original list, first level, and second level paths. As shown in the figure below
delete
The delete operation deletes the element to be deleted at the link layer that contains the element to be deleted.
If 4 is deleted, all 4 contained in each layer will be deleted.
conclusion
-
Each layer of a skip list is an ordered linked list, and the lowest linked list is the initial single linked list.
-
Combined with the characteristics of array and linked list, search, insert, delete time complexity is O(logn).
-
The number of layers of a skip list is related to a coin flip strategy and is a randomized data structure with different results for each run.
Code implementation (Java+Go)
Java version
class skipNode{
int val = -1;
skipNode[] next;// Next node in array form
int layer;// The number of layers to span
public skipNode(int val,int layer){
this.val = val;
this.layer=layer;
this.next = newskipNode[layer]; }}// Node structure
public class SkipList {
// Maximum number of layers
public int maxLayer = 16;
// Head node, not used, secondary node
public skipNode head = new skipNode(-1,maxLayer);
// Total number of skip list nodes
public int skipListSize = 0;
// The initial jump layer is the original linked list
public int layerCount = 1;
// The search process
public skipNode search(int val) {
skipNode point = this.head;
for(int i = layerCount-1; i>=0; i--) {// From the jump layer
while(point.next[i]! =null&& point.next[i].val<val) { point = point.next[i]; }}// Check whether the element exists
if(point.next[0]! =null && point.next[0].val==val) {
System.out.println(val+"Search successful");
return point.next[0];
}else {
return null; }}public int tossCoins(a){
int layer = 1;
while(true) {
int t = (int)(Math.random()*10);
if(t %2= =0)layer++;
else break;
}
System.out.println("The jump surface number of the linked list is:"+layer);
return layer;
}// Coin toss
public void add(int val) {
int layer = tossCoins();// Get the spanning layer
while(layer>this.layerCount*2.5){
layer = tossCoins();// Get the spanning layer
}
skipNode point = new skipNode(val,layer);
// Record the position of the node before the node is inserted
skipNode[] prePoint = new skipNode[layer];
skipNode tmp = this.head;
int i;
for(i=layer-1; i>=0; i--) {while(tmp.next[i]! =null&&tmp.next[i].val<val) {
tmp = tmp.next[i];
}
prePoint[i]=tmp;
}
/ / insert
for(i=0; i<layer; i++) { point.next[i] = prePoint[i].next[i]; prePoint[i].next[i] = point; }if(layer> this.layerCount) {
this.layerCount = layer;
}
this.skipListSize++;
System.out.println(val+"Insert successful");
}
public void delete(int val) {
skipNode[] prePoint = new skipNode[this.layerCount];
skipNode point = this.head;
int i=0;
for(i=this.layerCount-1; i>=0; i--) {while(point.next[i]! =null && point.next[i].val<val) {
point = point.next[i];
}
prePoint[i] = point;
}
if(point.next[0]! =null&&point.next[0].val == val) {
this.skipListSize--;
System.out.println(val+"Deleted successfully");
for(i=this.layerCount-1; i>=0; i--) {if(prePoint[i].next[i]! =null&& prePoint[i].next[i].val==val) { prePoint[i].next[i] = prePoint[i].next[i].next[i]; }}}}public static void printSkipList(SkipList list) {
for(int i = list.layerCount-1; i>=0; i--) { skipNode point = list.head;while(point.next[i]! =null){
System.out.print(point.next[i].val+""); point = point.next[i]; } System.out.println(); }}public static void main(String[] args) {
// TODO Auto-generated method stub
SkipList list = new SkipList();
for(int i=0; i<6; i++) { list.add(i); } printSkipList(list); list.delete(4);
printSkipList(list);
System.out.println(list.search(3));
System.out.printf("%d %d",list.skipListSize,list.layerCount); }}Copy the codeGo version
package main
import (
"fmt"
"math/rand"
"time"
)
const MAX_LAYER = 16
// Node structure
type skipNode struct {
val int
layer int
Next []*skipNode
}
// List structure
type skipList struct {
Head *skipNode
skipListSize int
maxLayer int
layerCount int
}
// Interface method
type method interface {
add(val int) / / to add
search(val int) *skipNode / / find
delete(val int) / / delete
}
// Create a node
func createSkipNode(val int,layer int) *skipNode{
return &skipNode{
val,
layer,
make([]*skipNode,layer),
}
}
// Create a skip list
func createSkipList(a)*skipList{
head :=createSkipNode(- 1,MAX_LAYER)
return &skipList{
Head: head,
skipListSize: 0,
maxLayer: MAX_LAYER,
layerCount: 1,}}// Coin toss
func tossCoins(a) int{
layer:=1
for true{
rand.Seed(time.Now().UnixNano())// Random number seed
t := rand.Intn(10)
if t%2= =0{
layer++
}else{
break
}
}
fmt.Printf("The number of jump surfaces of the linked list node is: %d \n",layer)
return layer
}
/ / to find
func(list *skipList)search(val int) *skipNode{
point:=list.Head
for i:=list.layerCount- 1; i>=0; i--{forpoint.Next[i] ! =nil && point.Next[i].val<val{
point = point.Next[i]
}
}
if point.Next[0]! =nil && point.Next[0].val == val{
fmt.Printf("\n %d Search succeeded \n",val)
return point.Next[0]}else {
return nil}}/ / to add
func(list *skipList)add(val int){
layer := tossCoins()
point := createSkipNode(val,layer)
prePoint := [MAX_LAYER]*skipNode{}
tmp := list.Head
for i:=layer- 1; i>=0; i--{fortmp.Next[i] ! =nil && tmp.Next[i].val<val {
tmp = tmp.Next[i]
}
prePoint[i] = tmp
}
/ / insert
for i:=0; i<layer; i++{ point.Next[i] = prePoint[i].Next[i] prePoint[i].Next[i] = point }if layer>list.layerCount{
list.layerCount = layer
}
list.skipListSize++
fmt.Printf("%d successfully inserted \n",val)
}
/ / delete
func(list *skipList)delete(val int){
prePoint := make([]*skipNode,list.layerCount)
point := list.Head
for i:=list.layerCount- 1; i>=0; i--{forpoint.Next[i] ! =nil && point.Next[i].val<val{
point = point.Next[i]
}
prePoint[i] = point
}
if point.Next[0] !=nil && point.Next[0].val==val{
list.skipListSize--
fmt.Printf("%d deleted successfully \n",val)
for i:=list.layerCount- 1; i>=0; i--{ifprePoint[i].Next[i]! =nil && prePoint[i].Next[i].val==val{
prePoint[i].Next[i]=prePoint[i].Next[i].Next[i]
}
}
}
}
// Output skip list
func printSkipList(list *skipList){
for i:=list.layerCount- 1; i>=0; i--{ point := list.Headforpoint.Next[i]! =nil{
fmt.Printf("%d ",point.Next[i].val)
point = point.Next[i]
}
fmt.Println()
}
}
func main(a){
list:= createSkipList()
for i:=0; i<6; i++{ list.add(i) } printSkipList(list) list.delete(0)
printSkipList(list)
list.search(3)
fmt.Printf("%d %d\n",list.skipListSize,list.layerCount)
}
Copy the code