Chapter Three: Linked list

This chapter covers:-

♪ Define Data structure
♪ Linked list
♪ Types of linked List
♪ Skip lists
♪ Self-organizing lists
♪ Sparse tables
♪ Advantage of linked list

1
 Data structure and Modelled
 Data structure is the way of organizing all data
items in order that not only elements to be
stored but also the relation between the
elements.
• In data can be seen from three different levels
application of model:
i) Application (user) level – is a level which
models real life data in a specific context.
• It answers the question “why data is needed
to be modelled?”
• e.g. BHU Hospital , Library, student cafeteria
and etc
2
 ii) Logical level
• Logical or abstract data type level – indicates the abstract view of the
domain and operations.
• It specifies the type of data stored and the operations supported on
them and user to create data types to their own specifications.
• The purpose to answer the question “what data is to be stored?” and
“what operations are made on the data?”

Example: data to be stored ( domain of application) – collection books

valid operations on this domain
 searching books
 Sorting data of book by title, author, publication year
 Inserting (adding) new books
 Reserving books
 Selling a car ( not valid operation)

3
iii) Implementation ( Data structure) level
• Implementation ( Data structure) level – is a
specific representation of the data structure
to hold the data items and the coding for
operations.
It answers “how is data represented?”.
Example:
int BookId[1000];
bool BooksRes[1000]; {
char BookTitle[1000][15];
4
Data structure

5
 Array compare within linked list
What are the problems • Linked list
with Arrays • Size is not fixed
• Size is fixed • Data can be stored at
• Array Items are stored any place.
contiguously. • Insertions and
• Insertions and deletion deletions are simple
at particular position is and faster.
complex.

6
 Linked List
• A linked list is a data structure which is built from
structures and pointers.
• It forms a chain of "nodes" with pointers representing
the links of the chain and holding the entire thing
together.
List is a finite, ordered sequence of data items known as
elements.
• “Ordered” in this definition means that each element
has a position in the list
Each list element has a data type
• A list is said to be empty when it contains no elements.
• The number of elements currently stored is called the
length of the list.
• The beginning of the list is called the head, the end of
the list is called the tail.
7
 Linked List cont….
•Linked lists are the most basic self-referential structures.
Linked lists allow you to have a chain of struct with
related data.
Node:- is a collection of elements, each of which stores
two types of fields.
1. Data items: holds the actual elements on the list and
2. pointer field: contains the address of the next and/or
previous node in the list.
Creating Linked Lists in C++
A linked list is a data structure that is built from
structures and pointers.
It forms a chain of "nodes" with pointers representing
the links of the chain and holding
8
 Creating Linked Lists in C++
• Start (Head): Special pointer that points to the
first node of a linked list, so that we can keep
track of the linked list.
• The last node should points to NULL.
Syntax
struct node{
int data;
node *next;
};node *head = NULL;

9
 Creating Linked Lists in C++
• linked list has four nodes in it, each with a link
to the next node in the series.
• The last node has a link to the special value
NULL, which any pointer (whatever its type)
can point to, to show that it is the last link in
the chain

10
 Cont….
There is also another special pointer, called Start, which
points to the first link in the chain so that we can keep
track of it.
struct node {
char name[20]; // Name of up to 20 letters
int age
float height; // In metres
node *nxt;// Pointer to next node
};struct node *start_ptr = NULL;
 C++ where you are allowed to refer to a data
type (in this case node)
 declared a pointer called start_ptr that will
permanently point to the start of the list
 start_ptr is set to NULL

11
 Adding a node to the list
• we declare the space for a pointer item and
assign a temporary pointer to it.
• Firstly, we declare the space for a pointer item
and assign a temporary pointer to it. This is
done using the new statement follows:
• temp = new node;
temp = new node;

12
 Adding a node to the list
• new node as *temp, i.e. "the node that temp
points to".
• When the fields of this structure are referred
to, brackets can be put round the *temp part,
as otherwise the compiler will think we are
trying to refer to the fields of the pointer.

13
 declared the node in c++
• Having declared the node, we ask the user to fill
in the details of the person, i.e. the name, age,
address or whatever:
cout << "Please enter the name of the person: ";
cin >> temp->name;
cout << "Please enter the age of the person : ";
cin >> temp->age;
cout << "Please enter the height of the person : ";
cin >> temp->height;
temp->nxt = NULL;
14
 declared the node in c++
• The last line sets the pointer from this node to
the next to NULL, indicating that this node, when
it is inserted in the list, will be the last node.
• Having set up the information, we have to decide
what to do with the pointers.
• Of course, if the list is empty to start with, there's
no problem - just set the Start pointer to point to
this node (i.e. set it to the same value as temp):
if (start_ptr == NULL)
start_ptr = temp;

15
 declared the node in c++
• It is harder if there are already nodes in the list. In
this case, the secret is to declare a second
pointer, temp2, to step through the list until it
finds the last node.
temp2 = start_ptr; // We know this is not NULL -
list not empty!
while (temp2->nxt != NULL)
{ temp2 = temp2->nxt; // Move to next link in
chain
}

16
 Declared the node in c++
• The loop will terminate when temp2 points to
the last node in the chain, and it knows when
this happened because the nxt pointer in that
node will point to NULL.
• When it has found it, it sets the pointer from
that last node to point to the node we have
just declared:
temp2->nxt = temp;

17
void add_node_at_end liked list
 link temp2->nxt in this diagram is the link
joining the last two nodes.
 The full code for adding a node at the end of
the list

18
 add_node_at_end liked list
void add_node_at_end ()
{ node *temp, *temp2; // Temporary pointers
// Reserve space for new node and fill it with data
temp = new node;
cout << "Please enter the name of the person: ";
cin >> temp->name;
cout << "Please enter the age of the person : ";
cin >> temp->age;
cout << "Please enter the height of the person : ";
cin >> temp->height;
temp->nxt = NULL;

19
 add_node_at_end liked list(cont)
// Set up link to this node
if (start_ptr == NULL)
start_ptr = temp;
else
{ temp2 = start_ptr;
// We know this is not NULL - list not empty!
while (temp2->nxt != NULL)
{ temp2 = temp2->nxt;
// Move to next link in chain
}
temp2->nxt = temp;
}
}

20
 Displaying the list of nodes
 Added one or more nodes, we need to display the list
of nodes on the screen
1.Set a temporary pointer to point to the same thing as
the start pointer.
2.If the pointer points to NULL, display the message "End
of list" and stop.
3.Otherwise, display the details of the node pointed to by
the start pointer.
4.Make the temporary pointer point to the same thing as
the nxt pointer of the node it is currently indicating.
5.Jump back to step 2.

21
 Displaying the list of nodes
Here is the C++ code that does the job:
temp = start_ptr;
do
{ if (temp == NULL)
cout << "End of list" << endl;
else
{ // Display details for what temp points to
cout << "Name : " << temp->name << endl;
cout << "Age : " << temp->age << endl;
cout << "Height : " << temp->height << endl;
cout << endl; // Blank line

// Move to next node (if present)

temp = temp->nxt;
}
} while (temp != NULL); 22
 Linked Lists
A linked list is a linear data structure.
• Allocate a new node.
• Nodes make up linked lists.
• Nodes are structures made up of data and a
pointer to another node.
• Usually the pointer is called next.

23
 Linear(singly) Linked List
 Elements organized in linear fashion.
 List terminates at a point.
 Last node points to NULL
 It’s navigation for ward only
 Single link list maintain its element a certain order,
as determined by chain of next link.
 Singly link list is not predetermined fized size.
 It is resized by add Or removing the node.

4
Circular Singly Linked List

25
Cont…

26
27
 Singly Linked List
Each node has only one link part.
Each link part contains the address of the next
node in the list.
Link part of the last node contains NULL value
which signifies the end of the node.

28
 Operations on sll

 Create list
 Insert an element into list
 Delete an element from the list
 Search an element in the list

29
30
 Creating a node
struct node{
int data; // A simple node of a linked list
node*next;
}*start; //start points at the first node
start=NULL ; initialised to NULL at beginning

node* create( int num) //say num=1 is passed from main

{
node*ptr;
ptr= new node; //memory allocated dynamically
if(ptr==NULL)
‘OVERFLOW’ // no memory available
exit(1);
else
{
ptr->data=num;
ptr->next=NULL;
return ptr;
}
}

31
 Inserting the node in a SLL
There are 3 cases here:-
• Insertion at the beginning
• Insertion at the end
• Insertion after a particular node
Insertion at the beginning
There are two steps to be followed:-
a) Make the next pointer of the node point
towards the first node of the list.
b) Make the start pointer point towards this new
node
 If the list is empty simply make the start pointer
