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;
}
Traverse operation
Visiting all nodes in the linked list is called traversal of a Linked list.
Steps are as follows:
- Start with the head node of the Linked list.
- Using next pointer go to the next node and get data.
- Keep on repeating previous steps till we reached NULL node.
Let’s look into the sample code
bool traversal (LinkedList* start)
{
while (start)
{
cout << "Data: " << start -> data << endl;
start = start -> next;
}
return false;
}
Search Operation
Searching a node in the linked list is a very common operations which is done via traversing of Linked List.
Steps are as follows:
- Start with the head node of the Linked list.
- Using next pointer go to the next node and compare data with searched data.
- Keep on repeating previous steps till we reached NULL node or we find searched data.
Let’s look into the sample code.
bool search_element (LinkedList* start, int searched_data)
{
LinkedList* temp = start;
while (temp)
{
if (temp -> data == searched_data)
{
cout << "Found the searched data: " << searched_data << endl;
return true;
}
temp = temp -> next;
}
cout << "Did not find the searched data: " << searched_data << endl;
return false;
}
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 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);
int searched_data = 5;
cout << "Searching element in linked list: " << searched_data << endl;
search_element (start, searched_data);
print_linked_list (start);
cout << "End check_searched_items_log" << endl;
}
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
Searching element in linked list: 5
Found the searched data: 5
3 5 7 9 2 3 11 16
