LINKED LIST

DYNAMIC MEMORY ALLOCATION

Application’s memory

STACK
Function calls
and local
variables

Global and
static data

Instructions

GLOBAL
 STACK FRAME
total total total

Global Global Global

• stack stack
OS allocates some
amount of space
for stack at
compile time but
stack frames and
local variables are
allocated at run
time

If stack grows
beyond the
reserved space
(eg: bad
total recursion), stack
overflow occurs
Global Global because stack
cannot grow at
run time
Unlike stack, heap is not fixed. Its size can vary during the lifetime of the
application. A programmer can totally control how much memory to use
from heap.
 malloc
calloc
Heap is also called dynamic realloc
memory and using the heap is free
referred to as dynamic memory
allocation
Clear the
memory
using free
•
•

?
Storing an integer
value in memory,
int x=8;

Memory Manager

Storing a list of
numbers in memory:
Using array we can
store list of number
of same type, array is
always stored as one
contiguous block of
memory

Memory Manager
 Irrespective of the
size of arrays, an
application can
access any of the
elements in array in
constant
time(Random access)
Memory Manager

Storing elements in
array: a[0]=6; a[1]=5;
a[2]=4; a[3]=2;

Memory Manager
 Now, adding one more
element to the array
won't be possible in the
same location, therefore
the array is copied to a
different memory area
where the sufficient
space is available

Memory
Memory Manager
Manager

Creation
Creationofofentirely
entirely
new
newarray
arrayisiscostly.
costly.
Solution
Solutiontotothis
this
problem
problemisislinked
linkedlist
list
Memory Manager
data
datastructure
structure
•
If we request for one
element at a time,
instead of getting one
contiguous block of
memory we get these
disjoint, non-contiguous
block of memory
Memory Manager

Now we need to link

these newly created
blocks. To link these
blocks, we store some
extra information with
the block.
Memory Manager
Request MM for 2 blocks
where 1st block stores
the value and other
variable stores the
address of the next block
in order to create a link
 Logical representation of linked list. Each
node stores the data and address to the
next node. First node also called as head
node and the only information about the
list that we keep all the time is address of
the first node. The address of the last
node is null.

Linked List vs Array

Both Arrays and Linked List can be used to store linear data of similar types, but they both have
some advantages and disadvantages over each other.
Following are the points in favor of Linked Lists.
(1) The size of the array is fixed: So we must know the upper limit on the number of elements in
advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage,
and in practical uses, upper limit is rarely reached.
(2) Inserting a new element in an array (sorted) of elements is expensive, because room has to be
created for the new elements and to create room existing elements have to shifted.
Linked lists have following drawbacks
1) Random access is not allowed. We have to access elements sequentially starting from the first
node. So we cannot do binary search with linked lists.
2) Extra memory space for a pointer is required with each element of the list.
LINKED LIST VS ARRAY
Dynamically allocating
an array of size 4 to this
heap area will not be
possible because
contiguous block of 16
bytes is not available
here.
HEAP MEMORY(every block
represents 4 byte and white color
block represents free space)

But, Allocating a linked

list of size 4 to this heap
area will be possible
LINKED LIST OPERATIONS
• Insert at the beginning of the linked list
• Insert at the end of the linked list
• Insert at the given position of the linked list
• Delete from the beginning of the linked list
• Delete from the end of the linked list
• Delete from the given position of the linked list
• Search an element in a given linked list
• Reversing a linked list
• Merging two linked list
• Traversing of linked list
ALGORITHM TO DISPLAY THE CONTENT
20

20
FUNCTION TO SEARCH AN ITEM
LINKED LIST OPERATIONS
Operations on Linked Lists

Refer Program here linkedlist.c