point towards the new node.
32
Insertion at the beginning sll

33
 Insertion at the beginning sll
void insert_beg(node* p)
{
node* temp;
if(start==NULL) //if the list is empty
{
start=p;
cout<<”\nNode inserted successfully at the
beginning”;
}
else {
temp=start;
start=p;
p->next=temp; //making new node point at
} the first node of the list
}

34
 Inserting at the end sll
Here we simply need to make the next pointer
of the last node point to the new node

35
 Code of Inserting at the end sll
void insert_end(node* p)
{
node *q=start;
if(start==NULL)
{
start=p;
cout<<”\nNode inserted successfully at the end…!!!\n”;
}
else{
while(q->link!=NULL)
q=q->link;
q->next=p;
}
}

36
 Inserting after an element
Here we again need to do 2 steps :-
• Make the next pointer of the node to be
inserted point to the next node of the node
after which you want to insert the node.
• Make the next pointer of the node after which
the node is to be inserted, point to the node
to be inserted .

37
Example :-Inserting after an element

38
 code :-Inserting after an element
void insert_after(int c,node* p)
{
node* q;
q=start;
for(int i=1;i<c;i++)
{
q=q->link;
if(q==NULL)
cout<<”Less than “<<c<<” nodes in the list…!!!”;
}
p->link=q->link;
q->link=p;
cout<<”\nNode inserted successfully”;
}

