Linked List

Qurra-tul-ann
 Limitations of
Arrays
Arrays are stored in contiguous memory blocks. And have advantages and
disadvantages due to it.
• It is very easy to access any data element from array using index
• We need to know size of array before hand.
• We cannot resize array. Because They are static in size
• Insertion and deletion is very expensive because it needs shifting of elements
Solution: Linked list
A dynamic data structure in which each data element is linked with next
element through some link. Because each element is connected/linked, it will be
easy to insert and delete an element without shifting.

2
Linked List
• Linked list is a linear collection of homogenous data elements where
each element is connected through a link. The links are maintained using
pointers.
• A single element in linked list is normally called Node. Every node has
two parts:
▪ Data: actual information
▪ Next Link- a reference to next node in memory

data next link

• If next link is NULL, it means it is the last node of list.

• The address of the first node in the list is stored in a separate
3location, called the head or first.
Linked List
Linked list with 4 nodes
Head/Start

We always need location of the first node of list in order to process it for any
purpose.
• Head or Start node is reference which points to address of the first node of list.
• Because all nodes are connected only through pointers, so if we have this head, any
node can be accessed by traversal.
• If head is NULL, it means list is empty
4
Linked List
Linked list with 4 nodes
Head/Start

Tail

We always need to know the last node of list.

• Tail node last node of list whose next pointer will be null.
• We can use head to traverse through list to search for tail node.
• Or just like head we can maintain a tail reference too

5
Node
Node can be represented using either structure or class.

struct
Node{ int
Node Operations: data; Node*
next;
1. Constructing a new Node* node=new Node() }
node

2. Accessing the data value node-> data class Node {

int data;
Node* next;
3. Accessing the next pointer node->next }

6
Example using class:
#include<iostream>
using namespace std;

class Node {
public: int main() {
int data; Node* node1 = new Node(10);
Node* next; // Pointer to the next node cout<< node1->data<<endl;
cout<< node1->next<<endl;
Node(int data) { return 0;
this->data = data; }
this->next = NULL;
}
};
Example using Structure
#include <iostream> int main() {
Using namespace std; Node* newNode = new Node(20);
struct Node { cout <<"Node created using struct:" ;
int data; cout<< newNode->data << endl;
Node* next;
// Free allocated memory
// Constructor to initialize the node delete newNode;
Node(int value) { return 0;
data = value; }
next = nullptr;
}
};
Linked List Memory Representation
Linked list has nodes and memory has cells, nodes of list are distributed in
memory cells, each node is an object that is dynamically created at run time
and a free memory cell is allocated to that node.
Let say head node of a linked list is located at memory cell 1009. Its data is only an
integer value. It points to list’s 2nd node which is located at memory location 1001 ,2nd
node points to 3rd node which is located at 1011.

1009 1001 1011

head15 1001 78 10118 NULL

3rd node points to NULL address, means it is end of list

9
Linked List Operations
• Traversal
▪ Search, print, update etc.
• Insertion
• Deletion

10
Search
Algorithm:

Code:
void print(Node* &head) {
Node* temp = head;

while(temp != NULL) {
cout<<temp->data<<" “ ;
temp = temp->next;
}
cout<<endl;
}

11
Insertion
Inserting a new node involves two things:
• Creating a new node
• Linking this node to its logical predecessor and successor node, so all nodes still
remain linked
There can be three scenarios to insert a new node
• Insertion at Start
• Insertion at End
• Insertion at Middle

12
Insertion at Start:
• If List is Empty • List is not Empty
head NULL 1009 1001
head data 1001 data NULL
Create a Node and Update Head
1009 Create new node, and update head pointer
head data NULL 1009 1001
head data 1001 data NULL

1099
data 1009

13
Insertion at Start:
Adding a New Node is a Two-Step Process

Result of Reversing the Order of the Two Steps

Insertion at Start:
Algorithm:
• Create a new Node
• Point the new Node's next pointer to the current head.
• Update the head of the linked list as the new node

Code:
// inserting new node at head
void insertAtHead(Node* &head, int d) {
Node* temp = new Node(d);
temp->next = head;
head = temp;
}

15
Insertion at End:
• If List is Empty • Non-Empty List
head NULL 1009 1001
head data 1001 data NULL

