University:
Tufts University
Course:
CS0011 | Introduction to Computer Science
Academic year:

2024
Views:

199

Pages:

2
Author:

customer-8292626

Basically a skip lists combines the following: no need to shift elements on deletion or insertion: O(1) (inspired by linked lists the ability to search a sorted collection with binary search (inspired by sorted arrays) But they implement the binary search in a strange way. We can view skip lists has a 2-dimensional collection of positions. Kind of like a 2D linked list except it's not every node on every line has it's own unique up down left and right links. We consider the skip list to have horizontal levels and vertical towers. The positions can be traversed with the following operations: next(p) //Returns the position following p on the same level. prev(p) //Returns the position preceding p on the same level. above(p) // Returns the position above p in the same tower. below(p) //Returns the position below p in the same tower. Skip List Arrangement Formal definition: $ \text{A skip list for a set S of distinct (key, element) items is a series of lists $S_0, S_1 , \cdots , S_h such that} Each level has the special keys (i.e. very large and very small or very negative numbers) e.g $+\infty, -\infty