469,612 Members | 1,674 Online

# Doubly Linked List - An Overview

Data structures are a method of efficiently storing and retrieving data. Depending on whether data is stored sequentially or not, data structures can be linear or nonlinear. Arrays, stacks, queues, and linked lists are examples of linear data structures.

Trees and graphs are examples of nonlinear structures. Each data structure has information on the sort of data it stores, the relationships between data, and the operations that can be performed on it. Homogeneous and Non-Homogeneous data structures can be classified based on whether the data in a repository is of the same type or not. The way data structures are put together can also influence how they are classified.

Let's have a look at what a Doubly Linked List is before we get into the benefits. It's a linked data structure made up of nodes, which are a collection of sequentially connected records. There are three fields in each node: two link fields and one data field. Classification.

A linked list is a linear data structure with a collection of nodes that are connected to one another. It resembles a chain structure. Each node has a reference to the next node as well as the sort of data it stores. Here are several reasons why a linked list is preferable over arrays.

A linked list is dynamic, which means it can expand and contract at any time. There will be no memory waste as a result of this.

It is easy to add and remove nodes from a linked list. Arrays require node shifting for insertion and deletion.

Linked lists can also be used to implement other linear data structures such as stacks and queues.
It's also possible to convert a linked list to other non-linear data structures like trees.

What Is a Doubly Linked List?

It is possible to go only in the direction of links in a single linked list, hence we are limited to traversing the linked list in just one direction.

Each node in a linked list offers information about the next node in the list. It has no idea where the previous node is stored in memory.

If we are at the 15th node in the list, we must traverse the list all the way back to the first node to get to the 14th node.

To overcome this, we can keep not just the address of the next node, but also the address of the previous node in each node. The address of the linked list's previous node. In data structures, this arrangement is known as a 'Doubly linked list.'

The list can be walked through either forward or backward. In a doubly-linked list, each node must have two link fields instead of one.

Insertion:

Inserting a node in the front: Making the head point to the new node and disconnecting the link with the prior node is the process of inserting a new node. The prior pointer of the new node must likewise be set to NULL, and the previous pointer of the previous new node must be set to a new node.
It's also possible to convert a linked list to other non-linear data structures like trees.

Inserting a node at the end: We must do the following when inserting a node at the end of the linked list:

Set New Node's next reference to NULL.
Make the New Node's prior pointer point to the previous last node.
Change the preceding node's next pointer to New Node.

Inserting a Node in the Middle:
This is more involved than the previous insertion process, and it must be implemented with care. This feature is frequently used in the real world.

Deletion:
There are three sorts of deletion: deletion from the beginning, deletion in the middle, and deletion at the conclusion. There is a common algorithm for all of these processes. The implementation, of course, is dependent on the language's grammar, but the algorithm remains the same. When deleting a node from a Doubly Linked list, we must first reposition the pointer referring to that node so that the preceding and following nodes have no relationship to the node being deleted. To delete a node in a doubly-linked list, follow the instructions below.

Searching:

In a doubly-linked list, searching is comparable to searching in a singly-linked list. We must go through the entire list and look for the target value. If the value of a node equals the target node, we simply display it and return 1 to indicate that the value is present in the linked list; otherwise, we return 0 to indicate that the target node is not present.

Reverse DLL:
A doubly linked list becomes particularly handy for practical uses as a result of this process. We've already utilized two pointers in a DLL node to make it easy to reach the previous node. When compared to a singly linked list, reversing a doubly-linked list is quite simple. All we have to do now is swap the head and tail points, as well as the two pointers for the complete list.
1 Week Ago #1
0 4999