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;
}
Linked List Reversal
Reversing a Linked List means order of nodes in a linked list should be reversed. After this operation current head node will become the last node and last node will become the head node in the reversed list.
Algorithm to reverse the linked list
- we need to store three node address in order to reverse the linked list. previous, current and next node.
- Start from the head node.
- Next node of current should be set to previous node of current node.
- go to the next node and repeat the previous steps till we reach the end of the Linked List.
There are two methods can be used to traverse the linked list. We will show both method here. Algorithm to reverse the Linked List will remain same in both method.
Reversal of Linked List using Iteration
Let’s look into the sample code.
LinkedList* reverse_linked_list_using_iteration (LinkedList* start)
{
LinkedList* prev = NULL;
LinkedList* cur = start;
LinkedList* next = NULL;
while (cur)
{
next = cur -> next;
cur -> next = prev;
prev = cur;
cur = next;
}
return prev;
}
Reversal of Linked List using Recursion
Let’s look into the sample code.
LinkedList* reverse_linked_list_using_recursion (LinkedList* node, LinkedList* parent)
{
if (!node)
return NULL;
LinkedList* next = node -> next;
node -> next = parent;
if (!next)
return node;
return reverse_linked_list_using_recursion (next, node);
}
Let’s use these functions in an example main functions to explain the usage of these functions.
Few of the functions used below are explained in Linked List Insert operation, Linked List Delete Operation and Linked List Traverse and Search article . Refer those before moving ahead.
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);
start = reverse_linked_list_using_iteration (start);
print_linked_list (start);
start = reverse_linked_list_using_recursion (start, NULL);
print_linked_list (start);
cout << "Deleting Head Node " << endl;
delete_start_node (&start);
print_linked_list (start);
cout << "Deleting Node 11" << endl;
delete_searched_node (&start, 11);
print_linked_list (start);
cout << "Deleting all Nodes" << endl;
delete_all_node (&start);
print_linked_list (start);
cout << "End check_delete_items_log" << endl;
}
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
16 11 3 2 9 7 5 3
3 5 7 9 2 3 11 16
Deleting Head Node
5 7 9 2 3 11 16
Deleting Node 11
Node found, going to delete
5 7 9 2 3 16
Deleting all Nodes
Linked list is null, nothing to print
