Practice
Resources
Contests
Online IDE
New
Free Mock
Scaler
Practice
Improve your coding skills with our resources
Contests
Compete in popular contests with top coders
Scaler
Explore Offerings by SCALER

Linked Lists

Go to Problems

Level 1

Jump to Level 2

Level 2

Jump to Level 3

Level 3

Jump to Level 4

Level 4

Jump to Level 5

Level 5

Jump to Level 6

Level 6

Jump to Level 7

Level 7

Jump to Level 8

Level 8

Be a Code Ninja!

Doubly linked list

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.

Syntax:

Struct node{

                 int data;

                 struct node *next, *prev;

                 *head;

 

Where struct keyword refers to a structure, node is the name of the structure, data is the information field which contains only integer values, *next is the pointer of type structure which holds the address of the next node in the sequential list, and *prev is the pointer of the type structure and hold the address of the previous node in the sequential list.

Doubly Linked List

Working of a Doubly linked list:

  1. Insertion
    1. Insert after
    2. Insert before
    3. Insert at the end
    4. Insert at the first position, respectively.
  2. Deletion
  3. Display
  4. Searching
  1. 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.

Insert at first position

doubly linked list insert operation

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.

insertion at the end

linked list insert end operation

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.

insert before operation doubly linked list

insert before

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.

insert after doubly linked list

insert after

  1. Deletion:
  • If the node to be deleted is the head node, then change the head pointer from the first node to second and make the prev pointer of 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.
  1. 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 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 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 NULL value.
  1. Searching: When one wants to search for a node, one keeps traversing the list till 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.

Serious about Learning Programming ?

Learn this and a lot more with Scaler Academy's industry vetted curriculum which covers Data Structures & Algorithms in depth.

Linked Lists Problems

List sort
Problem Score Companies Time Status
Sort Binary Linked List 200 33:16
Partition List 275
49:36
Insertion Sort List 300
49:25
Sort List 350 59:47
Pointer move
Problem Score Companies Time Status
K reverse linked list 200 60:30
Even Reverse 200 44:39
Swap List Nodes in pairs 350 33:34
Rotate List 350 33:58
List trick
Problem Score Companies Time Status
Kth Node From Middle 200 29:46
Reverse Alternate K Nodes 300 52:25
Reverse Link List II 450 57:24
Reorder List 600 57:10
List math
Problem Score Companies Time Status
Add Two Numbers as Lists 250 43:07
List Cycle 600 39:15
Free Mock Assessment
Fill up the details for personalised experience.
All fields are mandatory
Current Employer *
Enter company name *
Graduation Year *
Select an option *
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
Phone Number *
OTP will be sent to this number for verification
+33 *
+33
Change Number
Phone Number *
OTP will be sent to this number for verification
+33 *
+33
Change Number
Graduation Year *
Graduation Year *
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
*Enter the expected year of graduation if you're student
Current Employer *
Company Name *
Please verify your phone number
Edit
Resend OTP
By clicking on Start Test, I agree to be contacted by Scaler in the future.
Already have an account? Log in
Free Mock Assessment
Instructions from Interviewbit
Start Test