DOUBLY LINKED LIST
A Doubly Linked List (DLL) contains an extra pointer, typically called previous pointer,
together with next pointer and data which are there in singly linked list.
DOUBLY LINKED LIST
Advantages over singly linked list
1) A DLL can be traversed in both forward and backward direction.
2) The delete operation in DLL is more efficient if pointer to the node to be deleted is
given.
In singly linked list, to delete a node, pointer to the previous node is needed. To get
this previous node, sometimes the list is traversed. In DLL, we can get the previous
node using previous pointer.
Disadvantages over singly linked list
1) Every node of DLL Require extra space for a previous pointer.
2) All operations require an extra pointer previous to be maintained. For example, in
insertion, we need to modify previous pointers together with next pointers. For
example in following functions for insertions at different positions, we need 1 or 2
extra steps to set previous pointer.
 INSERTION IN DOUBLY LINKED LIST
Insert a node at the front in a Doubly Linked List:
A new node is always added before the header of the given linked list. The task can be completed using
the following 5 steps:
•Firstly, allocate a new node (say new_node).
•Now put the required data in the new node.
•Make the next of new_node point to the current head of the doubly linked list.
•Make the previous of the current head point to new_node.
•Lastly, point head to new_node.

https://www.geeksforgeeks.org/introduction-and-insertion-in-a-doubly-linked-list/
39
 INSERTION IN DOUBLY LINKED LIST
// Given a reference (pointer to pointer) to the head of a list and an int, inserts a new node on the front of the list.
void push(struct Node** head_ref, int new_data)
{
// 1. allocate node
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
// 2. put in the data
new_node->data = new_data;
// 3. Make next of new node as head and previous as NULL
new_node->next = (*head_ref);
new_node->prev = NULL;
// 4. change prev of head node to new node
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
// 5. move the head to point to the new node
(*head_ref) = new_node;
} 40
 INSERTION IN DOUBLY LINKED LIST
Add a node in between two nodes:
It is further classified into the following two parts:
Add a node after a given node in a Doubly Linked List:
We are given a pointer to a node as prev_node, and the new node is inserted after the given node. This can be done using the
following 6 steps:
•Firstly create a new node (say new_node).
•Now insert the data in the new node.
•Point the next of new_node to the next of prev_node.
•Point the next of prev_node to new_node.
•Point the previous of new_node to prev_node.
•Change the pointer of the new node’s previous pointer to new_node.

41
 INSERTION IN DOUBLY LINKED LIST
