Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Doubly-linked List contains an additional pointer, often called the first pointer, as well as the next pointer and data that could exist in a singly Linked List.

Here are the DLL nodes in C++.

/* Nodes of the bidirectional list */
class Node
{
	public:
	int data;
	Node* next; // A pointer to the next node in the DLL
	Node* prev; // A pointer to the previous node in the DLL
};
Copy the code

Here are the advantages and disadvantages of double-linked lists over single-linked lists. Advantages over unidirectional linked lists 1) A DLL can be traversed both forwards and backwards. 2) Deletion in a DLL is more efficient if a pointer is given to the node to be deleted. 3) We can quickly insert a new node before a given node. To delete a node in a singly linked list, you need a pointer to the previous node. To get the previous node, the list is sometimes traversed. In a DLL, we can use the previous pointer to get the previous node.

 

Disadvantages of unidirectional linked lists 1) Each node of a DLL needs extra space for the previous pointer. Although you can implement DLLS with single Pointers (see this and this). 2) All operations require an extra pointer to maintain. For example, when inserting, we need to modify both the previous and the next pointer. For example, in the following function for insertion at different locations, we need 1 or 2 additional steps to set the previous pointer. Insert nodes can be added in four ways: 1) before the DLL and 2) after a given node. 3) at the end of a DLL 4) before a given node.

1) add a node in front :(a 5-step process) new nodes are always added before the head of a given linked list. And the newly added node becomes the new header of the DLL. For example, if a given linked list is 10152025 and we add an item 5 in front, the linked list becomes 510152025. Let’s call the function added at the front of the list is push(). Push () must receive a pointer to a header pointer because push must change the header pointer to point to the new node

Here are five steps to add a node earlier.

/* Insert a new node in front of the list given a reference to the head of the list (a pointer to a pointer) and an int. * /
void push(Node** head_ref, int new_data)
{
        /* 1. Allocate nodes */
	Node* new_node = new Node(a);/* 2. Enter data */
	new_node->data = new_data;

	/* 3. Set the next node of the new node to the head and the previous node to NULL */
	new_node->next = (*head_ref);
	new_node->prev = NULL;

	/* 4. Change the prev of the first node to the new node */
	if((*head_ref) ! =NULL)
		(*head_ref)->prev = new_node;
		
	/* 5. Move the header to point to the new node */
	(*head_ref) = new_node;
}		
Copy the code

Four of the five steps above are the same as the four inserted earlier in the one-way list. The only additional step is to change the previous one of the headers. 2) Add a node after the given node. (a 7-step process) We get a pointer to the node as prev_node and insert the new node after the given node. \

void insertAfter(Node* prev_node, int new_data)
{
	if (prev_node == NULL)
	{
		cout<<"the given previous node cannot be NULL";
		return;
	}

	Node* new_node = new Node(a); new_node->data = new_data; new_node->next = prev_node->next; prev_node->next = new_node; new_node->prev = prev_node;if(new_node->next ! =NULL)
		new_node->next->prev = new_node;
}
Copy the code

The five-step procedure in the above steps is the same as the five steps used to insert after a given node in a one-way linked list. Two additional steps are required to change the previous pointer to the new node and the previous pointer to the next node of the new node. 3) add a node at the end :(7-step process) new nodes are always added after the last node in a given linked list. For example, if the given DLL is 510152025 and we add an item 30 at the end, the DLL becomes 51015202530. Since a linked list is usually represented by its head, we must traverse the list to the end, and then change the next last node to the new node.

Here are the final seven steps to add a node.

void append(Node** head_ref, int new_data)
{
	Node* new_node = new Node(a); Node* last = *head_ref; new_node->data = new_data; new_node->next =NULL;
	if (*head_ref == NULL)
	{
		new_node->prev = NULL;
		*head_ref = new_node;
		return;
	}
	while(last->next ! =NULL)
		last = last->next;
	last->next = new_node;
	new_node->prev = last;

	return;
}
Copy the code

Six of the seven steps above are the same as the six steps used to insert after a given node in a one-way linked list. An additional step is required to change the previous pointer to the new node. 4) Add a node before the given node: \

Step Set the pointer to this given node to next_node and the data for the new node to be added to new_data.

  1. Check whether next_node is NULL. If NULL, it is returned from the function because no new nodes can be added before NULL
  2. Allocate memory for the new node, named new_node
  3. Set new_node->data = new_data
  4. Set the previous pointer to new_node to the previous node of next_node, new_node->prev = next_node->prev
  5. Set the previous pointer to next_node to new_node, next_node->prev = new_node
  6. Set the next pointer to new_node to next_node, new_node->next = next_node;
  7. If the previous node of new_node is not NULL, set the next pointer to the previous node to new_node, new_node->prev->next = new_node
  8. Otherwise, if new_node’s prev is NULL, it will be the new head node. So make (*head_ref) = new_node.

Here is an implementation of the above method:

#include <iostream>
using namespace std;
struct Node {
	int data;
	struct Node* next;
	struct Node* prev;
};

void push(struct Node** head_ref, int new_data)
{
	struct Node* new_node
		= (struct Node*)malloc(sizeof(struct Node));

	new_node->data = new_data;

	new_node->next = (*head_ref);
	new_node->prev = NULL;

	if((*head_ref) ! =NULL)
		(*head_ref)->prev = new_node;

	(*head_ref) = new_node;
}
void insertBefore(struct Node** head_ref,
				struct Node* next_node, int new_data)
{
	if (next_node == NULL) {
		cout <<"the given next node cannot be NULL";
		return;
	}
	struct Node* new_node
		= (struct Node*)malloc(sizeof(struct Node));
	new_node->data = new_data;
	new_node->prev = next_node->prev;
	next_node->prev = new_node;
	new_node->next = next_node;
	if(new_node->prev ! =NULL)
		new_node->prev->next = new_node;
	else
		(*head_ref) = new_node;
}
void printList(struct Node* node)
{
	struct Node* last;
	cout <<"\n forward traversal \n";
	while(node ! =NULL) {
		cout <<""<< node->data;
		last = node;
		node = node->next;
	}

	cout <<"\n reverse traversal \n";
	while(last ! =NULL) {
		cout <<""<< last->data; last = last->prev; }}int main(a)
{
	struct Node* head = NULL;
	push(&head, 7);

	push(&head, 1);

	push(&head, 4);
	insertBefore(&head, head->next, 8);

	cout <<"The DLL created is:";
	printList(head);

	getchar(a);return 0;
}
Copy the code

Output:

The DLL created is: forward traversal9 1 5 7 6Reverse traversal6 7 5 1 9
Copy the code