Create a Node and Update Head Create new node

1009 1009 1001
head data NULL head data 1001 data 1099

Update pointer of last node

1099
data NULL

16
Insertion at End:
• Algorithm:
• Create a new Node
• If the linked list is empty, update the head as the new node.
• Otherwise traverse till the last node of the linked list.
• Update the next pointer of the last node from NULL to new node.

Code:
// inserting new node at tail or ending

void insertAtTail(Node* &tail, int d) {

Node* temp = new Node(d);
tail->next = temp;
tail = temp;
}

17
Insertion at Middle:
Let say we want to insert 13 in following list, at location 2.
1001 1099
1009
head 7 1099 11 NULL
9 1001
In this case, first we need to locate the 2nd node. That is node with data=7.
Now this will become 3rd node and new node will be inserted before this node.

1009 1001 1099

head 9 1019 7 1099 11 NULL
1019
13 1001

18
Insertion at Middle:
In order to insert somewhere middle of linked list, we need to maintain
two pointers, current and previous.
1009 1001 1099
head 91001 71099 11 NULL

prev curr
So when new node is inserted, we can easily change next links of new
node and previous node.
1009 1001 1099
head 9 1019 71099 11 NULL
1019
13 1001

19
Insertion at Middle:
void insertAtPosition(Node* &tail, Node* & head, int position, int d) {
if(position == 1) { //insert at Start
insertAtHead(head, d);
return;
}

Node* temp = head;

int cnt = 1;
while(cnt < position-1) {
temp = temp->next;
cnt++;
}
if(temp -> next == NULL) { //inserting at Last Position
insertAtTail(tail,d);
return ;
}
Node* nodeToInsert = new Node(d);
nodeToInsert -> next = temp -> next;
temp -> next = nodeToInsert;
}
Deletion
Deleting a new node involves two things:
• Unlinking the node in a way that its logical predecessor gets connected to next node of
list to maintain linking
There can be three scenarios to delete node
• Deletion from Start
• Deletion from End
• Deletion from Middle

21
Deletion
• Deletion From Start
1009 1001 1099
head 9 1001 7 1099 11 NULL

1001 1099
head 7 1099 11 NULL

• Deletion From End

1009 1001 1099
head 9 1001 7 1099 11 NULL

1009 1001
head 9 1001 7 NULL

22
Delete at Start:
Algorithm:
• Store the head of the linked list in a temp pointer.
• Update the head of the linked list to next node.
• Delete the temporary node stored in the temp pointer.

Code:
void deleteHead(int position, Node* & head){
Node* temp = head;
head = head -> next;
temp -> next = NULL; //memory free start node
delete temp;
}

23
Deletion at Location:
• This case involves searching a specific node to delete
• We also need to find current and previous node pointers in order to maintain links.
• Current will be our required node. Let say we need to delete 2nd from following list We need
to search 2nd in list, and then need to find its previous node also, so before deletion we can
link previous node to next node of 2nd node

1009 1001 1099

head 9 1001 7 1099 11 NULL

prev curr

24
Deletion at Location:
1009 1001 1099
head 9 1001 7 1099 11 NULL

prev curr

1009 1001 1099

head 9 1099 7 1099 11 NULL

prev curr

1009 1099
head 9 1099 11 NULL

