struct node *reverse(struct node *start)
{
struct node *previous, *ptr, *next;
previous = NULL;
ptr = start;
while(ptr!=NULL)
{
next=ptr->link;
ptr->link=previous;
previous=ptr;
ptr=next;
}
start=previous;
return start;
}
void search(struct node *start, int num2)
{
struct node *p=start;
int pos=1;
while(p!=NULL)
{
if(p->info==num2)
{
printf("%d found at pos %d",num2);
return;
}
p=p->link;
}
printf("num2 %d not found in the listn", num2);
}
void count(struct node *start)
{
int count = 0;
struct node *p=start;
while(p!=NULL)
{
p=p->link;
count++;
}
printf("Number of nodes %d ", count);
}
#include
#include
struct node{
int info;
struct node *link;
};
void display(struct node *start);
struct node *addatbeg(struct node *start, int num);
void addatend(struct node *start, int num);
struct node *del(struct node *start, int num);
void search(struct node *start, int num2);
main()
{
struct node *start=NULL;
int choice, num, num2;
while(1)
{
printf("n1. Displayn");
printf("2. Add node to empty list / Add at beginningn");
printf("3. Add node at the endn");
printf("4. Delete from listn");
printf("5. Exitnn");
scanf("%d",&choice);
switch(choice)
{
case 1:
display(start);
break;
case 2:
printf("Enter the number to be insertedn");
scanf("%d",&num);
start = addatbeg(start, num);
break;
case 3:
printf("Enter the number to be insertedn");
scanf("%d",&num);
addatend(start, num);
break;
case 4:
printf("Enter the number to be deletedn");
scanf("%d",&num);
start=del(start, num);
break;
case 5:
exit(1);
default:
printf("Invalid Input");
}
}
}
void display(struct node *start)
{
struct node *p;
if(start==NULL)
{
printf("nList is emptyn");
return;
}
p=start;
printf("List is : n");
while(p != NULL)
{
printf("%d ", p->info);
p=p->link;
}
}
struct node *addatbeg(struct node *start, int num)
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
temp->info=num;
temp->link = start;
start = temp;
return start;
}
void addatend(struct node *start, int num)
{
struct node *temp, *p;
temp=(struct node *)malloc(sizeof(struct node));
temp->info=num;
p=start;
while(p->link!=NULL)
{
p = p->link;
}
p->link = temp;
temp->link = NULL;
}
struct node *del(struct node *start,int num)
{
struct node *tmp,*p;
if(start==NULL)
{
printf("List is emptyn");
return start;
}
if(start->info==num) /*deletion from first or only node*/
{
tmp=start;
start=start->link;
free(tmp);
return start;
}
p=start;
while(p->link!=NULL)
{
if(p->link->info==num)
{
tmp = p->link;
p->link = tmp->link;
free(tmp);
return start;
}
p=p->link;
}
printf("%d not presentn",num);
return start;
}
The info part of the linked list contains the actual data, the data can be in form of an int value, float, char etc..
and the link part of the list contains the address of the next node in the list.
In the image above, there is a linked list made up of thee nodes. 1001, 1006 and 1009 are the addresses of each node respectively. You may see first node contains the address of the second node ie; 1006, second node contains the address of the third node ie; 1009 and because the third node is the last node in the list it has no next node so it has NULL in its link field. NULL has a predefined meaning in c language, it means empty or nothing.
If there is only one node in the linked list then that node is the first node as well as the last node and its link field will be NULL.
Each node stores the address of its next node but who stores the address of the first node ?
For this we have a start pointer, start is a pointer variable which stores the address of the first node in the list.
The general form of a node of a linked list
struct node {
          int info;                       /*** data type <name>***/
          struct node * link;        Â
         };
