Double-linked list program in C++
A doubly linked list (DLL) is a special type of linked list where each node has a pointer to both the linked list's previous and next nodes. It consists of nodes formed using self-referential structures. Each node consists of three components: the data, the reference to the list node after it, and finally, the reference to the list node before it.
To access the entire list, a reference to the initial list node, (commonly known as head) is needed. NULL is stored there since the list's final node leads to nothing. Because every node in the list that is doubly linked points to its former and next node, it may also be explored in both directions.
#include <iostream>
using namespace std;
struct Point {
int info;
struct Point *before;
struct Point *after;
};
struct Point* head = NULL;
void add(int newinfo) {
struct Point* newpoint = (struct Point*) malloc(sizeof(struct Point));
newpoint->info = newinfo;
newpoint->before = NULL;
newpoint->after = head;
if(head != NULL)
head->before = newpoint ;
head = newpoint;
}
void show() {
struct Point* pointer;
pointer = head;
while(pointer != NULL) {
cout<< pointer->info <<" ";
pointer = pointer->after;
}
}
int main() {
add(1);
add(2);
add(3);
add(4);
add(5);
cout<<"This is the double linked list: ";
show();
return 0;
}
Output:
The structure node forms the doubly linked list node in the above program. Along with the data, it has a pointer to the linked list nodes that come before and after it. This is provided in the manner mentioned below.
struct Point {
int info;
struct Point *before;
struct Point *after;
};
The data is inserted at the start of the doubly linked list using the add() function. The number is inserted into the new node's data field as it is created. Next, as entered at the beginning, the previous pointer in the new point points to NULL, and the subsequent pointer points to the head. The previous pointer of the head points to the new node if the head is not NULL. The new point, or where the linked list begins, is the final node that makes up the head. This is provided below.
void add(int newinfo) {
struct Point* newpoint = (struct Point*) malloc(sizeof(struct Point));
newpoint->info = newinfo;
newpoint->before = NULL;
newpoint->after = head;
if(head != NULL)
head->before = newpoint ;
head = newpoint;
}
The entire doubly linked list is shown via the show() method. The pointer indicates the head first. After that, it is passed on to the following node without interruption until all the nodes' data values are displayed. This is provided below.
void show() {
struct Point* pointer;
pointer = head;
while(pointer != NULL) {
cout<< pointer->info <<" ";
pointer = pointer->after;
}
}
Different values are initially added to the doubly linked list using the add() function within the main() function. Subsequently, the doubly linked list is shown. This is provided below.
int main() {
add(1);
add(2);
add(3);
add(4);
add(5);
cout<<"This is the double linked list is: ";
show();
return 0;
}
Insertion in a double-linked list
A new node can be added to a doubly linked list in a manner quite similar to that of a linked list. A little more work is needed to keep the previous node's link alive. There are four methods to add a node to a doubly linked list:
- The DLL's front portion.
- Between two nodes
- Following a specific node.
- Ahead of a certain node.
- At the DLL's end.
With a doubly linked list, add a node at the front:
In the following Linked List, the new node always gets added before the head. The following five stages can be used to finish the task:
- Assign a new node first (let's say new_point).
- Now, fill the new node with the necessary data.
- Set the next of new_point to point to the doubly linked list's current head.
- Set the current head's before point to new_point.
- Align head to new_point lastly.
void push(Point** head_refer, int new_info)
{
Point* new_point = new Point();
new_point->info = new_info;
new_point->after = (*head_refer);
new_point->before = NULL;
if ((*head_refer) != NULL)
(*head_refer)->before = new_point;
(*head_refer) = new_point;
}
Place a node between two other nodes:
It is further divided into the subsequent two sections:
In a doubly linked list, add a node after a specified node:
A pointer to a node is provided as before_point, and the new point is put after the node that was provided. The following six steps can be used to accomplish this:
- Please make a new node first (let's say new_point).
- In the new node, enter the data now.
- Navigate to the following new node from the previous node.
- Move the previous nodes next to the new node.
- Move the new node's previous to the previous node.
- Move the previous pointer of the new node to new_point
void add next(Point* before_point, int new_info)
{
if (before_point == NULL) {
cout << "The preceding node provided cannot be NULL.";
return;
}
Point* new_point = new Point();
new_point->info = new_info;
new_point->after = prev_point->after;
prev_point->after= new_point;
new_point->before = before_point;
if (new_point->after != NULL)
new_point->after->before = new_point;
}
In a doubly linked list, append a node before an existing node:
Let next_point be the pointer to this specific node. The six steps below can be used to accomplish this.
- Set aside memory for the new node, which you should name new_point.
- Copy the data to the new node.
- Assign the preceding node of this new node to the preceding node of the subsequent node.
- As the new node, set the preceding pointer of the next_point.
- Next_point should be set to this new_point's next pointer.
- Set the new_point's prior pointer now.
- Set the next pointer of this previous node to new_point if the previous node of the new_point is not NULL.
- It becomes the new head node; otherwise, if the previous instance of new_point is NULL.
void addprev(Point* next_point, int new_info)
{
if (next_point == NULL) {
printf("The following node provided cannot be NULL");
return;
}
Point* new_point = new Point();
new_point->info = new_info;
new_point->before = next_point->before;
next_point->before = new_point;
new_point->after = next_point;
if (new_point->before != NULL)
new_point->before->after = new_point;
else
head = new_point;
}
In a doubly linked list, append a node at the end:
The new node will always appear after the last node in the provided Linked List. The following 7 steps can be used to accomplish this:
- Make a fresh node, let's say new_point.
- In the new node, enter the value.
- Set new_point's next pointer to null.
- Make new_point the head if the list is empty.
- If not, proceed to the linked list's end.
- Make the last node's next pointer point to new_point at this moment.
- Modify the preceding pointer of new_point to point to the list's last node.
void add(Point** head_refer, int new_info)
{
Point* new_point = new Point();
Point* end = *head_refer;
new_point-> info = new_info;
new_point-> after = NULL;
if (*head_refer == NULL) {
new_point-> before = NULL;
*head_refer = new_point;
return;
}
while (end-> after != NULL)
end = end -> after;
end->after = new_point;
new_point-> before = end;
return;
}
Features of the Double-Linked List
A doubly linked list has the following properties:
- Variable size: A doubly linked list's size is flexible, allowing for adding or removing nodes as needed.
- Two-way navigation: A doubly linked list allows for both forward and backward travel because each node has references to both the previous and next members.
- Memory overhead: Besides the memory needed for the data contained in the node, every node in a doubly linked list needs memory for two pointers—previous and next.
Benefits of a Double-Linked List:
- Navigation in both directions: Navigating the doubly linked list structure in both forward and backward directions facilitates list traversal and element access anywhere.
- Effective insertion and deletion: Thanks to the doubly linked list structure, elements can be inserted or removed from the list at any point. This can be helpful when elements need to be added or removed regularly.
- Versatility: A versatile and helpful tool in computer science, the doubly linked list can build many data structures and algorithms.
The Drawbacks of a Double-Linked List
- Memory overhead: Besides the memory needed for the data contained in the node, every node in a doubly linked list needs memory for two pointers—previous and next. In contrast to a singly linked list, which only requires one pointer, this may result in a larger memory overhead.
- Reduced access speeds: Compared to arrays, access times for individual elements in a doubly linked list may be slower since pointers must be followed to access a particular node.
- Pointer manipulation: Compared to arrays, the doubly linked list structure requires more pointer manipulation, which can lead to more complex code and possibly problems.