Chapter 3: Linked Lists – 7. Skip Lists

Tuesday, 11/10/2022

Tram Ho

3.11 Skip Lists

Binary trees – Binary trees can be used to represent abstract data types such as dictionaries and ordered lists.
They work fine when the elements are inserted in random order.
Some sequences of operations, such as inserting elements in order, produce degraded data structures that yield very poor performance.
If it is possible to randomly permute the list of inserted items, the tree will work well with high probability for any input sequence.
In most cases, queries must be answered online, so it is impractical to permute the input randomly.
Balanced tree algorithms rearrange the tree as operations are performed to maintain certain equilibrium conditions and ensure good performance.
Skip list is a data structure that can be used as an alternative to balanced binary trees

The paragraph above about the current binary tree reading may be a bit confusing, for the time being we just skip it, when we come to the chapter on Tree, we will present it more clearly and in more detail.

Compared to a binary tree, a skip list allows for fast searching, insertion, and deletion of elements.
This is achieved by using probabilistic balance instead of strictly enforcing the balance as in tree.
It’s basically a linked list with additional pointers so that intermediate nodes can be omitted.
It uses a random number generator to make some decisions.
In a normally sorted linked list, search, insertion, and deletion are in O(n) because the list has to be scanned node by node from the head to find the relevant node.
If we can somehow scan the list in larger steps (ignoring it, like that), we reduce the cost of scanning.
This is the basic idea behind Skip Lists.

Skip Lists with One Level

Skip Lists with Two Levels

Skip Lists with Three Levels

Algorithms

This section gives algorithms for finding, inserting, and deleting elements in a dictionary or symbol table.
The Find operation returns the contents of the value associated with the desired key, or an error if the key is not present.
The Insert operation associates a specified key with a new value (insert the key if it doesn’t already exist).
The Delete operation deletes the specified key.
Easily support additional operations like “find minimum key” or “find next key”.
Each element is represented by a node, the level of which is chosen at random when the node is inserted, regardless of the number of elements in the data structure.
A level i node has i forward pointers, numbered 1 through i.
We don’t need to store the level of a node in node.
Levels are limited to an appropriate MaxLevel constant.
The level of the list is the maximum level currently in the list (or 1 if the list is empty).
Header of a list with pointers forwarding from level one to MaxLevel.
The header forward pointer at a level higher than the current maximum level of the list points to NULL.

Initialization

A NIL element is allocated and assigned a key greater than any valid key.
All levels of all ignore lists are terminated with NIL .
A new list is initialized so that the level of the list is 1 and all forward pointers of the list’s headers point to NIL.

Searching for an element

We search for an element by traversing forward pointers that do not exceed the node containing the element being searched.
When no further progress can be made at the current level of the forward pointer, the search moves down to the next level.
When we can’t process further at level 1, that means we have to be right in front of the node containing the desired element (if it’s in the list).

Insertion and Deletion Algorithms

To insert or delete a node we just need to search and concatenate.
The update vector is persisted so that when the search is complete (and we’re ready to do the splice), update[i] contains a pointer to the rightmost node of level i or higher that is to the left of the location. insert/delete position.
If the insertion produces a node whose level is greater than the previous max level of the list, we update the max level of the list and initialize the appropriate parts of the update vector.
After each delete we check if we have removed the maximum element of the list and if so, reduce the maximum of the list.

Random level pick

Initially, we discussed probability distributions where half of the nodes have level pointers

$i$ also have level pointer

$i + 1 . To eliminate magic constants, we say that part p of the nodes has level pointers$

$i also have level pointer$

$i + 1 . (for our initial discussion, p = 1/2). The levels are randomly generated by an algorithm. Levels are created without reference to the number of elements in the list$

Performance

In a singly linked list consisting of n elements, to perform the search, n worst-case comparisons are required.
If a second pointer to the previous two nodes is added to each node, the number of comparisons will be reduced

$n /2 + 1$ in the worst case.
Adding one more pointer to every fourth node and making them point to the previous fourth reduces the number of comparisons

$n / 4 +_2 . If this strategy is continued so that every node has a pointer to$

$2_i - 1 node ahead, O(logn) performance will be achieved and the number of pointers is only doubled$

$(n + n /2 + n /4 + n /8 + n /16 + \dots . = 2 n) .$

The usual find, insert, and remove operations on a binary search tree are efficient,

$O (l o g n)$ , when the input data is random; but less efficient,

$O (n), when the input data is sorted. Skip List performance for these same operations and for any data set is as good as that of a randomly constructed binary search tree specifically$

$O (l o g n) .$

The difference of Skip Lists

In a nutshell, Skip Lists are sorted linked lists with two differences:

The nodes in the normal list have only one reference to the next node. The nodes in the Skip List have multiple subsequent references (also known as forward references).
The number of forward references for a given node is determined by probability.

We’re talking about a node in the Skip List that has levels, one for each forwarding reference. The number of levels in a node is called the size of the node.
In a normally sorted list, the insert, remove, and find operations require sequential traversal of the entire list.
This leads to performance

$O (n)$ per operation.
Skip Lists allow intermediate nodes in the list to be ignored during browsing resulting in expected performance of

