by Linked List is a data structure used for storing collection of data where successive elements are connected through pointers and the size of linked list can grow or shrink dynamically.
In short, Linked list can be thought as similar to array in which traversal can happen through pointers instead of indexes. Before going ahead have a look into Linked List Basics and Linked List Implementation.
Let’s have a look on basic class definition for Linked List.
class LinkedList
{
public:
int data;
LinkedList* next;
LinkedList (int data);
~LinkedList ();
};
/* Below function will print all nodes in a Linked List */
void print_linked_list (LinkedList* start)
{
if (!start)
{
cout << "Linked list is null, nothing to print" << endl;
return;
}
LinkedList* temp = start;
while (temp)
{
cout << " " << temp -> data;
temp = temp -> next;
}
cout << endl;
}
Insert Operation
Adding a new node in any Linked List is called Insert Operation. Multiple variations of Linked List Insert operations are possible which are Listed below.
Inserting a node at the beginning
In this case new node needs to be inserted at the beginning. After this operation this new node will become the 1st data node of the linked list. Steps are as follows:
- Allocate memory for the new node.
- store data and set next pointer of new node to current head node pointer.
- Change Head node pointer to point at this new node.
Let’s look into the code.
void insert_at_begining (LinkedList** start, int new_data)
{
LinkedList* temp = new LinkedList(new_data);
temp -> next = *start;
*start = temp;
}
Inserting a node after certain element
In this case new node needs to be inserted after a specific node. This operation requires traversing through Linked List till searched element found in the Linked List. After that new node will be inserted.
Steps are as follows:
- Traverse the linked list to reach just before the required position.
- Allocate memory for the new node.
- store data and set next pointer of new node to current head node pointer.
- Change Head node pointer to point at this new node.
Let’s look into the code.
void insert_after_certain_element (LinkedList* start, int new_data, int search_data)
{
LinkedList* temp = start;
LinkedList* prev = start;
cout << "Inserting node " << new_data << endl;
if (!temp)
{
LinkedList* n = new LinkedList (new_data);
start = n;
return;
}
while (temp)
{
if (temp -> data == search_data)
{
// This is the first element
LinkedList* n = new LinkedList (new_data);
n -> next = temp -> next;
temp -> next = n;
return;
}
prev = temp;
temp = temp -> next;
}
cout << "Searched data not found, hence putting new node at the end" << endl;
LinkedList* n = new LinkedList (new_data);
n -> next = prev -> next;
prev -> next = n;
return;
}
Let’s use these functions in an example main functions to explain the usage of these functions.
int main ()
{
LinkedList* start = NULL;
print_linked_list (start);
insert_at_begining (&start, 3);
insert_after_certain_element (start, 5, 6);
insert_after_certain_element (start, 7, 5);
insert_after_certain_element (start, 9, 8);
insert_after_certain_element (start, 11, 10);
insert_after_certain_element (start, 16, 11);
insert_after_certain_element (start, 2, 9);
insert_after_certain_element (start, 3, 2);
print_linked_list (start);
}
Note that we are allocating Linked List Nodes memory using “new” function call but we are not deleting the memory.
We will cover that part in delete operation section.
Let’s analyze the output of this main function.
Linked list is null, nothing to print
Inserting node 5
Searched data not found, hence putting new node at the end
Inserting node 7
Inserting node 9
Searched data not found, hence putting new node at the end
Inserting node 11
Searched data not found, hence putting new node at the end
Inserting node 16
Inserting node 2
Inserting node 3
3 5 7 9 2 3 11 16