Structures will be used in linked list programs as used in the above example a short tutorial on structures if you are not familiar with it. https://youtu.be/JSSTnytdJUI
info is just a variable info part of the node which stores the data in form of an integer value and link is a pointer variable of type struct node which stores the address of the next node.
Empty condition
When the value of start is equal to null then the linked list is empty.
In the program initially we initialize the value of start to be equal to NULL and later when new nodes are added or deleted then the value of start changes accordingly.
struct node *start = NULL;
Traversing a linked list:Traversing means visiting nodes of a linked list in sequence starting from the first node one after the other.
Remember that linked list does not allow random access it only allows sequential access. So if there are 5 nodes in a linked list and we want to access the 4th node then starting from the first node we have to go through nodes 1, 2 and 3 to reach and access the 4th node, direct access to the nodes cannot take place in a linked list therefore traversal is important.
Lets take an example, in the above fig. there is a linked liked with three nodes. Lets say the user wants to visit the 3rd node in the list. This is how traversal is done.
Start pointer variable has the address of the first node, first node is the entry point into the linked list.
We declare another pointer variable and assign it the value of start which is the address of the first node.
struct node *p;
p = start;
while(p != NULL)
{
p = p->link;
}
The above while loop means as long as p is not equal to null keep on executing p = p-> link.
-> called the arrow operator and it is used to access the members of the structure using pointer variable. Shot tutorial on arrow operator https://youtu.be/J2iHTv5VVgg
Refer to the image above first time the while loop runs the value of p is 1001 which means the first node and p -> link means link part of that node and the link of that node is 1005.
p -> link evaluates to 1005 address of the second node.
So in the statement p = p -> link pointer variable p is assigned 1005.
Second time the while loop runs
Value of p will be 1005, p means second node and the link part of the second node p->link is 1008 ie; the address of the third node.
p will be assigned the address of the next node p = p -> link;
Third time the while loop runs
Value of p will be 1008
p = p -> link
p will be assigned p -> link which is the link part of that node and this time the link part is NULL so now p is equal to NULL.
Now all the nodes of the list have been visited, we don’t need any more traversing.
Fourth time the while loop runs
P is equal to NULL while loop becomes false and terminates.
Now that we know traversal we can easily create display function for our program on linked list by adding a simple printf function.
void display(struct node *start)
{
struct node *p;
if(start==NULL)
{
printf("nList is emptyn");
return;
}
p=start;
printf("List is : n");
while(p != NULL)
{
printf("%d ", p->info);
p=p->link;
}
}
p->info will will access whatever value is stored in the info variable of the structure or you can say info part of the node and printf function will print it each time the while loop runs while p is not equal to null.
p = p->link will move p to the next node each time the loop runs.
Adding a new node (insertion):
Adding a node at the beginning of the list or to an empty list. Initially a linked list is always empty.
The same code is enough to add nodes at the beginning of the list as well as into an empty list.
struct node *addatbeg(struct node *start, int num)
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
temp->info=num;
temp->link = start;
start = temp;
return start;
}
In the above code first we declare a pointer variable temp.
The malloc() function is used for dynamic memory allocation. In simple words here it allocates memory for the new node and returns the address of that memory location, the address is then assigned to pointer variable temp. Tutorial on malloc() function https://youtu.be/B4NRsJhM9WA
So temp has the address of the new node.
temp->info=num
temp->info means the info part of the new node which is assigned the value of num, the value is entered by user using scanf function in the main() and passed as an argument in the addatbeg() function
Now placing the new node into the list.
       temp->link = start;
Start has the address of the first node or if the list is empty then start is equal to NULL.
The new node temp which is added into the list will become the first node in the list.
If the list was previously empty then NULL will be assigned to the link part of the new node with the help of the statement temp->link = start;
Or if the list was previously not empty then the address of the next node will be assigned to the link part of the new node with the help of the same statement temp->link = start;
start = temp;
start should always hold the address of the first node and since the new node temp is the first node in the list so start is assigned its address.
return start;
The value of start has changed so it needs to be updated. The returned value of start goes into the main function and updates the value of start so that the next time if addatbeg function is called from the main() then the correct updated value of start is passed.
Adding a node at the end of a linked list
void addatend(struct node *start, int num)
{
struct node *temp, *p;
temp=(struct node *)malloc(sizeof(struct node));
temp->info=num;
p=start;
while(p->link!=NULL)
{
p = p->link;
}
p->link = temp;
temp->link = NULL;
}
The first three lines in the code is the same that was used in the previous case.
The while loop and p=p->link statement is used for traversal because first we need to reach the last node in the list then only we can insert a node at the end.
When p will be at the last node of the list then p->link will be equal to null which will make the while condition false, terminate the while loop and the following two statements will get executed.
          p->link = temp;
