[go: up one dir, main page]
Scribd
Upload
5 views9 pages

Doubly Linked List

A doubly linked list is a data structure where each node contains two pointers, allowing traversal in both directions. It supports various operations such as insertion and deletion at different positions. While it offers advantages like bidirectional traversal and easier reversal, it also requires more memory and time for operations compared to singly linked lists.

Uploaded by

yathavi05052007
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
5 views9 pages

Doubly Linked List

A doubly linked list is a data structure where each node contains two pointers, allowing traversal in both directions. It supports various operations such as insertion and deletion at different positions. While it offers advantages like bidirectional traversal and easier reversal, it also requires more memory and time for operations compared to singly linked lists.

Uploaded by

yathavi05052007
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 9

DOUBLY LINKED

LIST
Doubly linked lists
1. In doubly linked list each node contains two
pointers.
2. Which points has a reference to both the next
point and pervious point of node in list.
3. A doubly linked list is a two-way list because one
can move in either from left to right or from right to
left .
Node data
• Each node contains data and two links (or
pointers) to the next and previous nodes
in the list.
• lnfo : the user's data.
• Prev. Next : the address of next and previous
node in list I.
Operations in doubly linked list

1) Create list.
2) Insert element at beginning in list.
3) Insert element at end in list.
4) Insert element at any place in list.
5) Delete element from the beginning of
list.
6) Delete element from the end of list.
7) Delete element from any place from list.
Create doubly linked list
•A doubly linked list is a type of linked list in which each node
contains a pointer to both the next node and the previous node. This
allows traversal in both forward and backward directions. Each node
in a doubly linked list stores data, a pointer to the next node, and a
pointer to the previous node.
Example
Input: Create Doubly Linked List with 1 2 3 4
Output: head = [1] <-> [2] <-> [3] <-> [4] <-> NULL
Explanation: The doubly linked list is created with nodes containing
values 1, 2, 3, and 4.
Input: Create Doubly Linked List with 10 20 30
Output: head = [10] <-> [20] <-> [30] <-> NULL
Explanation: The doubly linked list is created with nodes containing
INSERTIONS

• Create a new node, say new_node


with its previous pointer as NULL.
• Set the next pointer to the current
head, new_node->next = head.
• Check if the linked list is not empty
then we update the previous pointer
of the current head to the new node,
head->prev = new_node.
Delete an element at any place doubly linked list

• Traverse to the node at the specified position, say


curr.
• If the position is valid, adjust the pointers to skip
the node to be deleted. ...
• Free the memory allocated for the deleted node.
PROS AND CONS
PROS CONS
We can traverse in both • It requires more space per space
directions i.e. from starting to end per node because one extra field is
and as well as from end to starting. required for pointer to previous
node.

It is easy to reverse the linked •Insertion and deletion take more
list. time than linear linked list
because more pointer operations
are required than linear linked
list.
 If we are at a node, then we • Doubly linked lists use more
can go to any node. But in memory than singly linked lists
linear linked list, it is not because each element has an
possible to reach the previous additional previous pointer.
node.

You might also like