Linked List implementation in C++
Algorithm for adding an element (data) to the front of the list list.
1. Declare and initialize necessary variables
2. Create an empty node and assign it to node pointer p.
3. Take input data and assign it to info field of new node
i.e. p->info = data;
4. Set next field. i.e. p->next = list;
5. Set list pointer to p i.e. list = p;
6. For next insertion operation, goto step 2
Insertion new node at the end.
1. Declare neccessary variables.
2. Create an empty node and assign it to node pointer p.
3. Insert the data item to info field of newly created node,
i.e. p->info = data;
4. Assign NULL to the next field of newly created node
i.e. p->next = NULL;
5. If list == NULL;
then list = p;
Else
Find the last node of the current list say l.
then l->next = p;
6. For next insertion, goto step 2.
Deletion of the first node
1. Declare the necessary variables
2. If list = NULL
print "Empty list"
Else
p = list
list = p -> next
3. Remove the node p i.e. delete(p)
4. For next deletion, goto step 2
Deletion of the last node
1. Declare necessary variable
2. If list = NULL
print "Empty List"
Else
set p = list
if p->next = NULL
list = NULL
delete(p)
Else
while(p->next!=NULL)
temp = p
p = p->next
temp->next = NULL
delete(p)
3. For next deletion goto step 2
The source code in C++ for whole process include inserting and deleting elements before and after the given node is given below:
/********************************************
Program: Linked List using C++
by Bibek Subedi
June, 29 2011
********************************************/
#include
#include
using namespace std;
struct node{
int info;
struct node *next;
};
class Link{
node *list;
public:
Link();
void insert_at_begining(int);
void insert_at_end(int);
void insert_before_node();
void insert_after_node();
void delete_at_begining();
void delete_at_end();
void delete_before_node();
void delete_before_after_node(int);
node *find_before_node(node*);
void display();
};
Link::Link(){
list = NULL;
}
node *Link::find_before_node(node *p){
int count = 0;
int count1 = 0;
node *temp = new node;
temp = list;
while(temp!=p){
count++;
temp=temp->next;
}
temp = list;
while(count1
count1++;
temp = temp->next;
}
return temp;
}
void Link::insert_at_begining(int data){
node *p = new node;
p->info = data;
p->next = list;
list = p;
}
void Link::insert_at_end(int data){
node *p = new node;
node *r = new node;
node *q = new node;
r = list;
p->info = data;
p->next = NULL;
if(list == NULL){
list = p;
}else{
while(r->next!=NULL){
r = r->next;
}
r->next = p;
}
}
void Link::insert_before_node(){
node *p = new node;
node *l = new node;
node *r = new node;
int data1, data2;
bool isFound = false;
coutEnter the node: ";
cin>>data1;
p = list;
while(p != NULL){
if(p->info == data1){
isFound = true;
break;
}
l = p;
p = p->next;
}
if(isFound){
coutEnter the data to insert:";
cin >> data2;
r->info = data2;
if(p==list){
insert_at_begining(data2);
}else{
l->next = r;
r->next = p;
}
}else{
cout\nMember not found\n";
}
}
void Link::insert_after_node(){
node *p = new node;
node *r = new node;
node *l = new node;
int data1, data2;
bool isFound = false;
coutEnter the node: ";
cin>>data1;
p = list;
while(p!= NULL){
if(p->info == data1){
isFound = true;
break;
}
p = p->next;
}
if(isFound){
coutEnter the data to insert: ";
cin>>data2;
r->info = data2;
if(p->next == NULL){
insert_at_end(data2);
}else{
l = p->next;
p->next = r;
r->next = l;
}
}else{
cout\nMember not found\n";
}
}
void Link::delete_at_begining(){
node *p = new node;
if(list == NULL){
cout\nList is Empty\n";
}else{
p = list;
list = list->next;
delete p;
}
}
void Link::delete_at_end(){
node *p = new node;
node *l = new node;
if(list == NULL){
cout\nList is Empty\n";
}else{
p = list;
if(p->next == NULL){
list = NULL;
delete p;
}else{
while(p->next!= NULL){
l = p;
p = p->next;
}
l->next = NULL;
delete p;
}
}
}
void Link::delete_before_node(){
node *p = new node;
node *l = new node;
int data1;
bool isFound = false;
p = list;
coutEnter the node: ";
cin>>data1;
if(p == NULL){
cout\nList is Empty"
exit(0);
}
while(p!=NULL){
if(p->info == data1){
isFound = true;
break;
}
l = p;
p = p->next;
}
if(isFound){
if(p == list){
cout\nIt is the first element\n";
}else if(p == list->next){
list = p;
delete l;
}else{
find_before_node(l)->next = p;
delete l;
}
}
}
void Link::display(){
node *p = new node;
p = list;
if(list==NULL){
cout\nNothing to Display\n";
}else{
cout\nThe contents of list\n";
while(p!=NULL){
coutinfo
p = p->next;
}