This article is dedicated to the launch of the course "Algorithms for Developers" from OTUS. I express my gratitude for the support of the resource by this company.
Let's explore what operations can be performed on a linked list.
Two important points to remember:
- head points to the first node of the linked list
- next the last node pointer is nullptr , so if the next node from the current node is nullptr , we have reached the end of the linked list.
In all examples, we will assume that the linked list has three nodes 1 ---> 2 ---> 3 with a node structure as shown below:
struct node
{
int data;
struct node* next {nullptr};
};
How to iterate through a linked list
Displaying the contents of a linked list is very simple. We continue to move the temporary node to the next one and display its contents.
When temp is NULL , we know we've reached the end of the linked list, so we exit the while loop.
struct node* temp = head;
std::cout << std::endl << std::endl << "List elements are - " << std::endl;
while(temp != nullptr)
{
std::cout << temp->data << " ---> ";
temp = temp->next;
}
The output of this program will be:
List elements are - 1 ---> 2 ---> 3 --->
How to add elements to a linked list
You can add elements to the beginning, middle, or end of a linked list.
Add to start
- Allocate memory for the new node
- Save data
- Change the new next node to point to head
- Change head to point to the newly created node
struct node* newNode = new node(); newNode->data = value; newNode->next = head; head = newNode;
Add to end
- Allocate memory for the new node
- Save data
- Make a transition to the last node
- Change next from last node to newly created node
struct node* newNode = new node();
newNode->data = value;
newNode->next = nullptr;
struct node *temp = head;
while (temp->next != nullptr)
{
temp = temp->next;
}
temp->next = newNode;
Add to middle
- Allocate memory and store data for the new node
- Jump to the node immediately before the desired position of the new node
- Change next pointers to add a new node in between
struct node *newNode = new node();
newNode->data = value;
struct node *temp = head;
for (int i=2; i < position; i++)
{
if (temp->next != nullptr)
{
temp = temp->next;
}
}
newNode->next = temp->next;
temp->next = newNode;
How to remove a node from a linked list
You can delete either from start, end or from a specific position.
Delete from beginning
- Set the head pointer to the second node
head = head->next;
Delete from the end
- Go to second last element
- Change next pointer to nullptr
struct node* temp = head;
while (temp->next->next != nullptr)
{
temp = temp->next;
}
temp->next = nullptr;
Remove from middle
- Move to the element before the element to be removed
- Change next pointers to exclude the node from the chain
struct node* temp = head;
for (int i = 2; i < position; ++i)
{
if (temp->next != nullptr)
{
temp = temp->next;
}
}
temp->next = temp->next->next;
Complete program for linked list operations
Here is the complete program for all the linked list operations we have learned. Many edge cases have been omitted to keep the program short.
We suggest you just take a look at the program and try to implement it yourself.
Also notice how we pass the address of head as struct node headRef in the insertAtFront and deleteFromFront functions. These two functions change the position of the head pointer, so we need to pass the address of the head** pointer and change its value inside the function.
#include <iostream>
struct node
{
int data;
struct node* next {nullptr};
};
void display(struct node* head)
{
struct node* temp = head;
std::cout << std::endl << std::endl << "List elements are - " << std::endl;
while(temp != nullptr)
{
std::cout << temp->data << " ---> ";
temp = temp->next;
}
}
void insertAtMiddle(struct node *head, int position, int value)
{
struct node *newNode = new node();
newNode->data = value;
struct node *temp = head;
for (int i=2; i < position; i++)
{
if (temp->next != nullptr)
{
temp = temp->next;
}
}
newNode->next = temp->next;
temp->next = newNode;
}
void insertAtFront(struct node** headRef, int value)
{
struct node* head = *headRef;
struct node* newNode = new node();
newNode->data = value;
newNode->next = head;
head = newNode;
*headRef = head;
}
void insertAtEnd(struct node* head, int value)
{
struct node* newNode = new node();
newNode->data = value;
newNode->next = nullptr;
struct node *temp = head;
while (temp->next != nullptr)
{
temp = temp->next;
}
temp->next = newNode;
}
void deleteFromFront(struct node** headRef)
{
struct node* head = *headRef;
head = head->next;
*headRef = head;
}
void deleteFromEnd(struct node* head)
{
struct node* temp = head;
while (temp->next->next != nullptr)
{
temp = temp->next;
}
temp->next = nullptr;
}
void deleteFromMiddle(struct node* head, int position)
{
struct node* temp = head;
for (int i = 2; i < position; ++i)
{
if (temp->next != nullptr)
{
temp = temp->next;
}
}
temp->next = temp->next->next;
}
int main()
{
/* Initialize nodes */
struct node *head;
struct node *one = new node();
struct node *two = new node();
struct node *three = new node();
/* Assign data values */
one->data = 1;
two->data = 2;
three->data = 3;
/* Connect nodes */
one->next = two;
two->next = three;
three->next = nullptr;
/* Save address of first node in head */
head = one;
display(head); // 1 ---> 2 ---> 3 --->
insertAtFront(&head, 4);
display(head); // 4 ---> 1 ---> 2 ---> 3 --->
deleteFromFront(&head);
display(head); // 1 ---> 2 ---> 3 --->
insertAtEnd(head, 5);
display(head); // 1 ---> 2 ---> 3 ---> 5 --->
deleteFromEnd(head);
display(head); // 1 ---> 2 ---> 3 --->
int position = 3;
insertAtMiddle(head, position, 10);
display(head); // 1 ---> 2 ---> 10 ---> 3 --->
deleteFromMiddle(head, position);
display(head); // 1 ---> 2 ---> 3 --->
}
The output of the program will be as follows
List elements are - 1 ---> 2 ---> 3 ---> List elements are - 4 ---> 1 ---> 2 ---> 3 ---> List elements are - 1 ---> 2 ---> 3 ---> List elements are - 1 ---> 2 ---> 3 ---> 5 ---> List elements are - 1 ---> 2 ---> 3 ---> List elements are - 1 ---> 2 ---> 10 ---> 3 ---> List elements are - 1 ---> 2 ---> 3 --->
Conclusion
You can also study algorithms in more depth on the course "Algorithms for Developers" from OTUS you You will be able to study in more depth both basic algorithms and more complex ones.
The course offers the following:
- Understanding the principles of operation of various algorithms, data structures
- Ability to use ready-made algorithms and data structures and create your own for the task
- Possession of the technique of calculating the complexity of algorithms
- Mastering advanced data structures: hash tables, graphs, search trees and more
- Ability to solve algebraic problems and dynamic programming problems
At the same time, this course offers the study of algorithms and data structures using such programming languages as Java, C ++, Python.
You can test your skills in testing to understand if you are ready to take this course and what this course will give you additionally.