39
 Deleting a node in SLL
• Here also we have three cases:-

• Deleting the first node

• Deleting the last node

• Deleting the intermediate node

40
 Deleting the first node
• Here we apply 2 steps:-
• Making the start pointer point towards the
2nd node
• Deleting the first node using delete keyword

41
 Deleting the first node
void del_first()
{
if(start==NULL)
cout<<”\nError……List is empty\n”;
else
{
node* temp=start;
start=temp->link;
delete temp;
cout<<”\nFirst node deleted successfully….!!!”;
}
}

42
43
 Delete last node in sll
void del_last()
{
if(start==NULL)
cout<<”\nError….List is empty”;
else
{
node* q=start;
while(q->link->link!=NULL)
q=q->link;
node* temp=q->link;
q->link=NULL;
delete temp;
cout<<”\nDeleted successfully…”;
}
}
}

44
45
 Deleting particular node
void del(int c)
{
node* q=start;
for(int i=2;i<c;i++)
{
q=q->link;
if(q==NULL)
cout<<”\nNode not found\n”;
}
if(i==c)
{
node* p=q->link; //node to be deleted
q->link=p->link; //disconnecting the node p
delete p;
cout<<“Deleted Successfully”;
}
}

46
 Searching a SLL
• Searching involves finding the required
element in the list
• We can use various techniques of searching
like linear search or binary search where
binary search is more efficient in case of
Arrays
• But in case of linked list since random access is
not available it would become complex to do
binary search in it
• We can perform simple linear search traversal

47
In linear search each node is traversed till the data in
the node matches with the required value

void search(int x)
{
node*temp=start;
while(temp!=NULL)
{
if(temp->data==x)
{
cout<<“FOUND ”<<temp->data;
break;
}
temp=temp->next;
}
}

48
 Doubly linked list
1. Doubly linked list is a linked data structure that consists of a set of
sequentially linked records called nodes.
2 . Each node contains three fields ::
 one is data part which contain data only.
 two other field is links part that are point
 references to the previous or to the next node in the sequence of nodes.
3. The beginning and ending nodes' previous and next
links, respectively, point to some kind of terminator,
typically a sentinel node or null to facilitate traversal
of the list.

49
Structure of DLL
struct node
{
int data;
node*next;
node*previous; //holds the address of previous node
}; node *head = NULL, *tail = NULL;

50
Inserting at beginning

51
 Inserting at the beginning Dll
void insert_beg(node *p)
{
if(start==NULL)
{
start=p;
cout<<"\nNode inserted successfully at the beginning\m";
}
else
{
node* temp=start;
start=p;
temp->previous=p; //making 1st node’s previous point to the new node
p->next=temp; //making next of the new node point to the 1st node
cout<<"\nNode inserted successfully at the beginning\n";
}

52
Inserting at the end Dll

53
 Inserting at the end
void insert_end(node* p)
{
if(start==NULL)
{
start=p;
cout<<"\nNode inserted successfully at the end";
}
else
{
node* temp=start;
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=p;
p->previous=temp;
cout<<"\nNode inserted successfully at the end\n";
}
}

54
55
 Inserting after a node in Dll
void insert_after(int c,node* p)
{
temp=start;
for(int i=1;i<c-1;i++)
{
temp=temp->next;
}
p->next=temp->next;
temp->next->previous=p;
temp->next=p;
p->previous=temp;
cout<<"\nInserted successfully";
}

56
 Deleting a node in Dll
• Node deletion from a DLL involves changing two
links
• In this example,we will delete node b
Head
a b c

• We don’t have to do anything about the links in

node b
• Garbage collection will take care of deleted nodes
• Deletion of the first node or the last node is a
special case
57
 Deleting a node in Dll
void del_at(int c)
{
node*s=start;
{
for(int i=1;i<c-1;i++)
{
s=s->next;
}
node* p=s->next;
s->next=p->next;
p->next->previous=s;
delete p;
cout<<"\nNode number "<<c<<" deleted successfully";
}
}
}