25
DELETE at Location:
void deleteNode(int position, Node* & head) {
if(position == 1) { //deleting first or start node
deleteHead(position, head);
}
else {
//deleting any middle node or last node
Node* curr = head;
Node* prev = NULL;
int cnt = 1;
while(cnt < position) {
prev = curr;
curr = curr -> next;
cnt++;
}
prev -> next = curr -> next;
curr -> next = NULL;
delete curr;
}
}
26
Code:
Code:
Code:
Code:
Code:
Code:
Practice Task
Write a C++ program that maintains library shop stock using link list. Provide
below facility in program:
1) Insert book details (at specific location)
2) Delete Book Detail (from specific location)
3) Facility to search book
4) Display all books details also take below information for particular book:
• Book Author
• Book Title
• Book Price
Stack Implementation - Linked-List
void push(int x) {
Node* newNode = new Node(); // Create a new node
newNode->data = x; // Set the data of new node to input value
newNode->next = top; // Set the next ptr of new node to current top
top = newNode; // Update the top pointer to the new node
}
void pop() {
if (top == NULL) {
cout << "Stack is empty!" << endl;
return;
}
Node* temp = top; // Temporary pointer to the current top
top = top->next; // Update the top pointer
delete temp; // Delete the old top node
}
Stack Implementation - Linked-List
void display() {
if (top == NULL) {
cout << "Stack is empty" << endl;
return;
}
Node* temp = top; // Temporary pointer to traverse the stack
cout << "Stack elements are: ";
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
Code:
Code:
Code:
Queue Implementation - Linked-List
void enqueue(int element){
Node* node = new Node();
if (node == NULL) {
cout << "System out of memory" << endl;
return; }
node->element = element;
node->next = NULL;

// If the Queue is empty, set Front to point the new node. Otherwise connect new node at Rear.
if (rear == NULL) {
front = node;
} else {
rear->next = node;
}
// Change the rear to point the new node
rear = node;
}
 Queue Implementation - Linked-List
int dequeue() {
if (front == NULL) {
return -1;
}
// Retrieve the element at Front
int element = front->element;
// Remember the front node in a temporary pointer
Node* tmp = front;
// If next node is available, change Front to point next node. Otherwise set Front and Rear to point the NULL
if (front->next == NULL) {
front = rear = NULL;
} else {
front = front->next;
}
// Delete the node stored in temporary pointer
delete tmp;
return element;
}
 Types of Linked List
Depending upon how links are maintained, there can be variationsof linked list:
Singly Linked List
We have discussed it already
🞂 Doubly Linked List
Circular Linked List

41
Singly Linked List
Every node contains only one next link which points to next node in list
1009 1001 1099
head 9 1001 71099 11 NULL

Last nodes points to NULL.

42
Doubly Linked List
Every node contains two links, next which points to next node and previous
which points to previous node in list
1009 1099 1001
head 1009 11 1099 1001 15 NULL
NULL 7 1001

Note that prev and next links hold address of nodes. So, prev link of node located at
1001 points to 1009 and next link points to 1099.
• Previous link of first node is NULL
• Next link of last node is NULL
• Doubly linked list can be traversed from start to end and from end to start.
If we have tail node
43
Doubly Linked List
Insertion:
In a double-linked list, the insertion operation can be performed in three ways:
• Inserting At Beginning of the list
• Inserting At End of the list
• Inserting At Specific location in the list
Deletion :
In a double-linked list, the deletion operation can be performed in three ways:
• Deleting from Beginning of the list
• Deleting from End of the list
• Deleting a Specific Node
Insertion at Start
• If List is Empty? • If List is non-Empty?
head NULL

Create new node, and update head

1009
head NULL 7 NULL

3 2

4
temp

45
Insertion at Start
void insertAtHead(Node* &head, int d) {

//empty list
if(head == NULL) {
Node* temp = new Node(d);
head = temp;
}
else{
Node* temp = new Node(d);
temp -> next = head;
head -> prev = temp;
head = temp;
}

46
Insertion at End
If List is Empty? If List is non-Empty?
head NULL 1009 1001
head NULL 7 1001 1009 11 NULL

Create new node, and update head Create new node

1009 1011
head NULL 7 NULL NULL 15 NULL
009
Change links

1009 1001
head 1001 1009 11 1011
NULL
7

1011
15 NULL
1001 009
47
Insertion at End
void insertAtTail(Node* &tail, int d) {
if(tail == NULL) {
Node* temp = new Node(d);
tail = temp;
}
else{
Node* temp = new Node(d);
tail -> next = temp;
temp -> prev = tail;
tail = temp;
}

48
Insertion at Middle
Let say we want to insert 13 in following list, at location 2.
1099 1001
1009
head NULL 1001 1009 11 1099 11 NULL
7

New Node 1019

NULL 13 NULL
Linking
1009 1001 1099
head 1019 11 NULL
NULL 2 1009 11 1099
7
temp 4 3
5 1019
1009 13 1001

49
Insert at Middle
void insertAtPosition(Node* & tail, Node* &head, int position, int d) {
if(position == 1) { //insert at Start
insertAtHead(tail,head, d);
return; } temp
Node* temp = head;
int cnt = 1;
while(cnt < position-1) {
temp = temp->next;
cnt++;
}
if(temp -> next == NULL) { //inserting at Last Position
insertAtTail(tail,head,d);
return ; }
Node* nodeToInsert = new Node(d); //creating a node for d
nodeToInsert ->next = temp -> next;
temp -> next -> prev = nodeToInsert;
temp -> next = nodeToInsert;
nodeToInsert -> prev = temp;
}
50
Deletion at Start
If this is the last node? Else?
1009 1009 1001
head NULL 7 NULL head 1001 1009 11 NULL
NULL 7

Update head
Update head
Delete node
Update prev link of next node
Delete node
head NULL 1001
head NULL 11 NULL

51
DELETE at Start
void deleteNode(int position, Node* & head) {
//deleting first or start node
if(position == 1) {
Node* temp = head;
temp -> next -> prev = NULL;
head = temp ->next;
temp -> next = NULL;
delete temp;
}
}

52
Deletion at End
If this is the last node? Else?
1009 1009 1001
head NULL 7 NULL head NULL 7 1001
1009 11 NULL
prev curr
Update head
Update next link of prev node
Delete node
Delete node
1009
head NULL
head NULL 7 NULL

53
Deletion at Location
Let say we need to delete 2nd node.

1009 1001 1099

head NULL 1001 1099 1001 11 NULL
7 1009 11
100

curr

1009 1099
head 1099 1009 11 NULL
NULL 7

54
curr
DELETE at location/last
//deleting any middle node or last node
Node* curr = head;
Node* prev = NULL;
int cnt = 1; curr
while(cnt < position) {
prev = curr;
curr = curr -> next;
cnt++;
}
curr -> prev = NULL; curr
prev -> next = curr -> next;
curr -> next = NULL;
delete curr;
curr

56
Code:
Code:
Code:
Code:
Code:
Code:
Circular Linked List-Single
Every node contains only one next link which points to next node in list.
1009 1001 1099
head 9 1001 7 1099 11 1009

Last nodes points to First node of list

What change needs to be done in singly linked list algorithms?
How to know that node is last node in list?

63
Modified Insert_End –Single Linked List
🞂Algorithm: INSERT_END(Head, Tail, V)
🞂 Input: head node and data to be inserted
🞂 Output: list with new node inserted
🞂 Steps:
Start:
1. newestNode = new Node(V) //create new node
2. If Head==NULL // list is empty
3. Head=newestNode
4. Tail=newestNode
5. Else
//list is not empty. Search last node
6. Tail.next=newestNode
// update the next pointer of ptr(last node)
7. Tail=newestNode;
8. End If
End

64
Circular Linked List-Double
Doubly linked list, with last node pointing to first node and first node pointing
to last node.

Previous link of first node is Last node

Next link of last node is first node

65
Tail Node
🞂Whenever we do insertion/deletion to end of list, we need to search for last
node, it involves loop
🞂 Can we avoid this loop?
🞂 By maintaining a reference to last node just like we do for first node.
🞂 It will save time
🞂 How?
1009 1001
head data 1001 data NULL tail

66
Tail Node
🞂Whenever we do insertion/deletion to end of list, we need to search for last
node, it involves loop
🞂 Can we avoid this loop?
🞂 By maintaining a reference to last node just like we do for first node.
🞂 Will save time?
🞂 Let Say Tail points to last node
🞂 Insertion at End needs last node 1001
🞂 Tail.next=newestNode;
1009
head NULL tail
data
🞂 Tail=NewestNode data 1001
🞂 If double linked list, then set prev link of new node
🞂 Deletion at End needs 2nd last node
🞂 In single linked list: No benefit, we always need to search for 2nd last node
🞂 In Double: we can go to previous node of double linked list.

67
Array vs. Linked List
Memory allocation
Static vs. dynamic
Contiguous vs linked
Space utilization
Array is fixed whereas linked list can grow/shrink
Single node vs single cell

58
Applications of Linked List
Where size is not fixed, and no random access.
Few example:
Other data structures
Stack, queue, trees, graphs
Browser’s back button
To go to previous URLs
Card Game
Deck of cards, no random access

59