Practice
Resources
Contests
Online IDE
New
Free Mock
Events New Scaler
Practice
Improve your coding skills with our resources
Contests
Compete in popular contests with top coders
logo
Events
Attend free live masterclass hosted by top tech professionals
New
Scaler
Explore Offerings by SCALER

Linked Lists

Last Updated: Nov 17, 2023
Go to Problems
locked
Linked Lists
info
Complete all the problems in this Topic to unlock a badge
Completed
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!
Contents

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.

Video Courses
By

View All Courses
Excel at your interview with Masterclasses Know More
Certificate included
What will you Learn?
Free Mock Assessment
Fill up the details for personalised experience.
Phone Number *
OTP will be sent to this number for verification
+1 *
+1
Change Number
Graduation Year *
Graduation Year *
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
2028
2029
*Enter the expected year of graduation if you're student
Current Employer
Company Name
College you graduated from
College/University Name
Job Title
Job Title
Engineering Leadership
Software Development Engineer (Backend)
Software Development Engineer (Frontend)
Software Development Engineer (Full Stack)
Data Scientist
Android Engineer
iOS Engineer
Devops Engineer
Support Engineer
Research Engineer
Engineering Intern
QA Engineer
Co-founder
SDET
Product Manager
Product Designer
Backend Architect
Program Manager
Release Engineer
Security Leadership
Database Administrator
Data Analyst
Data Engineer
Non Coder
Other
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