58
 Circular linked list
 Last node does not contain a NULL pointer

 It points to the first node

 Circular link list has no beginning and end

 Special node which, we call “cursor“

 The cursor node allows front and back.

59
 Syntax of Circular LL
struct node
{
int data;
node *prev;
node *next;
};
node *head = NULL, *tail = NULL;

60
 Adding a node to the front of a Circular Singly linked list
void insert_front(int x)
{
node *temp = new node;
temp->data = x;
temp->next = temp;
if(head==NULL)
head = temp;
else
{
node *temp2 = head;
while(temp2->next!=head)
{
temp2 = temp2->next;
}
temp->next = head;
head = temp;
temp2->next = temp;
}
}
61
 Adding a node to the left Circular Singly linked list
void insert_left_y(int x, int y)
{
node *temp=new node;
temp->data=x;
temp->next=temp;
if(head==NULL)
head = temp;
else
if(head->data==y)
{
node *temp2 = head;
while(temp2->next!=head)
{
temp2 = temp2->next;
}

62
 Adding a node to the left in Circular
Singly linked list
temp->next = head;
head = temp;
temp2->next = temp;
}
else
{
node *temp2 = head;
node *temp3;
while(temp2->data!=y)
{
temp3 = temp2;
temp2 = temp2->next;
}
temp->next = temp3->next;
temp3->next = temp;
}
} 63
 Adding a node to the right in Circular
