[click to read Insert at last] …………………….. [click to read Insert between first and last node]
Till now we have got the basic knowledge of the linked list i.e. what is linked list, how it looks like and what is the basic concept of linked list.
Now let’s understand basic linked list operation and will also understand that how these operations will be performed.
Inserting a new node in the list is done at the three scenarios, it will be inserted at the beginning, or at the last or somewhere between the first and last. To perform these operations we need to understand the scenarios where these different operations are used. Possible cases are
- inserting into an empty list, i.e. there is no node existing so you are inserting this node as a first node
- inserting at the beginning or at the front in an existing linked list
- inserting at the last or at the back in an existing linked list
- inserting somewhere between the first and last
Though we see here four cases or the four scenarios but actually we can combine these situations into two cases as a whole. Logically inserting a node in case-1 and case-2 is dealt with the same kind of logic though the scenarios look different but almost same logic is applicable in both the cases. Similarly inserting node in the between or at the last of the linked list uses same kind of logic.
Before we actually move to the algorithm and to the actual program stuff we need to understand logically that what actually we are looking for, unless you understand the scenario you are not in a position to understand the algorithm.
Inserting a new node at the beginning
If you are interested to add a new node as the first node that means you want to make this node as the starting node, it means the head or the front pointer must then point to this node, when you insert at the beginning, then new node should be considered as head. This can be achieved using following logic
- declare new node
- Make new node point to first node of the list
- head need to point the new node, it means that this earlier first node will be treated as a second node
let us understand uh the logic, there is the linked list consists of three nodes (see figure).
- Create a new node which we are interested to insert ( its address is stored at some pointer variable, say node, this new node is isolated initially)
- First node of existing list is pointed to by the front, means front keeps the address of the first node.
- Make the new node point to the first node (i.e. assign the address stored in front to the link field of new node). This means that now the newly created node is no more isolated but connects to the existing linked list. Still the new node is not pointed by the front
- Assign the address stored in pointer variable node to front, it means that now front will point to the newly created node.
So now our task is achieved as front is pointing to new node and this node is pointing to the previous first node and hence we succeeded in adding new node at the beginning.
(Note: head and front, both are having the same meaning and is used interchangeably at different part of the discussion)
Algorithm- Inserting Node at Beginning Let us look at the algorithm; the logic that we have discussed now to be represented in terms of pseudo code which will be implemented using any programming language
void insert_beg(int val)
The pseudocode given is to any function definition. It takes the one parameter (int), here we pass the value which we are looking to store in the newly created node.
node *temp=new node;
temp->info=val;
temp is a pointer variable of type node, it will store the address of any node type. This statement will create one node (each node contains of two information data and the link,data to store the actual value and link i to store the address).
The above statement will allocate space in the memory and will return the address of this location which is stored in variable temp. Here info refersto data field of the node, in our case we are assuming it of type integer, also we have one link field which we are referring as next to hold the address of next node (connecting node). In the information field, info we assigned value val which is passed to function as an argument.
If (head==NULL) # this statement checks if the list is empty
If initially head equals to NULL, here, head is a pointer variable that stores the value of the first node, head= NULL means your list is empty or no node exists. In this case, we actually insert a new node as a first node
{ head=temp; temp->next=NULL}
so head equals to temp means head is now going to store the address of new node and temp->next equals to NULL means this node is also the last node of the linked list.
Otherwise if the head is not NULL, means already the list already exists.
else{ temp->next=head; head=temp; } }
Assume a scenario where we have three nodes already existing is the list
Just recall that we have a new node whose address is at the temp and head contains the address of the first node
temp->next = head
The above statement means that now the new node contains the address of first node of the list and
head=temp
means head is now pointing to new node so now head points to new node and new node points (connects) to first node (of previous list). Entire logic is simple and straight forward but we have to be careful while dealing pointers. If you write any of them incorrectly then the entire logic will crash and you will not get the desired results.
Expertvision 