temp is the newly created node and its address will be assigned to the link part of node p which will now become the second last node in the list and temp will become the last node in the list and the link part of the last node should always be null and the following statement will ensure that.
          temp->link = NULL;
Here we don’t need to return start because as opposed to the previous case here adding a node at the end of the list does not change the value of start.
Deletion
In deletion the node to be deleted is passed by the user through scanf function in the main(). The node to be deleted is recognized by the data it contains. So if there is a node that contains integer value 25 in its info part and the user enters 25 to be deleted then that node would get deleted.
struct node *del(struct node *start,int num)
{
struct node *tmp,*p;
if(start==NULL)
{
printf("List is emptyn");
return start;
}
if(start->info==num) /*deletion from first or only node*/
{
tmp=start;
start=start->link;
free(tmp);
return start;
}
p=start;
while(p->link!=NULL)
{
if(p->link->info==num)
{
tmp = p->link;
p->link = tmp->link;
free(tmp);
return start;
}
p=p->link;
}
printf("%d not presentn",num);
return start;
}
if(start->info==num)Â Â Â Â Â Â Â Â /*deletion from first or only node*/
{
tmp=start;
start=start->link;
free(tmp);
return start;
}
This part of the delete function handles the situation where the node to be deleted is the first node in the list.
This if condition if(start->info==num) will become true if the number entered by the user is equal to the info part of the first node because start holds the address of the first node.
start=start->link;
start->link means the link part of the first node which contains the address of the next node or the second node. It is assigned to start so the second node becomes the first node.
free(tmp);
Since memory is dynamically allocated in case of a linked list and dynamically allocated memory is not freed automatically so we have to free the memory by using free() function.
return start;
When the first node is changed the value of start also changes so we need to return the value so that it gets updated in the main() function.
The return statement here also help us to get out of del() function after deletion is performed.
If the node to be deleted is not the first node then traversing will take place each node with be checked.
if(p->link->info==num)
p->link->info means the info part of the next node. If info part of the next node is equal to the number entered by the user (num) then the condition becomes true and node is deleted from anywhere in the list except the first node. It can also delete the last node in the list.
The following code will get executed if the above if condition becomes true.
tmp = p->link;
p->link = tmp->link;
free(tmp);
return start;
If the number is present p will stop right before the node to be deleted.
tmp = p->link  Assign tmp the address of node which is going to be deleted in the above image it is p->link ie 1008
p->link = tmp->link;Â tmp is 1008 ie; last node and its link part is NULL so null will be assigned to the second last node thus making it the last node in the list. Imagine if tmp was not the last node then also this code would have done its job the address of the next node would have been assigned to p->link instead of null, removing node tmp.
return start;
Value of start doesn’t get changed but still we need to return some value because the del() function is not of type void and return statement helps the program control to get out of delete fucking after the job is completed.
If the while condition becomes false it would mean that the number or node to be deleted is not present in the list and printf(“%d not presentn”,num); number not present will be displayed to the user.
/***************www.marxtudor.com****************/
#include
#include
#define MAX 5
void insert(int);
int del();
void display();
int cqueue[MAX];
int front=-1;
int rear=-1;
main()
{
int choice, num;
while(1)
{
printf("nEnter your choicen");
printf("1. Insertn");
printf("2. Deleten");
printf("3. Displayn");
printf("4. Exitn");
scanf("%d",&choice);
switch(choice)
{ case 1:
printf("Enter a number to be inserted : ");
scanf("%d",&num);
insert(num);
break;
case 2:
num=del();
break;
case 3:
display();
break;
case 4:
exit(1);
default:
printf("Invalid choicen");
}
}
}
void insert(int element)
{
if((front==0 && rear==MAX-1) || (front==rear+1))
{
printf("Queue is fulln");
return;
}
if(front==-1)
{
front = 0;
}
if(rear==MAX-1)
{
rear=0;
}
else
{
rear=rear+1;
}
cqueue[rear]=element;
}
int del()
{
int element;
if(front==-1)
{
printf("Queue is Emptyn");
return;
}
element = cqueue[front];
if(front==rear)
{
front=-1;
rear=-1;
}
else if(front==MAX-1)
{
front=0;
}
else
{
front = front + 1;
}
printf("%d has been deleted n",element);
return element;
}
void display()
{
if(front==-1)
{
printf("Queue is Emptyn");
return;
}
int i;
i=front;
if(front<=rear)
{
while(i<=rear)
printf("%d ",cqueue[i++]);
}
else {
while(i<=MAX-1)
printf("%d ",cqueue[i++]);
i=0;
while(i<=rear)
printf("%d ",cqueue[i++]);
}
}
In a simple queue when the Rear reaches the last position or if Rear is equal to MAX-1 then insertion is not possible.
See the above two images in the first image the queue was full then we deleted 3 elements from the queue.
You may see in the second image there are 3 empty positions (0, 1 and 2) in the array/queue. In case of simple queue we cannot insert elements into those empty positions because in a simple queue when Rear is at the last position in other words when Rear is equal to MAX-1 (Rear==MAX-1) then the queue is full and insertion cannot take place, elements in the queue are always inserted from the rear end.
But in case of circular queue we can insert new elements into those empty positions. So circular queue or array overcomes the limitation of simple queue.
We can think of a circular queue as both the ends of the array above joint together to form a circle.
Insertion and deletion operations in a circular queue can be performed in a manner similar to that of a queue but we need to take care of few things.
When rear is at last position or rear is equal to MAX-1 then then instead of incrementing rear we reset rear to zero and then perform insertion.
In the same way when front is at the last position of the queue (front == MAX-1) then instead of incrementing front we reset the value of front to 0.
The overflow condition in case of circular queue is different, a circular queue will be full only when all the positions are occupied as opposed to Rear equals to MAX-1 in case of a simple queue.
A circular queue will be full in two situations:
Condition 1:
When the value of front is equal to 0 and Rear equals to MAX-1 as shown in the above image.
if(front==0 && rear==MAX-1)Â
Condition 2:
In the image above initially the queue was full then 3 elements gets deleted there are three empty positions (0,1 and 2)
First 11 then 15 and finally 20 is inserted into the queue.
In the last instance the value of Rear is 2 and Front is 3 which means front = rear + 1
Hence;
if(front==(rear+1) then circular queue is full
Complete overflow condition of the circular queue.
    if((front==0 && rear==MAX-1) || (front==rear+1))
{
printf(“Queue is fulln”);
   }
To implement circular queue using an array we may create the following three function.
void insert(int) – for insertion
int del() – for deletion
void display() – for displaying elements in the queue.
In the insert function first we should check if the queue is full, if it is then the user should not be allowed to insert elements into the queue.
void insert(int element)
{
if((front==0 && rear==MAX-1) || (front==rear+1))
{
printf("Queue is fulln");
return;
}
if(front==-1)
{
front = 0;
}
if(rear==MAX-1)
{
rear=0;
}
else
{
rear=rear+1;
}
cqueue[rear]=element;
}
If front is is -1 and the user wants to insert an element into the queue then first front should be made zero.
 if(front==-1)
{
front = 0;
}
If rear is at the last position of the queue and the user wants to insert an element, if(rear==MAX-1) then rear should be made equal to zero so that the new element can be inserted from 0th position of the queue if it is empty.
 if(rear==MAX-1)
{
rear=0;
}
If not then else condition will be executed which is the same increment statement rear=rear+1 that is used in simple queue to first increment the value of rear and then insert the element at the rear position.
    else
{
rear=rear+1;
}
 The new element into the queue is inserted using the following statement
cqueue[rear]=element;
Here element is the user entered value with the help of scanf function which is be passed as an argument into the function void insert(int element) from the main function whenever the insert function is called.
So this is the insert function in case of a circular queue.
Now the underflow condition and delete function.
A circular queue will be empty initially when the value of front is equal to -1. Remember the value of Front and Rear are always equal to -1 initially.
In the image above the 3 elements in the queue are deleted, you should know when each time an element is deleted from the queue the value of front is incremented by 1 (front = front + 1)
Finally Front is equal to Rear + 1 and the queue is empty.
In the above fig. all the elements 15, 25, 55,20,90 gets deleted one by one and each time the element from the queue is deleted the value of front is incremented by one (front=front+1) except when Front is at the MAX-1 or the last position of the queue which is 5 in the above example then instead of incrementing the value of front we reset the value of front to zero so finally Front = 0 and Rear = Max-1 and the queue is empty.
But wait; the above two conditions
front=rear+1
and
front=0 and rear=MAX-1
is also true when the circular queue is full so we have to make some changes here to differentiate between and empty queue and full queue.
Leave the insert function and overflow condition as it is and make changes in underflow condition and delete function.
In the delete function we first check if the queue is empty, if it is then queue empty message should be displayed to the user.
int del()
{
int element;
if(front==-1)
{
printf("Queue is Emptyn");
return;
}
element = cqueue[front];
if(front==rear)
{
front=-1;
rear=-1;
}
else if(front==MAX-1)
{
front=0;
}
else
{
front = front + 1;
}
printf("%d has been deleted n",element);
return element;
}
element = cqueue[front]; assigning element the value w will which be deleted so that it can be returned afterwards, the function is of type int. Remember in a queue the element always gets deleted front he front end.
Always remember that there is always one element in the queue when Front is equal to Rear. This always happens as you may see the above fig. when there is one element 30 in the queue front and rear are both equal to 2.
So if front is equal to rear which means one element in the queue and the user calls the delete function to delete an element then what happens ?
The queue becomes empty so inside delete function we can write this code.
if(front==rear)
{
front = -1;
rear = -1;
}
Resetting the value of front and rear to -1. The next time user calls delete function front will be equal to -1 and front = -1 means queue is empty.
else if(front==MAX-1)
{
front=0;
}
If front is at the last position of the queue then reset the value of front to zero.
else
{
front = front + 1;
}
If none of the above conditions are true then usual front = front+1, value of front is incremented and element deleted from the queue.
Display function
void display()
{
if(front==-1)
{
printf("Queue is Emptyn");
return;
}
int i;
i=front;
if(front<=rear)
{
while(i<=rear)
printf("%d ",cqueue[i++]);
}
else {
while(i<=MAX-1)
printf("%d ",cqueue[i++]);
i=0;
while(i<=rear)
printf("%d ",cqueue[i++]);
}
}
/*************** BY Marxtudor www.marxtudor.com/ ***************/ #include#define MAX 5 void insert(int); int del(); void display(); int queue[MAX]; int front=-1; int rear=-1; main() { int choice, num; while(1) { printf("nEnter your choicen"); printf("1. Insertn"); printf("2. Deleten"); printf("3. Displayn"); printf("4. Exitn"); scanf("%d",&choice); switch(choice) { case 1: printf("Enter a number to be inserted : "); scanf("%d",&num); insert(num); break; case 2: num=del(); break; case 3: display(); break; case 4: exit(1); default: printf("Invalid choicen"); } } } void insert(int element) { if(rear==MAX-1) { printf("nQueue is Fulln"); return; } if(front==-1) { front = 0; } rear=rear+1; queue[rear]=element; } int del() { int element; if(front==-1 || front==rear+1) { printf("Queue is Emptyn"); return; } element = queue[front]; front = front + 1; printf("%d has been deletedn", element); return element; } void display() { if(front==-1 || front==rear+1) { printf("Queue is Emptyn"); return; } int i; for(i=front; i<=rear; i++) { printf("%d ",queue[i]); } }