Singly linked list
void insert_right_y(int x, int y)
{
node *temp=new node;
temp->data=x;
temp->next=temp;
if(head==NULL)
head = temp;
else
{
node *temp2 = head;
while(temp2->data!=y)
{
temp2 = temp2->next;
}
temp->next = temp2->next;
temp2->next = temp;
}

64
Deleting a node from the end of a
Circular Singly linked list
void delete_end()
{
node *temp, *temp2;
if(head==NULL)
cout <<"No data inside\n";
else
{
temp = head;
while(temp->next!=head)
{
temp2 = temp;
temp = temp->next;
}
temp2->next = temp->next;
delete temp;
}
}
65
Deleting a node from the front of a
Circular Singly linked list
void delete_front()
{
node *temp;
if(head==NULL)
cout <<"No data inside\n";
else {
temp = head;
node *temp2 = head;
while(temp2->next!=head)
{
temp2 = temp2->next;
}
temp2->next = head->next;
head = head->next;
delete temp;
}
}

66
 Deleting any node
 using the search data from a Circular Singly linked list
void delete_any(int x)
{
node *temp, *temp3;
if(head==NULL)
cout <<"No data inside\n";
else
if(head->data==x)
{
temp = head;
node *temp2 = head;
while(temp2->next!=head)
{
temp2 = temp2->next;
}
temp2->next = head->next;

67
 Deleting any node
 using the search data from a Circular Singly linked list
head->next;
delete temp;
}
else
{
temp = head;
while(temp->data!=x)
{
temp3 = temp;
temp = temp->next;
}
temp3->next = temp->next;
delete temp;
}
}

68
 skip list
• A skip list is a probabilistic data structure that
allows for fast search, insertion, and deletion
operations.
• It is an extension of a linked list with multiple
layers of linked lists, where higher layers skip over
fewer elements.
Structure:
• Each node contains a key and pointers to nodes
at the same level and below.
• The top layer is a single linked list containing all
elements, while lower layers skip over
progressively more elements.
69
 Con’t….
• An interesting data structure for efficiently
realizing the ordered map ADT is the skip list.
• This data structure makes random choices in
arranging the entries in such a way that search
and update times are O(logn) on average.
• The main advantage of using randomization
in data structure and algorithm design is that
the structures and functions that result are
usually simple and efficient.

70
 Con’t….
• A skip list S for a map M consists of a series of
lists {S0,S1, . . . ,Sh}.
• Each list Si stores a subset of the entries of M
sorted by increasing keys plus entries with two
special keys, denoted −∞ and +∞, where −∞
is smaller than every possible..

71
 Insertion in a Skip List
Algorithm SkipInsert(k,v):
Input: Key k and value v
Output: Topmost position of the entry inserted in the skip list
p←SkipSearch(k)
q←null
e←(k,v)
i←−1
repeat
i←i+1
if i ≥ h then
h←h+1 {add a new level to the skip list} t ←after(s)
s←insertAfterAbove(null, s, (−∞,null))
insertAfterAbove(s, t, (+∞,null))
while above(p) = null do
p←before(p) {scan backward} p←above(p) {jump up to higher level}
q←insertAfterAbove(p,q,e) {add a position to the tower of the new entry} until coinFlip() = tails
n←n+1
return q

72
 Searching in a Skip List
• Suppose we are given a search key k.
• We begin the Skip Search function by setting a position
variable p to the top-most, left position in the skip list S, called
the start
• position of S. That is, the start position is the position of Sh
storing the special entry with key −∞.
• key(p) denotes the key of the entry at position p:
1. If S.below(p) is null, then the search terminates we are at the
bottom and have located the largest entry in S with key less than
or equal to the search key k.
• Otherwise, we drop down to the next lower level in the
present tower by setting p←S.below(p).

73
 2. Starting at position p,
• we move p forward until it is at the right-most
position on the present level such that key(p) ≤
k.
• We call this the scan forward step.
• Note that such a position always exists, since
each level contains the keys +∞ and −∞.
• In fact, after we perform the scan forward for
this level, p may remain where it started.
• In any case, we then repeat the previous step.

74
 Example: Insertion
• Let’s insert values [3, 6, 9, 12] into a skip list
with coin-flip-based layering:
• Layer 0 (base): 3 → 6 → 9 → 12
• Layer 1: 3 → 9 → 12 (probabilistic skipping)
• Layer 2: 3 → 12
Searching for 9:
• Start at Layer 2: 3 → Next node is 12 (too
large).
• Drop to Layer 1: 3 → Move to 9 (found).
75
 Self-Organizing List
• A list that reorganizes itself based on access
patterns to optimize future operations.
• Common heuristics include Move-to-Front
(MTF) or Transpose.
Single-layer linked list
 Heuristic-based reordering
Worst case is O (n)
Optimizing access locality

76
 Example:
• Initial List: A → B → C → D
• Access C (MTF):
• New list: C → A → B → D
• Access B (MTF):
• New list: B → C → A → D
• Access C (Transpose):
• Swap C with B: A → C → B → D

77
 Sparse Table
• A Sparse Table is an efficient data structure used
primarily for answering range queries, particularly
those involving associative operations (like minimum,
maximum, and greatest common divisor) over an
immutable array.
• It allows queries to be answered in constant time after
an initial preprocessing phase.
Characteristics of Sparse Tables
• Immutable Data: It works best with static data (where
the input array doesn’t change).
• Preprocessing Time: The preprocessing to create the
Sparse Table takes O(nlogn) time, where n is the length
of the array.
• Query Time: After preprocessing, range queries can be
answered in O(1)O(1) time.
78
 Build the Sparse Table
• Create a 2D array st, where st[i][j] stores the
minimum value in the range arr[i] to arr[i + 2^j -
1].
Querying:
For a query on the range [L, R] :
k=floor(log2(R-L +1))
k=floor(log 2(R−L+1))
The answer will be min(st[L][k], st[R - (1 << k) +
1][k])

79
 Example :Sparse Table
Index: 0 1 2 3 4 5
Row 0: [1, 3, 2, 7, 9, 11] (original array)
Row 1: [1, 2, 2, 7, 7, 11] (min of pairs)
Row 2: [1, 2, 2, 7, X, X] (min of groups of 4)
Answer:

80
 Advantages of linked list
• Dynamic Data Structure: The size of linked list increase and
decrease during program execution.
• No memory wastage: In linked list memory will be
allocated at the time of program execution so no memory
wastage.
• Easily insert and delete data: In linked list you can insert
any data at specific position and also delete any data from
specific position.
Dis-Advantages of linked list
• Need more memory: For store data in linked list you need
more memory space, you need memory space for both
data and address part.

81
82