To insert a node after a given node in the linked list: (Given a node as prev_node, insert a new node after the given node)
void insertAfter(struct Node* prev_node, int new_data)
{
// Check if the given prev_node is NULL
if (prev_node == NULL) {
printf("the given previous node cannot be NULL");
return;
}
// 1. allocate new node
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
// 2. put in the data
new_node->data = new_data;
// 3. Make next of new node as next of prev_node
new_node->next = prev_node->next;
// 4. Make the next of prev_node as new_node
prev_node->next = new_node;
// 5. Make prev_node as previous of new_node
new_node->prev = prev_node;
// 6. Change previous of new_node's next node
if (new_node->next != NULL)
new_node->next->prev = new_node;
42
 INSERTION IN DOUBLY LINKED LIST
Add a node before a given node in a Doubly Linked List:
Let the pointer to this given node be next_node. This can be done using the following 6 steps.
• Allocate memory for the new node, let it be called new_node.
• Put the data in new_node.
• Set the previous pointer of this new_node as the previous node of the next_node.
• Set the previous pointer of the next_node as the new_node.
• Set the next pointer of this new_node as the next_node.
• Now set the previous pointer of new_node.
• If the previous node of the new_node is not NULL, then set the next pointer of this previous node as new_node.
• Else, if the prev of new_node is NULL, it will be the new head node.

43
 INSERTION IN DOUBLY LINKED LIST
// Given a node as prev_node, insert a new node after the given node
void insertBefore(struct Node* next_node, int new_data)
{
// Check if the given next_node is NULL
if (next_node == NULL) {
printf("the given next node cannot be NULL");
return;
}
// 1. Allocate new node
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
// 2. Put in the data
new_node->data = new_data;
// 3. Make previous of new node as previous of next_node
new_node->prev = next_node->prev;
// 4. Make the previous of next_node as new_node
next_node->prev = new_node;
// 5. Make next_node as next of new_node
new_node->next = next_node;
// 6. Change next of new_node's previous node
if (new_node->prev != NULL)
new_node->prev->next = new_node;
else
44
 INSERTION IN DOUBLY LINKED LIST
Insert a node at the end in a Doubly Linked List:
The new node is always added after the last node of the given Linked List. It can be done using the
following 7 steps:
• Create a new node (say new_node).
• Put the value in the new node.
• Make the next pointer of new_node as null.
• If the list is empty, make new_node as the head.
• Otherwise, travel to the end of the linked list.
• Now make the next pointer of last node point to new_node.
• Change the previous pointer of new_node to the last node of the list.

45
 INSERTION IN DOUBLY LINKED LIST
// Given a reference (pointer to pointer) to the head of a DLL and an int, appends a new node at the end
void append(struct Node** head_ref, int new_data)
{
// 1. allocate node
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head_ref; /* used in step 5*/
// 2. put in the data
new_node->data = new_data;
// 3. This new node is going to be the last node, so
// make next of it as NULL
new_node->next = NULL;
// 4. If the Linked List is empty, then make the new
// node as head
if (*head_ref == NULL) {
new_node->prev = NULL;
*head_ref = new_node;
return;
}
// 5. Else traverse till the last node
while (last->next != NULL)
last = last->next;
// 6. Change the next of last node
last->next = new_node;
// 7. Make last node as previous of new node
new_node->prev = last;
return;}
46
 DELETION IN DOUBLY LINKED LIST
We can delete an element in a list from:
• From beginning
• From end
• From middle
Delete from End:
Point head to the previous element i.e. last
second element
Change next pointer to null
Delete from Beginning:
struct node *end = head;
Point head to the next node i.e. second node
struct node *prev = NULL;
temp = head
while(end->next)
head = head->next
{
prev = end;
Make sure to free unused memory
end = end->next;
free(temp); or delete temp;
}
prev->next = NULL;

Make sure to free unused memory

free(end); or delete end;

47
 DELETION IN DOUBLY LINKED LIST
Delete from Middle:
Keeps track of pointer before node to delete and pointer to node to delete
temp = head;
prev = head;
for(int i = 0; i < position; i++)
{
if(i == 0 && position == 1)
head = head->next;
free(temp)
else
{
if (i == position - 1 && temp)
{
prev->next = temp->next;
free(temp);
}
else
{
prev = temp;
if(prev == NULL) // position was greater than number of nodes in the list
break;
temp = temp->next; }}}

48
DOUBLY LINKED LIST OPERATIONS
Note: Doubly linked list
operations like insertion at
• Refer Program here double.c begin, insertion at end and
insertion at middle are present
in the attached code. You need
to complete deletion at
beginning, deletion at end and
deletion at a position on your
own
 CIRCULAR LINKED LIST
In a circular linked list, the first node and the last node are linked together to form a circle. There is no NULL at the end.

Advantages of a Circular linked list

• Entire list can be traversed from any node.
• Circular lists are the required data structure when we want a list to be accessed in a circle or loop.
• Despite of being singly circular linked list we can easily traverse to its previous node, which is not possible in singly linked list.
Disadvantages of Circular linked list
• Circular list are complex as compared to singly linked lists.
• Reversing of circular list is a complex as compared to singly or doubly lists.
• If not traversed carefully, then we could end up in an infinite loop.
• Like singly and doubly lists circular linked lists also doesn’t support direct accessing of elements.
50
 OPERATIONS ON CIRCULAR LINKED LIST
Creation of list
Traversal of list
Insertion of node
• At the beginning of list
• At any position in the list
Deletion of node
• Deletion of first node
• Deletion of node from middle of the list
• Deletion of last node
Counting total number of nodes
Reversing of list
51
CREATION AND TRAVERSAL OF A CIRCULAR LIST
#include <stdio.h>
#include <stdlib.h>
/* Basic structure of Node */

struct node {
int data;
struct node * next;
}*head;
int main()
{
int n, data;
head = NULL;

printf("Enter the total number of nodes in list: ");

scanf("%d", &n);
createList(n); // function to create circular linked list
displayList(); // function to display the list

return 0;
} 52
 CREATION AND TRAVERSAL OF A CIRCULAR LIST
void createList(int n)
{
int i, data;
struct node *prevNode, *newNode;
if(n >= 1){ /* Creates and links the head node */
head = (struct node *)malloc(sizeof(struct node));
printf("Enter data of 1 node: ");
scanf("%d", &data);
head->data = data;
head->next = NULL;
prevNode = head;
for(i=2; i<=n; i++){ /* Creates and links rest of the n-1 nodes */
newNode = (struct node *)malloc(sizeof(struct node));
printf("Enter data of %d node: ", i);
scanf("%d", &data);
newNode->data = data;
newNode->next = NULL;
prevNode->next = newNode; //Links the previous node with newly created node
prevNode = newNode; //Moves the previous node ahead
}
prevNode->next = head; //Links the last node with first node
printf("\nCIRCULAR LINKED LIST CREATED SUCCESSFULLY\n");
}}
53
 CIRCULAR LINKED LIST: TRAVERSAL OF LIST
void displayList()
{
struct node *current;
int n = 1;
if(head == NULL)
{
printf("List is empty.\n");
}
else
{
current = head;
printf("DATA IN THE LIST:\n");

do {
printf("Data %d = %d\n", n, current->data);

current = current->next;
n++;
}while(current != head);
}}
54
REPRESENTING A POLYNOMIAL USING A LINKED LIST

• Store the coefficient and exponent of each term in nodes

– int [] item1 = {5, 12}
– int [] item2 = {2, 9}
– int [] item3 = {-1, 3}

5 x12  2 x 9  x3
5 12 2 9 -1 3
ADDITION OF TWO POLYNOMIALS
Example:
Addition of the following polynomials

5 x12  2 x 9  x3
The results should
11 be :
5x  4 x9  2 x3  x

5 x12  5 x11  2 x9  x3  x
ADDITION OF TWO POLYNOMIALS
• Represent two polynomials in two linked lists l1 and l2
• Create a third empty linked list l3
• Compare the items in l1 with the items in l2, If there is no item having the same
exponent, append these items to the third list. If there are two items with the same
exponent exp and coefficient coff1 and coff2, append an item with exponent exp
and coefficient coff1+coff2 to l3

poly.c
SUBTRACTION OF TWO POLYNOMIALS
Example:
Subtraction of the following polynomials

5 x12  2 x 9  x3
The results should
11 be :
5x  4 x9  2 x3  x

5 x12  5 x11  6 x 9  3x 3  x
SUBTRACTION OF TWO POLYNOMIALS
f(x) and g(x) are two polynomials. In order to solve f(x)-g(x):
• Represent two polynomials in two linked lists (l1 for f(x) and l2 for g(x))
• Create an empty linked lists l3 Negate the coefficient of all items in l2 and append
these items to l3
• Add l1 to l3 (Use algorithm: Addition of two polynomials)

Note: Write program for addition and subtraction of polynomials by your own
MULTIPLICATION OF TWO POLYNOMIALS
f(x) and g(x) are two polynomials. In order to solve f(x)*g(x):
• Represent two polynomials in two linked lists (l1 for f(x) and l2 for g(x))
• For each item i in l1, multiply i with l2 and store the result in a new list. Add all the
new lists together.
• To multiply an item i with a list l. You need to multiply i with each item in l and
store the results in a new list.
• Multiply an item i (exp1, coff1)with an item j(exp2, coff2), you get an item k
(exp1+exp2, coff1*coff2)
APPLICATION OF LINKED LIST: POLYNOMIAL
MANIPULATION.
• Polynomial Manipulation is one of the common application of linked list.
• Representing and performing various basic operations on polynomials.
• The basic structure of the linked list for polynomial manipulation is
// Structure representing a term in a polynomial
struct Term {
int coefficient;
int exponent;
struct Term* next;
};

61
 FUNCTIONS : POLYNOMIAL MANIPULATION .
Create node:
– Allocates memory for a new term using malloc.
– Initializes the coefficient and exponent fields with the provided data.
– Sets the next pointer to NULL.
– Returns a pointer to the newly created term.
struct Term* createTerm(int coefficient, int exponent) {
struct Term* newTerm = (struct Term*)malloc(sizeof(struct
Term));
if (newTerm == NULL) {
// Handle memory allocation failure
printf("Memory allocation failed.\n");
exit(EXIT_FAILURE);
}
newTerm->coefficient = coefficient;
newTerm->exponent = exponent;
newTerm->next = NULL;
return newTerm;
}

62
FUNCTIONS : POLYNOMIAL MANIPULATION .
• Add Term:
– Adds a new term to a polynomial.
– If the polynomial is empty, sets the new term as
the head.
void addTerm(struct Term** poly, int coefficient, int exponent)
{
struct Term* newTerm = createTerm(coefficient, exponent);

if (*poly == NULL) {
*poly = newTerm;
} else {
struct Term* temp = *poly;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newTerm;
}
}

63
 FUNCTIONS : POLYNOMIAL MANIPULATION .
• Add Polynomials:
– Adds two polynomials and returns the result. struct Term* addPolynomials(struct Term* poly1, struct Term*
poly2) {
– Iterates through both polynomials, adding
struct Term* result = NULL;
corresponding terms.
while (poly1 != NULL || poly2 != NULL) {
int coef1 = (poly1 != NULL) ? poly1->coefficient : 0;
int coef2 = (poly2 != NULL) ? poly2->coefficient : 0;
int exp1 = (poly1 != NULL) ? poly1->exponent : 0;
int exp2 = (poly2 != NULL) ? poly2->exponent : 0;

int sum_coef = coef1 + coef2;

addTerm(&result, sum_coef, exp1);

if (poly1 != NULL) poly1 = poly1->next;

if (poly2 != NULL) poly2 = poly2->next;
}

return result;
}
64
 FUNCTIONS : POLYNOMIAL MANIPULATION .
• Display Polynomial:
– Displays the elements of a polynomial. void displayPolynomial(struct Term* poly) {
if (poly == NULL) {
– Prints each term's coefficient and exponent.
printf("Polynomial is empty.\n");
– Adds a plus sign between return;
terms for better readability. }

while (poly != NULL) {

printf("%dx^%d", poly->coefficient, poly->exponent);

if (poly->next != NULL) {
printf(" + ");
}

poly = poly->next;
}

printf("\n");
}

65
MERGING OF TWO SORTED LINKED LIST

• https://dotnettutorials.net/lesson/how-to-merge-two-linked-lists/
LAB EXPERIMENTS
Write a menu driven program for all the operations in case of singly linked list,
circular singly linked list, doubly linked list, circular doubly linked list.
• Insert at the beginning of the linked list
• Insert at the end of the linked list
• Insert at the given position of the linked list
• Delete from the beginning of the linked list
• Delete from the end of the linked list
• Delete from the given position of the linked list
• Search an element in a given linked list
• Reversing a linked list
• Merging two linked list
• Traversing/ Display of linked list
• Detect loop in a linked list (not in case of circular singly and circular doubly)
LAB EXPERIMENTS
Write programs for the
• Addition
• Subtraction
• Multiplication
of two polynomials using linked lists
PRACTICE MCQ QUESTIONS ON LINKED LIST

• https://www.geeksforgeeks.org/data-structure-gq/top-mcqs-on-linked-list-data-
structure-with-answers/
TO P 5 0 PRO B L E M S O N LI N K E D L I ST DATA ST RU C TU R E A SK E D I N S D E
I N T E RVI E WS

• https://www.geeksforgeeks.org/top-20-linked-list-interview-question/
REAL LIFE EXAMPLES OF DIFFERENT TYPES OF LINKED
LIST

• Singly Linked List: Example: Imagine a playlist in a music player. Each song is a
node in the singly linked list, and each node contains information about the song
and a reference to the next song in the playlist.
• Node 1 Node 2 Node 3
• +---------+ +---------+ +---------+
• | Song 1 | -> | Song 2 | -> | Song 3 |
• +---------+ +---------+ +---------+

• Doubly Linked List: Example: Consider a browser history where each webpage is
a node. In a doubly linked list, each node has a reference to the previous and next
pages.
• +---------+ +---------+ +---------+
• (null) <- | Page 1 | <-> | Page 2 | <-> | Page 3 | -> (null)
• +---------+ +---------+ +---------+
• Singly Circular Linked List: Example: A round-robin scheduling algorithm in operating
systems. The process queue is implemented as a singly circular linked list. After the last
process, it cycles back to the first process.
• +---------+ +---------+ +---------+
• | Process1| -> | Process2| -> | Process3|
• +---------+ +---------+ +---------+
• ^ |
• |-----------------------------------|
• Doubly Circular Linked List: Example: A deck of cards in a card game where each card
is a node. It's a doubly circular linked list because you can navigate forward and backward
through the deck, and after the last card, it cycles back to the first card.
• +---------+ +---------+ +---------+
• <->| Card1 | <->| Card2 | <->| Card3 | <->
• +---------+ +---------+ +---------+
• | |
• +-----------------------------------+
APPLICATIONS OF LINKED LIST
• Polynomial manipulation
• Support for other data structures: Some other data structures like stacks, queues,
hash tables, graphs can be implemented using a linked list.
• Memory Management: Memory management is one of the operating system's key
features. It decides how to allocate and reclaim storage for processes running on
the system. We can use a linked list to keep track of portions of memory available
for allocation.
• Linked allocation of files: A file of large size may not be stored in one place on a
disk. So there must be some mechanism to link all the scattered parts of the file
together. The use of a linked list allows an efficient file allocation method in which
each block of a file contains a pointer to the file's text block. But this method is
good only for sequential access.
HEADER LINKED LIST
• https://www.geeksforgeeks.org/header-linked-list-in-c/
GENERALIZED LINKED LIST
• https://www.geeksforgeeks.org/generalized-linked-list/

• A Generalized Linked List L, is defined as a finite sequence of n>=0 elements, l 1, l2,

l3, l4, …, ln, such that li are either item or the list of items. Thus L = (l1, l2, l3, l4, …,
ln) where n is total number of nodes in the list.
• To represent a list of items there are certain assumptions about the node structure.
• Flag = 1 implies that down pointer exists
• Flag = 0 implies that next pointer exists
• Data means the item.
• Down pointer is the address of node which is down of the current node
• Next pointer is the address of node which is attached as the next node
WHY GENERALIZED LINKED LIST?
• Generalized linked lists are used because although the efficiency of polynomial
operations using linked list is good but still, the disadvantage is that the linked list
is unable to use multiple variable polynomial equation efficiently. It helps us to
represent multi-variable polynomial along with the list of elements.

• When first field is 0, it indicates that the second field is variable. If first field is 1
means the second field is a down pointer, means some list is starting.
POLYNOMIAL REPRESENTATION USING GENERALIZED
LINKED LIST
• The typical node structure will be:

•Here Flag = 0 means variable is present

•Flag = 1 means down pointer is present
•Flag = 2 means coefficient and exponent is
present
-4X Y Z + 10X YZ +7XYZ +45
4 2 3 2 2
SENTINEL NODE
• Sentinel nodes are specially designed nodes that do not hold or refer to any data of
the linked list.
• To make insertion and deletion operations in a linked-linked list simple, we have to
add one sentinel node at the beginning of the linked list and one at the end of the
linked list, as shown in the below diagram.
 DOUBLY LINKED LIST: SENTINEL OR “DUMMY NODES
When implementing a doubly linked lists, we add two special nodes to the ends of the lists: the header
and trailer nodes.
• The header node goes before the first list element. It has a valid next link but a null prev link.
• The trailer node goes after the last element. It has a valid prev reference but a null next reference.

NOTE: the header and trailer

nodes are sentinel or
“dummy” nodes because they
do not store elements. Here’s
a diagram of our doubly
linked list:

82
ADVANTAGES OF SENTINEL NODE:

• The most significant advantage of using the sentinel nodes in the linked list:
• By adding the sentinel nodes to the doubly linked list now for
the deletion or insertion at the beginning, end or in between the beginning and
end nodes of the linked list, we do not need to write the different conditions for
each one.
• All these operations can be done as the deletion or insertion between the beginning
and end node of a doubly linked list.
SKIP LIST
• https://www.geeksforgeeks.org/skip-list/
• A skip list is a data structure that allows for efficient search, insertion and deletion of
elements in a sorted list. It is a probabilistic data structure, meaning that its average
time complexity is determined through a probabilistic analysis.
• In a skip list, elements are organized in layers, with each layer having a smaller
number of elements than the one below it. The bottom layer is a regular linked list,
while the layers above it contain “skipping” links that allow for fast navigation to
elements that are far apart in the bottom layer. The idea behind this is to allow for
quick traversal to the desired element, reducing the average number of steps needed
to reach it.
• Skip lists are implemented using a technique called “coin flipping.” In this technique,
a random number is generated for each insertion to determine the number of layers
the new element will occupy. This means that, on average, each element will be in
log(n) layers, where n is the number of elements in the bottom layer.
• Skip lists have an average time complexity of O(log n) for search, insertion and
deletion, which is similar to that of balanced trees, such as AVL trees and red-black
trees, but with the advantage of simpler implementation and lower overhead.
SKIP LIST.

• Based on the concept of simple linked list.

• Elements are organized in layers.
• Bottom layer is the regular linked list.
• Rest of the lists having fewer elements than the bottom lint.
• No new element is added in the list layers.
Node structure is shown below
struct Node {
int data;
struct Node* next[MAX_LEVEL];
}; //MAX_LEVEL defining the number of layers

85
CAN WE SEARCH IN A SORTED LINKED LIST BETTER
THAN O(N) TIME?

• The worst-case search time for a sorted linked list is O(n) as we can only linearly
traverse the list and cannot skip nodes while searching. For a Balanced Binary
Search Tree, we skip almost half of the nodes after one comparison with the root.
For a sorted array, we have random access and we can apply Binary Search on
arrays. Can we augment sorted linked lists to search faster? The answer is Skip
List. The idea is simple, we create multiple layers so that we can skip some nodes.
See the following example list with 16 nodes and two layers. The upper layer works
as an “express lane” that connects only the main outer stations, and the lower layer
works as a “normal lane” that connects every station. Suppose we want to search
for 50, we start from the first node of the “express lane” and keep moving on the
“express lane” till we find a node whose next is greater than 50. Once we find such
a node (30 is the node in the following example) on “express lane”, we move to
“normal lane” using a pointer from this node, and linearly search for 50 on “normal
lane”. In the following example, we start from 30 on the “normal lane” and with
linear search, we find 50.