Intro to Doubly Linked List in C++

Tech Bro
Tech Bro
Sep 7, 2020 · 5 min read

A doubly linked list is a data structure where a set of sequential links of records called nodes exist. Unlike the singly linked list, a node of a doubly-linked list consists of three fields: two link fields and one information field. Two link fields provide information about the address of previous nodes and the next nodes in the sequence and one data field.

The link fields are also known as “previous” and “next” pointers and store the addresses of the previous and next nodes in the list. And the previous pointer of the very first node, as well as the next pointer of the last node points to a Null value or called a sentinel node.

Structure:

Struct node{                 int data;                 struct node *next, *prev;
}
Image for post

Working of a Doubly linked list:

  1. Insertion
  2. Deletion
  3. Display
  4. Searching

Insertion

Insert at the first position: When a new node is inserted at the first position of the doubly linked list, it becomes the new head. Start by creating the node and inserting the data value in it. Next change the pointer references of the old and new head node. The prev pointer of the new node should be pointed to a NULL value, whereas the next pointer should be pointed towards the old head. Similarly, the prev pointers of the old head which was set to NULL should be pointing to the new head.

Image for post
Image for post

Insert at the end: When a new node is inserted at the last position of the doubly linked list, it requires a couple of changes as the previous last node now becomes the second last node. The next pointer of the previous last node should now be changed from null value and point towards the newly inserted node. The next of the newly inserted last node should now point towards null value and the prev pointer of this very node points to the older last node which is now the second last node.

Image for post
Image for post

Insert before: Suppose we have a node called A and the next node to A is C. Now we have to insert a node before C. When a new node is created which is to be placed before C requires the following changes. First the next pointer of this new node will point to node C and the prev pointer of this new node will point to A. Whereas the next pointer of node A will point to the newly inserted node and the previous pointer of node C will now point to the node inserted before C.

Image for post
Image for post

Insert after: Suppose we have a node called A and the next note to A is C. Now to insert a node after node we follow the steps similar to when we insert a node before any particular node. If a node B is to be placed after node A then the following changes need to be encountered. First we start with creating a new node and this node needs to be inserted after node A so the previous pointer of this node B will point to node A and the next of this node will point to node C. Now the next pointer of node A will point to node B, and the previous of node C will point to node B.

Image for post
Image for post

Deletion

  • If the node to be deleted is the head node, then change the head pointer from the first node to the second and make the prev pointer of the second node as NULL. Also, make the next and prev pointers of the older first node as NULL and free the node.
  • Else, if the node to be deleted is the last node, then make the prev pointer of the last node as NULL and the next pointer of the older second last node as NULL.
  • But is the node to be deleted suppose is B and lies in between two nodes A and C, then make the next pointer of the node A to point at node C and the prev pointer of node C point to node A. Once this is done, make the next and prev pointers of node B as NULL and free the node.

Display

It calls for printing the values in some order, be it from first to last or last to first.

  • When one wants to print the values in the order first to last, one keeps traversing till the next pointer of a node doesn’t point to the NULL value.
  • And if one wants to print in the last to first manner then, first one traverses till the node whose next pointer doesn’t point to a NULL value and then prints the values in the reverse fashion, till the point where the prev pointer of the node doesn’t point to the NULL value.

Searching

When one wants to search for a node, one keeps traversing the list until the required data value is found. Comparing each node’s data with the data value to be searched and return the index of the item found, is how searching takes place in a doubly-linked list.

The Startup

Medium's largest active publication, followed by +773K people. Follow to join our community.

Tech Bro

Written by

Tech Bro

Technical Details behind all your favorite products.

The Startup

Medium's largest active publication, followed by +773K people. Follow to join our community.

Tech Bro

Written by

Tech Bro

Technical Details behind all your favorite products.

The Startup

Medium's largest active publication, followed by +773K people. Follow to join our community.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store