Linked List
Shall we start with the typical definition then?
According to Wikipedia :
In computer science, a linked list is a linear collection of data elements, whose order is not given by their physical placement in memory. Instead, each element points to the next.
If this isn't clear (and I know it's not), lemme tell you how it's different from arrays and then the concept shall make itself more clear as we proceed from there.
We can imagine an array as a long-ass bench in a class with a certain seating capacity (say 9), and there are 7 people sitting in it currently.
When we initialize an array, we have to set it to a particular size. That size might be 7, 9, 10, or 100, or 1000 or whatever.
But if we don't know exactly how many people are going to sit, how do we decide the size?
If we take a huge-ass bench (big size array), it'll take a lot of space in the class (in computer memory), but if enough students don't show up, all that extra space would be wasted.
Conversely, if we choose a small sized bench (small array), what do we do if huge number of students show up?
We'll have to dispose that old smaller bench, and deploy an entirely new (bigger) bench, to accommodate more people. Not only that, we'll have to move that entire previous group of students (the entire data) from the old bench (array) to the new bench (array) .
Therefore!!!
We come up with a new solution!
We introduce single-seater seats, where each bench accommodates only 1 person, AND also shows you the direction to the next bench, so the students still sit on order, but not necessarily next to each other
Something like this:
This way, we need not worry about the size. Because, we can just add more benches as new students show up. Each students points to the next student.
When a student has no bench pointing towards it, it means that he's the first student.
When a student's pointer has nothing to point to, it's the last student.
If in case, we need to enter a student (3.5) in between student 3 and 4, we can just make the 3 point to 3.5 (instead of 4) and then make 3.5 point to 4.
That way the series goes 1 -> 2 -> 3 -> 3.5 -> 4 -> 5 and so on...
(In Contrast, if we were to put a 3.5 between 3 and 4 in an array, we would've had to shift all the elements from 4 to 7 and then insert the 3.5 where 4 originally was)
The definition should be pretty clear now, "Linked list is a linear collection of data elements" (is a collection of students(data)), " whose order is not given by their physical placement in memory" (they can be anywhere in the memory, not necessarily next to each other(like how the students are placed randomly in the class)), "each element points to the next".
Assuming you now understand the concept, let's introduce you to the formal terms.
That single seater bench is called a node.
A node has 2 parts. The first part stores data and other part is a pointer that points to the next node.
AND NOW!!
TIME TO CODE!!!
We'll code in C (because Python is out of syllabus and JAVA is an unnecessarily complex piece of trash language that none should ever have the misfortune of using).
OK.
Defining a node (We'd obviously have to tell the computer what a node is, before we start using it)
struct Node {
int data; //data containing part
struct Node* next; //address to the next node
};
You should notice something slightly off. It's that there is no data type before next (no int, or string, or float, or anything), instead, it is struct Node*.
This is a self-referencing pointer. It means a pointer that points to whatever it is a part of. Here, next is a part of the node and it will point to the next node
OK.
Now that we have created we know exactly what a node is, let's look at the code to create a node and insert it.
We'll initialize a start node, with no data and something that points to absolutely nothing. For now, it's just a placeholder, for the first node to be.
we do this by declaring a global start node by :
struct node *start = NULL;Now, let's create a function to create new nodes:
We'll first initialize two nodes called temp and ptr by :
struct node *temp, *ptr;We're going to put our data in the temp node, so we'll first have to dynamically allocate a memory, of the size of the node to the node structure
We do this by:
temp = (struct node *)malloc(sizeof(struct node));what this says is :
1. struct node is the structure of our node.
2. sizeof(struct node) calculates the size of the node.
3. malloc(sizeof(struct node)) will allocate that much size in the memory.
4. (struct node *) is the pointer that points to that memory location.
Therefore, temp refers to a pointer that points to a memory location of the size of the node.
Now, before creating a node, we should first check whether we have enough space (in our memory) to allocate to a node. We do this by :
if (temp==NULL) {
printf("\n Out of memory space. \n");
}
Now that we've ensured that there's space in your memory for a new node. We'll check if there's already a start node
If there isn't any start node, then we'll make temp, the start node. Otherwise, we'll use that second node that we created (the ptr node), and we'll start traversing from the start node and keep on travelling through the linked list, until we come across the end node (some node that points to null (see diagram)).
Now how do we traverse through the linked list?
Simple. We start from the first node. We call it ptr and we check if the current node (the start node) points to NULL or not, if it doesn't, then it obviously points to the next node, and so, we call the next node as ptr, and check if THAT node points to NULL, if it doesn't, then we go to the next node, call it ptr, and check the NULL and so on.
The ptr goes on travelling from the first node to the last.
Therefore, this entire process would be coded as
if (start==NULL)
{
start = temp;
}
else
{
ptr = start;
while (ptr->next!=NULL)
{
ptr = ptr->next;
}
ptr->next = temp;
}
To Insert at Specific Position, we'll follow an example.
If I have to insert a node at position 4, then I'll traverse till 3 (right before 4), and change the pointer of the 3rd node to the new node, hence the new node is then the 4th node. We now change the pointer of our new 4th node to the 5th node (which was previously the old 4th node)
So, now that we have a clear idea of what we want to do, I'll just show you the code and explain what each line is doing
struct node *ptr, *temp;int i, pos;
temp = (struct node *) malloc(sizeof(struct node));
printf("Enter the position of the new node to be inserted : ");
scanf("%d", &pos);
printf("Enter the data value of the node: ");
scanf("%d", &temp->info);
temp->next= NULL; //the current new node points to zero
if(pos==0) //if the entered position is 0
{
temp->next = start; //make the temp point to the start node
start = temp; //make temp the start node
}
else
{
for(i=0, ptr=start ; i<pos-1;i++)//travel till one node BEFORE the selected position
{
ptr = ptr->next; //travelling
if (ptr==NULL) //if you hit no node
{
printf("Position not found");
return;
}
}
temp->next = ptr->next; //the 3rd node was connected to the old 4th node, but now, the new 4th node should point to where the 3rd node used to point
ptr->next = temp //3rd node should point to the new 4th node
}
Now, that we've learnt to traverse the linked list, enter different numbers into the linked list, the only thing that's left is to delete items from the linked list
Honestly, I'm getting just as tired writing all this as you are, reading and (hopefully) understanding. Let's just hurry up and end this ASAP.
Here's the principle:
We delete the whole node (the information as well as its pointer)
Not too hard to understand, right?
Here's the code:
int i, pos;
struct node *ptr, *temp;
printf("Enter the position you want to delete");
scanf("%d", &pos);
ptr = start; //we'll start traversing the linked list
for(i = 0; i<pos; i++) //keep traversing until you reach the position to be deleted
{
temp = ptr; //temp becomes ptr
ptr = ptr->next; //and ptr moves forward
if (ptr->next == NULL) //if you don't find anything in the end, then..
{
printf("Position not found");
return;
}
} //finally after reaching the node we want to delete
temp->next = ptr->next; //we make the previous node point to the node ptr was pointing towards
printf("Deleted item is %d", ptr->info); //show the content of ptr
free(ptr); //free the ptr from all its misery. The world is a cruel place after all
That's it!
Those were all the essential functions.
We can now implement many more functions that are basically just slight variations of same concepts written above
Here's a code for an entire working program where you can analyse more functions that are based on the very concepts that we learnt here
#include<stdlib.h>#include <stdio.h>
void create();
void display();
void insert_begin();
void insert_end();
void insert_pos();
void delete_begin();
void delete_end();
void delete_pos();
struct node
{
int info;
struct node *next;
};
struct node *start=NULL;
int main()
{
int choice;
while(1){
printf("\n MENU \n");
printf("\n 1.Create \n");
printf("\n 2.Display \n");
printf("\n 3.Insert at the beginning \n");
printf("\n 4.Insert at the end \n");
printf("\n 5.Insert at specified position \n");
printf("\n 6.Delete from beginning \n");
printf("\n 7.Delete from the end \n");
printf("\n 8.Delete from specified position \n");
printf("\n 9.Exit \n");
printf("\n--------------------------------------\n");
printf("Enter your choice:\t");
scanf("%d",&choice);
switch(choice)
{
case 1:
create();
break;
case 2:
display();
break;
case 3:
insert_begin();
break;
case 4:
insert_end();
break;
case 5:
insert_pos();
break;
case 6:
delete_begin();
break;
case 7:
delete_end();
break;
case 8:
delete_pos();
break;
case 9:
exit(0);
break;
default:
printf("n Wrong Choice:n");
break;
}
}
return 0;
}
void create()
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
if(temp==NULL)
{
printf("\nOut of Memory Space:\n");
exit(0);
}
if(start==NULL)
{
printf("\nEnter the data value for the node:\t");
scanf("%d", &temp->info);
temp->next = NULL;
start=temp;
}
else
{
printf("\nA linked list already exists.\n");
return;
}
}
void display()
{
struct node *ptr;
if(start==NULL)
{
printf("\nList is empty:\n");
return;
}
else
{
ptr=start;
printf("\nThe List elements are:\n");
while(ptr!=NULL)
{
printf("%d\t",ptr->info );
ptr=ptr->next ;
}
}
}
void insert_begin()
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
if(temp==NULL)
{
printf("\nOut of Memory Space:\n");
return;
}
printf("\nEnter the data value for the node:\t" );
scanf("%d",&temp->info);
temp->next =NULL;
if(start==NULL)
{
start=temp;
}
else
{
temp->next=start;
start=temp;
}
}
void insert_end()
{
struct node *temp,*ptr;
temp=(struct node *)malloc(sizeof(struct node));
if(temp==NULL)
{
printf("\nOut of Memory Space:\n");
return;
}
printf("\nEnter the data value for the node:\t" );
scanf("%d",&temp->info );
temp->next =NULL;
if(start==NULL)
{
start=temp;
}
else
{
ptr=start;
while(ptr->next !=NULL)
{
ptr=ptr->next ;
}
ptr->next =temp;
}
}
void insert_pos()
{
struct node *ptr,*temp;
int i,pos;
temp=(struct node *)malloc(sizeof(struct node));
if(temp==NULL)
{
printf("\nOut of Memory Space:\n");
return;
}
printf("nEnter the position for the new node to be inserted:\t");
scanf("%d",&pos);
printf("nEnter the data value of the node:\t");
scanf("%d",&temp->info) ;
temp->next=NULL;
if(pos==0)
{
temp->next=start;
start=temp;
}
else
{
for(i=0,ptr=start;i<pos-1;i++) {
ptr=ptr->next;
if(ptr==NULL)
{
printf("\nPosition not found:[Handle with care]\n");
return;
}
}
temp->next =ptr->next ;
ptr->next=temp;
}
}
void delete_begin()
{
struct node *ptr;
if(ptr==NULL)
{
printf("\nList is Empty:\n");
return;
}
else
{
ptr=start;
start=start->next ;
printf("\nThe deleted element is :%d\t",ptr->info);
free(ptr);
}
}
void delete_end()
{
struct node *temp,*ptr;
if(start==NULL)
{
printf("\nList is Empty:");
exit(0);
}
else if(start->next ==NULL)
{
ptr=start;
start=NULL;
printf("\nThe deleted element is:%d\t",ptr->info);
free(ptr);
}
else
{
ptr=start;
while(ptr->next!=NULL)
{
temp=ptr;
ptr=ptr->next;
}
temp->next=NULL;
printf("\nThe deleted element is:%d\t",ptr->info);
free(ptr);
}
}
void delete_pos()
{
int i,pos;
struct node *temp,*ptr;
if(start==NULL)
{
printf("\nThe List is Empty:\n");
exit(0);
}
else
{
printf("\nEnter the position of the node to be deleted:\t");
scanf("%d",&pos);
if(pos==0)
{
ptr=start;
start=start->next ;
printf("\nThe deleted element is:%d\t",ptr->info );
free(ptr);
}
else
{
ptr=start;
for(i=0;i<pos;i++) { temp=ptr; ptr=ptr->next ;
if(ptr==NULL)
{
printf("\nPosition not Found:\n");
return;
}
}
temp->next =ptr->next ;
printf("\nThe deleted element is:%d\t",ptr->info );
free(ptr);
}
}
}//Original code from https://www.edureka.co/blog/linked-list-in-c/. Posted with a lot of modifications.
I encourage you to copy and paste the entire code, run it on your computer, and observe carefully how each of these functions work.
If you are clear on all the concepts taught so far, I assure you that every function would be totally understandable.
And so, this is how we reach
Comments
Post a Comment