Linked_list_in_c++
#include <iostream>
using namespace std;
/*
Important Notes about the program
1. Here we declare head in global so there is no need to pass it every
function.
2. We are passing position numbers in insertAtPos() function they start
from 1 and go on.
3. Above point(2) is very important when dealing with list array we are
dealing with, which starts at 0 (I mean index)
*/
//Node structure
struct Node{
int data;
Node* link;
};
// declaring head in global
// function declarations or prototype
struct Node* insert(struct Node* head,int data);
struct Node* insertAtBeg(struct Node* head,int data);
struct Node* insertAtPos(struct Node* head,int data, int pos);
struct Node* deleteAtPos(struct Node* head,int pos);
struct Node* deleteAtEnd(struct Node* head);
struct Node* deleteAtBeg(struct Node* head);
struct Node* reverse(struct Node* head);
void print(struct Node* head);
//Main function
int main(){
Node* head;
head = NULL;
head = insert(head,10);
head = insertAtBeg(head,1);
head = insert(head,20);
head = insertAtPos(head,5,4);
head = insertAtPos(head,20,1);// insertAtPos(data, position_number)
head = insertAtPos(head,56,3);
// Now the list is :
// 20 1 56 10 20 5
print(head);
head = deleteAtEnd(head);
print(head);
// 20 1 56 10 20
head = deleteAtBeg(head);
print(head);
// 1 56 10 20
head = deleteAtPos(head,2);
print(head);
// 1 10 20
// cout << "Printing Head before reverse: " << head << "\n";
head = reverse(head);
//20 10 1
// cout << "\nPrinting Head after reverse: " << head;
print(head);
// 1 10 20
// head = insert(head,12);
// //1 10 20 12
// head = insert(head,15);
// //1 10 20 12 15
// reverse(head);
// //15 12 20 10 1
// print(head);
// //1 10 20 12 15
}
struct Node* insert(struct Node* head, int data){
Node* temp1 = new Node();
if(temp1 != NULL){
temp1->data = data;
temp1->link = NULL;
if(head == NULL)
{
head = temp1;
return head;
}
Node* temp;
temp = head;
while(temp->link != NULL){
temp = temp->link;
}// this belongs to while
// If temp->link is null , its the end of linked list and we append our new
// node there
temp->link = temp1;
//now temp->link points to the address of temp1
}// if block ends here
else{
cout << "MEMORY is FULL";
}
return head;
}
struct Node* insertAtBeg(struct Node* head,int data){
Node* temp1 = new Node();
if(temp1 != NULL){
temp1->data = data;
temp1->link = nullptr;
if(head == NULL){
head = temp1;
return head;
}
temp1->link = head;
head = temp1;
temp1 = NULL;
}// if block ends
else{
cout << "MEMORY is FULL";
}
return head;
}
int count_iter(struct Node* head){
int count = 0;
Node* temp;
temp = head;
while(temp != NULL){
++count;
temp = temp->link;
}
return count;
}
int count_recur(struct Node* head){
if(head == NULL){
return 0;
}
return 1 + count_recur(head->link);
}
struct Node* insertAtPos(struct Node* head,int data,int pos){
Node* temp1 = new Node();
if(temp1 != NULL){
temp1->data = data;
temp1->link = NULL;
if(pos == 1){
temp1->link = head;
head = temp1;
return head;
}
// pos-1 because position starts at 1
// if(pos-1 > count_recur(head)){
// cout << "sorry type the correct position number\n\n";
// return;
// }
Node* temp;
temp = head;
for(int i=0;i <pos-2;++i){
temp = temp->link;
}
// The above for loops ends with temp containing the Node address of position - 1
// before node we want to insert at
temp1->link = temp->link;// new node contains address of the next node
temp->link = temp1;//linking previous node with new node
}// if block ends here
else{
cout << "MEMORY is FULL";
}
return head;
}
void print(struct Node* head){
Node* temp;
temp = head;
cout << "The linked list is : \t";
while(temp != NULL){
cout << temp->data << "\t";
temp = temp->link;
}
}
struct Node* deleteAtPos(struct Node* head,int pos){
// if(pos-1 > count_recur(head)){
// cout << "There is no element at given position( " << pos << " )\n";
// return;
// }
Node* temp1;
temp1 = head;
if(pos == 1){
head = temp1->link;
delete temp1;
temp1 = NULL;
}
for(int i=0; i < pos-2; ++i){
temp1 = temp1->link;
}
Node* temp2 = temp1->link;// temp2 contains the node address that we want to
// delete
temp1->link = temp2->link;
delete temp2;
temp2 = NULL;
return head;
}
struct Node* deleteAtBeg(struct Node* head){
Node* temp1;
temp1 = head;
head = temp1->link;
delete temp1;
temp1 = NULL;
return head;
}
struct Node* deleteAtEnd(struct Node* head){
Node* temp1;
int c = 0;// counting the nodes
temp1= head;
Node* temp2;
while(temp1 != NULL){
++c;
if( c == count_iter(head)-1 ){
Node* temp2 = temp1->link;
temp1->link = NULL;
delete temp2;
temp2 = NULL;
break;
}
temp1 = temp1->link;
}
return head;
}
// By using iterative way we will modify original list
struct Node* reverse(struct Node* head){
// cout << "Printing Head in reverse: " << head;
Node *current, *next, *prev, *temp;
current = head;
prev = NULL;
while(current != NULL){
next = current->link;
current->link = prev;
prev = current;
current = next;
}
head = prev;
return head;
// The problem with this reverse function is its modifying the original head
}
// to reverse without changing original list we need to reverse it using recursion
// remember head is local to each function that contains a copy of the address of head
// we are traversing through null here we are not changing(modifying any nodes) anything here notice that
void reverse_rec(struct Node* head){
if(head == NULL){
return;
}
reverse_rec(head->next);
cout << head->data; // we can rename the variable if we confuse
}
void print_rec(struct Node* head){
if(head == NULL){
return;
}
cout << head->data;
reverse_rec(head->next);
}INFO