(ELE 144)

Data Structures and Algorithms

Lecture 5
Linked list
 Linked lists operations in C++
Agenda • Deletion item
• Reversing a list

Types of linked list

Stack Implementation using

Linked List

Queue Implementation using

Linked List
Single Linked List: Deletion

Deletion steps
• Manage links to
• Delete at front
• Delete at end
• Delete at any position
Single Linked List: Deletion Cont.

• Do not forget to delete() memory location dynamically allocated for a node after
deletion of that node.

• It is the programmer’s responsibility to free that memory block.

• Failure to do so may create a dangling pointer – a memory, that is not used either
by the programmer or by the system.
 Single Linked List: Deletion at Front

Steps to delete first node of Singly Linked List

Step 1: Copy the address of first node i.e. Step 3: Disconnect the connection of
head node to some temp variable say delptr. first node to second node.

Step 2: Move the head to the second node

of the linked list (head = head->next). Step 4: Free the memory occupied by the first node.
 Deletion at Front Function
/* Delete the first node of the linked list */

void delete_first()
{
node* delptr = head;
head = delptr->next;
delete delptr;
}
 Single Linked List: Deletion at any Position or
at End

Step 1: Traverse to the nth node of the singly Step 2: Reconnect n-1th node with the n+1th node i.e.
linked list and also keep reference of n-1th node prev->next = delptr->next
in some temp variable say prev. (Where prev is n-1th node and delptr node
is the nth node and delptr->next is the n+1th node).

Step 3: Free the memory occupied by the nth node i.e. delptr node.
Deletion at any Position or at End Function

void del(int item)

{
node* prev=NULL;
node* delptr=head;
while (delptr->data!=item)
{
prev=delptr;
delptr=delptr->next;
}
prev->next=delptr->next;
delete delptr;
}
Deletion from any position
void delete_anynode(int item)
{
node*delptr=head;
if (IsEmpty())
cout<<“list is empty, no items to delete \n”;
else if (head->data==item){
head=head->next;
Delete delptr;
}
else
{
node* prev=NULL;
while (delptr->data!=item)
{
prev=delptr;
delptr=delptr->next;
}
prev->next=delptr->next;
Delete delptr;
}
}
 Single Linked List: Reversing
Reversing a List: Iterative Method Function
 Steps to reverse a Singly Linked List using Iterative method

curr = head
Prev =NULL

temp
continue to

void reverse()
{
node* prev= NULL;
node* curr= head;
node* temp= NULL;
while(curr != NULL)
{
temp = curr->next;
curr->next = prev;
prev = curr;
curr = temp;
}
head= prev;
}
Types of Lists: Double Linked List
• Doubly linked list is a collection of nodes linked together in a sequential way.
• Doubly linked list is almost similar to singly linked list except it contains two
address or reference fields, where one of the address field contains reference of
the next node and other contains reference of the previous node.

• Doubly linked list is sometimes also referred as bi-directional linked list since it
allows traversal of nodes in both direction (forward or backward).
• Since doubly linked list allows the traversal of nodes in both direction, we can
keep track of both first(head) and last(tail) nodes.

head tail

null A B C null
Defining a Node of a Double Linked List
Each node of doubly linked list (DLL) consists of three fields:
• Item (or) Data
• Pointer of the next node in DLL
• Pointer of the previous node in DLL node
Data
prev next

How to define a node of a doubly linked list (DLL)?

struct Node
{
string Data;
Node * next;
Node * prev;
};
 Doubly-linked Lists: What Changes?
Every time we insert a new node or delete an existing node, we must
update three sets of pointers:

1. The new node’s next and previous pointers.

2. The previous node’s next pointer.
3. The following node’s previous pointer.

And of course, we still have special cases if

we insert or delete nodes at the top or the
bottom of the list.
Double versus Single Linked List
• Advantages over singly linked list
A DLL can be traversed in both forward and backward direction.

• Disadvantages over singly linked list

1) Every node of DLL Require extra space for an previous pointer.
2) All operations require an extra pointer previous to be maintained.

• Disadvantages of singly linked list

One of the downsides with our simple linked list is that we can only travel in one
direction… forward!
Types of Lists: Circular Linked List

Circular linked list

•The pointer from the last element in the list points back to the
first element

Doubly circular linked list: Basic structure of singly circular linked list:
 Circular Linked List
• A circular linked list is basically a linear linked list that may be single- or
double-linked.
• The only difference is that there is no any NULL value terminating the list.
• In fact in the list every node points to the next node and last node points to
the first node, thus forming a circle. Since it forms a circle with no end to
stop it is called as circular linked list.
• In circular linked list there can be no starting or ending node, whole node
can be traversed from any node.
• In order to traverse the circular linked list, only once we need to traverse
entire list until the starting node is not traversed again.
• A circular linked list can be implemented using both singly linked list and
doubly linked list.
Circular linked list: Cont.
Advantages of a Circular linked list
• Entire list can be traversed from any node.
• 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 supports direct
accessing of elements.
 Stack Implementation using Linked List

PUSH
OPERATION POP
OPERATION

top
top
 Basic Idea
• In the array implementation, we would:
• Declare an array of fixed size (which determines the maximum
size of the stack).

• Keep a variable which always points to the “top” of the stack.

• Contains the array index of the “top” element.

• In the linked list implementation, we would:

• Maintain the stack as a linked list.
• A pointer variable top points to the start of the list.
• The first element of the linked list is considered as the stack top.
class node
{public:
int Data; node *next; Pushing an element popping an element
node() into stack from stack
{data=0;
Next=null;}
};

int pop()
class stack void push(int item)
{
{private: {
Int pop_val;
node *top; node *new_node=new
if(isEmpty()){
Public: node();
Cout<<“stack is empty”;
stack() new_node->data=item;
Return 0;}
{ if(isEmpty())
Else {
top=NULL; new_node->next=NULL;
node* delptr=top;
} else
pop_val=delptr->data;
bool isEmpty() new_node->next=top;
top=top->next;
{ if (top==NULL) top=new_node;
Delete delptr;
return true; }
return pop_val;
else }}
return false;
}
Queue: Linked List Structure
• Basic idea:
• Create a linked list to which items would be added to one end
and deleted from the other end.
• Two pointers will be maintained:
• One pointing to the beginning of the list (point from where
elements will be deleted).
• Another pointing to the end of the list (point where new
elements will be inserted).
Rear

Front DELETION INSERTION

 ENQUEUE
front rear

DEQUEUE
front rear
 Queue Operations using Linked List
void enqueue()
{ void dequeue()
int val; {
cout<<"Insert the element in queue : if ((front==NULL) && (rear==NULL)) {
"<<endl; cout<<“Queue is Empty”<<endl;}
cin>>val; else if (rear==front) {
cout<<front->data;
node* newnode= new node(); delete front;
newnode->data=val; front=rear=NULL;
newnode->next=NULL; }
else
if ((front == NULL) && (rear == NULL)) {
{ node *delptr=front;
front=rear=newnode;} front=front->next;
else{ cout<<delptr->data;
delete delptr;
rear->next=newnode; }
rear=newnode; }
}}