Doubly Linked List data structure

Doubly linked list is the list that most programming languages uses in their libraries (like, java lists, c++ lists…etc). The problem with linked lists is that we can’t move backward from any respective node. To overcome this problem Doubly Linked Lists (DLL) comes into the picture.

Unlike nodes in linked lists here Node has two additional pointers called previous and next. The node structure is as shown below.

// Node structure in DLL
struct Node
{
    // Data object
    int data;
    // Next & Prev node addresses
    struct Node *prev;
    struct Node *next;
}

Similar to all other data structures Doubly Linked Lists also needs to support basic operations like Insert, Delete and Find. Let’s discuss these operations in detail.

Operations in DLL are almost similar to these operations in Linked Lists. Let’s check how to represent doubly-linked lists.

Doubly linked list with 4 nodes.

Insert

Insert a node in DLL is as same as inserting in Linked List. To insert a new node in DLL at a given position, We need to take a current node with the head’s position then move the node until we reach the position where we need to install a new node. For example assume we wanted to install a node with data “40” at 2nd position in the above list example. Let’s see below the pictorial representation of this use case.

NewNode 40 is linked before current’s next node.
Established final link to form DLL with 40 in 2nd position.
// Code to delete a value from DLL.
// Here head, tail are class variables.
// newNode is a class member to create a node.
int insert_at(int val, int pos)
{
	struct Node *tmpNode = newNode(val);
	struct Node *curr = head;
	int index = 0;
	if(empty() && pos == index)
	{
		head = tail = tmpNode;
		return ;
	}
	while(curr != NULL)
	{
		index++;
		if(index == pos)
			break;
		curr = curr->next;
	}
	if(index == pos)
	{
		// Insert node at given pos.
		tmpNode->next = curr->next;
		curr->next->prev = tmpNode;
		tmpNode->prev = curr;
		curr->next = tmpNode;
	}
}

Above is the code to insert a node in a DLL at give position, which takes O(n) complexity. Whereas insertion at the end and start takes only O(1) time in Doubly linked list.

Delete

Deleting a node at a given position in DLL is also similar to deleting one in Linked List. Whereas deleting node at the start and end position of the DLL is constant time operation. The below picture depicts how delete operation works in the Doubly linked list.

De-coupling node 40 from DLL.
Remove and free node 40.

The code for this operation is as shown below.

// Code to delete a value from DLL.
// Here head, tail are class variables.
int delete_at(int val) {
	struct Node *curr = head;
	int index = -1;
	if(head == tail)
	{
		if(head->data == val) {
			head = tail = NULL;
			free(curr);
			return 0;
		}
		return index;
	}
	while(curr->next != NULL)
	{
		index++;
		curr = curr->next;
		if(curr->data == val)
		{
			curr->prev->next = curr->next;
			curr->next->prev = curr->prev;
			curr->next = NULL;
			curr->prev = NULL;
			free(curr);
			return index;
		}
	}
	if(curr != NULL)
		return -1;
}

Complexity for this deletion code is O(n). In contrast complexity to delete at start and end positions is constant.

Find

Consequently find operation works similar to how to find operation works in Linked List. A current node linearly searches for the value that needs to be found. Below is the code to show how to find works.

// code to find a value in DLL.
// head is a class variable here.
struct Node *find(int value)
{
	struct Node *curr = head;
	while(curr->next != NULL)
	{
		if(curr->data == value)
			return curr;
	}
	return NULL;
}

Finally, the complexity of find operation in a DLL is O(n).

Above are a few of the operations supported by Doubly Linked Lists. Hence we are concluding DLL here with this. If you found any errors or improvements please help readers to understand by commenting below. Cheers!.

Advertisements