Operations in linked list
OPERATION ON LINKED LIST
The primitive operations performed on the linked list are as follows
Creation operation is used to create a linked list. Once a linked list is created with one node, insertion operation can be used to add more elements in a node.
Insertion operation is used to insert a new node at any specified location in the linked list. A new node may be inserted.
(a) At the beginning of the linked list
(b) At the end of the linked list
(c) At any specified position in between in a linked list
Deletion operation is used to delete an item (or node) from the linked list. A node may be deleted from the
(a) Beginning of a linked list
(b) End of a linked list
(c) Specified location of the linked list
Traversing is the process of going through all the nodes from one end to another end of a linked list. In a singly linked list we can visit from left to right, forward traversing, nodes only. But in a doubly linked list forward and backward traversing is possible.
Concatenation is the process of appending the second list to the end of the first list. Consider a list A having n nodes and B with m nodes. Then the operation concatenation will place the 1st node of B in the (n+1)th node in A. After concatenation A will contain (n+m) nodes.
Singly Linked List
All the nodes in a singly linked list are arranged sequentially by linking with a pointer. A singly linked list can grow or shrink, because it is a dynamic data structure.
Create node
struct node
{
int no;
struct node *next;
};
Algorithm for Inserting a node at the beginning
Algorithm: Insert a Node at the beginning
1. Input DATA to be inserted
2. Create a NewNode
3. NewNode → DATA = DATA
4. If (START equal to NULL)
(a) NewNode → Link = NULL
5. Else
(a) NewNode → Link = START
6. START = NewNode
7. Exit
Algorithm for inserting a node at the end
Algorithm: Insert a Node at the end
1. Input DATA to be inserted
2. Create a NewNode
3. NewNode → DATA = DATA
4. NewNode → Next = NULL
5. If (START equal to NULL)
(a) START = NewNode
6. Else
(a) TEMP = START
(b) While (TEMP → Next not equal to NULL)
(i) TEMP = TEMP → Next
7. TEMP → Next = NewNode
8. Exit
Algorithm for Inserting the node at specific position
//Algorithm: Insert a Node at any specified position
1. Input DATA and POS to be inserted
2. initialize TEMP = START; and j = 0
3. Repeat the step 3 while( k is less than POS)
(a) TEMP = TEMP -> Next
(b) If (TEMP is equal to NULL)
(i) Display “Node in the list less than the position”
(ii) Exit (c) k = k + 1
4. Create a New Node
5. NewNode → DATA = DATA
6. NewNode → Next = TEMP → Next
7. TEMP → Next = NewNode
8. Exit
Algorithm for deleting a node from the beginning
Algorithm: To delete node from beginning
Step 1: IF HEAD = NULL
Write UNDERFLOW
Go to Step 5
[END OF IF]
Step 2: SET PTR = HEAD
Step 3: SET HEAD = HEAD -> NEXT
Step 4: FREE PTR
Step 5: EXIT
Algorithm for deleting a node from the end
Algorithm: To delete node from last
Step 1: IF HEAD = NULL
Write UNDERFLOW
Go to Step 8
[END OF IF]Step
2: SET PTR = HEAD
Step 3: Repeat Steps 4 and 5 while PTR -> NEXT!= NULL
Step 4: SET PREPTR = PTR
Step 5: SET PTR = PTR -> NEXT
[END OF LOOP]
Step 6: SET PREPTR -> NEXT = NULL
Step 7: FREE PTR
Step 8: EXIT
Algorithm for deleting the node from specific position
Algorithm: To delete node at given position
[Exercise]
Algorithm for searching a node
ALGORITHM : FOR SEARCHING A NODE
1. Input the DATA to be searched
2. Initialize TEMP = START; POS =1;
3. Repeat the step 4, 5 and 6 until (TEMP is equal to NULL)
4. If (TEMP → DATA is equal to DATA)
(a) Display “The data is found at POS”
(b) Exit
5. TEMP = TEMP → Next
6. POS = POS+1
7. If (TEMP is equal to NULL)
(a) Display “The data is not found in the list”
8. Exit
ALGORITHM FOR DISPLAY ALL NODES
Suppose START is the address of the first node in the linked list. Following algorithm will visit all nodes from the START node to the end.
ALGORITHM : FOR DISPLAY ALL NODES
1. If (START is equal to NULL)
(a) Display “The list is Empty”
(b) Exit
2. Initialize TEMP = START
3. Repeat the step 4 and 5 until (TEMP == NULL )
4. Display “TEMP → DATA”
5. TEMP = TEMP → Next
6. Exit
Write a C program to implement singly Linked List
#include<stdio.h>
#include<stdlib.h>
struct node{
int data;
struct node *next;
};
struct node *head=NULL;
void insert_at_begining(){
int data;
struct node *ptr;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr==NULL){
printf("\noverflow error:\n");
exit(0);
}
else{
printf("\nEnter element to be inserted:");
scanf("%d",&data);
ptr->data=data;
ptr->next=head;
head=ptr;
}
}
void insert_at_end(){
int data;
struct node *temp,*ptr;
temp = (struct node*)malloc(sizeof(struct node));
if(temp==NULL){
printf("\noverflow error:\n");
}
else{
printf("\nEnter element to be inserted:");
scanf("%d",&data);
temp->data=data;
if(head==NULL){
temp->next=head;
head=temp;
}
else{
ptr=head;
while(ptr->next!=NULL){
ptr=ptr->next;
}
ptr->next=temp;
temp->next=NULL;
}
}
}
void display(){
struct node *temp;
temp = head;
if(temp==NULL){
printf("\n Empty List error\n");
}
else{
printf("\nLinked List contains following elements:\n");
while(temp!=NULL){
printf("%d\t",temp->data);
temp=temp->next;
}
}
}
void insert_at_position(){
struct node *temp,*ptr;
int pos,data,count=1;
temp = (struct node *)malloc(sizeof(struct node));
if(temp==NULL){
printf("\noverflow error\n");
exit(0);
}
else
{
printf("\n Enter position: ");
scanf("%d",&pos);
printf("\nEnter element to be inserted:");
scanf("%d",&data);
temp->data=data;
if(pos==1){
temp->next=head;
head=temp;
}
else
{
ptr=head;
while(count!=pos-1){
ptr = ptr->next;
count++;
}
temp->next=ptr->next;
ptr->next=temp;
}
}
}
void delete_from_begining(){
struct node *ptr;
if(head==NULL){
printf("\nunderflow error\n");
exit(0);
}
else
{
ptr = head;
head = head->next;
free(ptr);
}
}
void delete_from_end(){
struct node *ptr,*temp;
if(head==NULL){
printf("\nunderflow error\n");
exit(0);
}
else{
ptr=head;
while(ptr->next->next!=NULL){
ptr = ptr->next;
}
temp = ptr->next;
ptr->next=NULL;
free(temp);
}
}
void delete_from_position(){
int count=1,pos;
struct node *ptr,*temp;
if(head==NULL){
printf("\nunderflow error\n");
exit(0);
}
else{
printf("\nEnter position to be deleted from: ");
scanf("%d",&pos);
if(pos==1){
delete_from_begining();
}
else
{
ptr = head;
while(count!=pos-1){
ptr = ptr->next;
}
temp = ptr->next;
ptr->next=ptr->next->next;
free(temp);
}
}
}
int main(){
display();
insert_at_begining();
insert_at_begining();
insert_at_begining();
insert_at_begining();
insert_at_begining();
display();
insert_at_position();
insert_at_end();
display();
delete_from_begining();
display();
delete_from_end();
display();
delete_from_position();
display();
return 0;
}
Write a C++ program to implement singly Linked List:
#include<iostream>
using namespace std;
class Node{
public:
int data;
Node *link;
};
class LList{
private:
Node *head,*tail;
public:
LList(){
head=NULL;
}
void create();
Node *getNode();
void append(Node*);
void insertAtPos(Node*,int);
void deletePos(int pos);
void display();
};
// This function is used to create node when required.
Node *LList::getNode(){
int data;
Node *newnode;
cout<<"Enter data to be inserted: ";
cin>>data;
newnode = new Node;
newnode->data= data;
newnode->link = NULL;
return (newnode);
}
//This function is used to create Linked list by appending the node in the linked list.
void LList::create(){
Node *temp;
char ch;
while(1){
cout<<"Do you want to add more nodes(y/n)";
cin>>ch;
if(ch=='n') break;
else{
temp = getNode();
append(temp);
}
}
}
void LList::append(Node *temp){
// For the empty linked list, the first inserted node will be assigned as HEAD node
if(head==NULL){
head=temp;
tail=temp;
}
else{
tail->link = temp;
tail = temp;
}
}
//Traverse the entire list, and display the data part of node.
void LList::display(){
Node *temp;
temp=head;
if(temp==NULL){
cout<<"Empty list"<<endl;
}
else{
cout<<"Following are the elements of the list: "<<endl;
while(temp!=NULL)
{
cout<<temp->data<<" ";
temp = temp->link;
}
cout<<endl;
}
}
//The method given below is used to insert the node at position specified by the user.
void LList::insertAtPos(Node *temp,int pos){
int i,flag=1;
// If node is to be inserted at first position, then newly added node should be assigne as HEAD node
if(pos==1){
temp->link = head;
head = temp;
}
else{
// this section handle the insertion of node at the position specified by the user.
// Move to the pos-1 of specified pos, then insert the new node between node at pos-1 and its successor.
Node *q=head;
for(i=1;i<pos-1;i++){
if(q->link==NULL){
flag=0;
}
q = q->link;
}
if(flag==1){
temp->link=q->link;
q->link=temp;
}
else{
cout<<"Position not found"<<endl;
}
}
}
void LList::deletePos(int pos){
Node *temp,*prev,*cur;
temp=head;
int i,flag=1;
if(pos==1){
head = temp->link;
delete temp;
}
else{
for(i=0;i<pos;i++){
if(temp->link==NULL){
flag=0;
}
temp=temp->link;
}
if(flag==1){
prev=temp;
cur = temp->link;
prev->link = cur->link;
delete cur;
}
else{
cout<<"position not found"<<endl;
}
}
}
int main()
{
int pos,delpos;
LList L1;
L1.create();
L1.display();
cout<<"Enter the position where you want to insert the node: ";
cin>>pos;
Node *temp= L1.getNode();
L1.insertAtPos(temp,pos);
L1.display();
cout<<"Enter the position from where you want to delete the node: ";
cin>>pos;
L1.deletePos(delpos);
L1.display();
}