$O (l o g n) per operation.$

Implementation

import java.util.Random;

public class SkipList&lt;T extends Comparable&lt;T&gt;, U&gt; {
	private class Node{
		public T key;
		public U value;
		public long level;
		public Node next;
		public Node down;
		public Node(T key, U value, long level, Node next, Node down) {
			this.key = key;
			this.value = value;
			this.level = level;
			this.next = next;
			this.down = down;
		}
	}
	
	private Node head;
	private Random _random;
	private long size;
	private double _p;
	
	private long level() {
		long level = 0;
		while(level &lt;= size &amp;&amp; _random.nextDouble() &lt; _p) {
			level++;
		}
		return level;
	}
	
	public SkipList() {
		head = new Node(null, null, 0, null, null);
		_random = new Random();
		size = 0;
		_p = 0.5;
	}
	
	public void add(T key, U value) {
		long level = level();
		if(level &gt; head.level) {
			head = new Node(null, null, level, null, head);
		}
		Node cur = head;
		Node last = null;
		while(cur != null) {
			if(cur.next == null || cur.next.key.compareTo(key) &gt; 0) {
				if(level &gt;= cur.level) {
					Node n = new Node(key, value, cur.level, cur.next, null);
					if(last != null) {
						last.down = n;
					}
					cur.next = n;
					last = n;
				}
				cur = cur.down;
				continue;
			} else if(cur.next.key.equals(key)) {
				cur.next.value = value;
				return;
			}
			cur = cur.next;
		}
		size++;
	}
	
	public boolean containsKey(T key) {
		return get(key) != null;
	}
	
	public U remove(T key) {
		U value = null;
		Node cur = head;
		while(cur != null) {
			if(cur.next == null || cur.next.key.compareTo(key) &gt;= 0) {
				if(cur.next != null &amp;&amp; cur.next.key.equals(key)) {
					value = cur.next.value;
					cur.next = cur.next.next;
				}
				cur = cur.down;
				continue;
			}
			cur = cur.next;
		}
		size--;
		return value;
	}
	
	public U get(T key) {
		Node cur = head;
		while(cur != null) {
			if(cur.next == null || cur.next.key.compareTo(key) &gt; 0) {
				cur = cur.down;
				continue;
			} else if(cur.next.key.equals(key)) {
				return cur.next.value;
			}
			cur = cur.next;
		}
		return null;
	}
	
	public static void main(String[] args) {
		SkipList s = new SkipList&lt;&gt;();
		s.add(1, 100);
		System.out.println(s.get(1));
	} 
}

100

101

102

103

104

105

106

107

108

import java.util.Random;

public class SkipList<T extends Comparable<T>, U> {

private class Node{

public T key;

public U value;

public long level;

public Node next;

public Node down;

public Node(T key, U value, long level, Node next, Node down) {

this.key = key;

this.value = value;

this.level = level;

this.next = next;

this.down = down;

}

private Node head;

private Random _random;

private long size;

private double _p;

private long level() {

long level = 0;

while(level <= size && _random.nextDouble() < _p) {

level++;

}

return level;

}

public SkipList() {

head = new Node(null, null, 0, null, null);

_random = new Random();

size = 0;

_p = 0.5;

}

public void add(T key, U value) {

long level = level();

if(level > head.level) {

head = new Node(null, null, level, null, head);

}

Node cur = head;

Node last = null;

while(cur != null) {

if(cur.next == null || cur.next.key.compareTo(key) > 0) {

if(level >= cur.level) {

Node n = new Node(key, value, cur.level, cur.next, null);

if(last != null) {

last.down = n;

}

cur.next = n;

last = n;

}

cur = cur.down;

continue;

} else if(cur.next.key.equals(key)) {

cur.next.value = value;

return;

}

cur = cur.next;

}

size++;

}

public boolean containsKey(T key) {

return get(key) != null;

}

public U remove(T key) {

U value = null;

Node cur = head;

while(cur != null) {

if(cur.next == null || cur.next.key.compareTo(key) >= 0) {

if(cur.next != null && cur.next.key.equals(key)) {

value = cur.next.value;

cur.next = cur.next.next;

}

cur = cur.down;

continue;

}

cur = cur.next;

}

size--;

return value;

}

public U get(T key) {

Node cur = head;

while(cur != null) {

if(cur.next == null || cur.next.key.compareTo(key) > 0) {

cur = cur.down;

continue;

} else if(cur.next.key.equals(key)) {

return cur.next.value;

}

cur = cur.next;

}

return null;

}

public static void main(String[] args) {

SkipList s = new SkipList<>();

s.add(1, 100);

System.out.println(s.get(1));

}

Share the news now

Source : Viblo

Chapter 3: Linked Lists – 7. Skip Lists

3.11 Skip Lists

Algorithms

Initialization

Searching for an element

Insertion and Deletion Algorithms

Random level pick

Performance

The difference of Skip Lists

Implementation

TikTok becomes the second largest social platform in South Africa

The fastest depreciating after 9 months of launch, iPhone 14 Pro Max continues to break the bottom in Vietnam

Beginner's guide to R: Introduction

10 essential SublimeText plugins for JavaScript developers