Doubly Linked List Tutorial

Doubly Linked List Intro

A Doubly Linked List is a type of linked list in which each node contains three components:

Data: The actual value or information stored in the node.
Next: A pointer or reference to the next node in the sequence.
Previous: A pointer or reference to the previous node in the sequence.

Key characteristics of a Doubly Linked List:

Bidirectional traversal: Unlike a singly linked list, a doubly linked list can be traversed in both forward and backward directions.
Each node has two links: This allows for more flexibility in list manipulation but requires more memory per node.
The first node's previous pointer and the last node's next pointer both point to null.
Easier deletion: Deletion of a node is more efficient as we have direct access to the previous node.
More complex implementation: Due to the additional previous pointer, the implementation is slightly more complex than a singly linked list.

Advantages of Doubly Linked List:

Can be traversed in both directions
Deletion of a node is more efficient
Can quickly insert a new node before a given node

Disadvantages:

Requires more memory due to the extra previous pointer
Operations are slightly more complex due to handling two pointers

Real-world applications of Doubly Linked List:

Implementation of navigation systems (forward/backward navigation)
Music players with previous and next song functionality
Undo/Redo operations in various applications
Browser cache for storing recently visited pages
Implementation of MRU (Most Recently Used) cache

Doubly Linked List Key Operations

Key operations on a Doubly Linked List include:

Insertion (at the beginning, end, and at a specific position)
Deletion (from the beginning, end, and at a specific position)
Forward traversal
Backward traversal
Searching for an element

This is General Representation Of Doubly Linked List. Each node has two links: This allows for more flexibility in list manipulation but requires more memory per node.

The first node's previous pointer and the last node's next pointer both point to null.

java

python

xxxxxxxxxx
 
Define Node Structure:    Node:        - data: Integer        - next: Node        - prev: Node

Insertion In DLL: Add a node at the beginning, end, or a specific position.

First we write the Pseudocode for Doubly Linked List Operations

Add a node at the beginning.
Adding a node at the end.
Adding a node at a specific position.

Node Structure

Define Node Structure:
    Node:
        - data: Integer
        - next: Node
        - prev: Node

Initialize Head and Tail Pointers

Initialize:
    - head = null
    - tail = null

Add Node at Last

Pseudocode

java

xxxxxxxxxx
 
Function addNodeAtLast(data: Integer):    Create newNode with given data    If head is null:        head = newNode        tail = newNode        Return    Else:        Set tail.next to newNode        Set newNode.prev to tail        Set tail to newNode

Add Node at First

Pseudocode

java

xxxxxxxxxx
 
Function addNodeAtFirst(data: Integer):    Create newNode with given data    If head is null:        head = newNode        tail = newNode        Return    Else:        Set newNode.next to head        Set head.prev to newNode        Set head to newNode

Insert Node at Specific Index

Pseudocode

java

xxxxxxxxxx
 
Function insertAt(index: Integer, data: Integer):    If index < 0:        Print "Invalid index"        Return    Create newNode with given data    Set current to head    Initialize counter j to 0    While j < index - 2:        If current is null:            Print "Invalid index"            Return        Set current to current.next        Increment j    If current.next is not null:        Set newNode.next to current.next        Set current.next.prev to newNode    Set newNode.prev to current    Set current.next to newNode

Print Doubly Linked List Forward

Pseudocode

java

xxxxxxxxxx
 
Function printDLLForward(head: Node):    Set current to head    While current is not null:        Print current.data followed by "->"        Set current to current.next    Print "null"

Print Doubly Linked List Reverse

Pseudocode

java

xxxxxxxxxx
 
Function printDLLReverse(tail: Node):    Set current to tail    While current is not null:        Print current.data followed by "->"        Set current to current.prev    Print "null"

Code for Insertions In Doubly Linked List

Code for Insertions In Doubly Linked List

Add a node at the beginning.
Adding a node at the end.
Adding a node at a specific position.

Insertions Operations In Doubly Linked List

java

python

​x
 
package ds.linked_list.doubly_linked_list;​public class OperationsOnDLL{    private static DLLNode dllNodeHead = null;    private static DLLNode dllNodeTail = null;​    public static class DLLNode {        int data;        DLLNode next;        DLLNode prev;​        DLLNode(int data) {            this.data = data;            this.next = null;            this.prev = null;        }    }​    public static void addNodeAtLast(int data)    {        DLLNode newNode = new DLLNode(data);        if(dllNodeHead == null)        {            dllNodeHead = newNode;            dllNodeTail = newNode;            return;        }        dllNodeTail.next = newNode;        newNode.prev = dllNodeTail;        dllNodeTail = newNode;    }​    public static void addNodeAtFirst(int data)    {        DLLNode newNode = new DLLNode(data);        if(dllNodeHead == null)        {            dllNodeHead = newNode;            dllNodeTail = newNode;            return;        }        newNode.next = dllNodeHead;        dllNodeHead.prev = newNode;        dllNodeHead = newNode;    }​    public static void insertAt(int index, int data)    {        if(index < 0)        {            System.out.println("Invalid index");            return;        }        DLLNode newNode = new DLLNode(data);        DLLNode curr = dllNodeHead;        int j = 0;        while( j < (index-2) )        {            if(curr == null) {                System.out.println("Invalid index");                return;            }            curr = curr.next;            j++;        }        if(curr.next != null) {            newNode.next = curr.next;            curr.next.prev = newNode;        }        newNode.prev = curr;        curr.next = newNode;    }​    public static void printDLLForward(DLLNode dllNodeHead)    {        DLLNode current = dllNodeHead;        while(current != null)        {            System.out.print(current.data + "->");            current = current.next;        }        System.out.print("null");    }​    public static void printDLLReverse(DLLNode tail)    {        DLLNode prev = tail;        while(prev != null)        {            System.out.print(prev.data + "->");            prev = prev.prev;        }        System.out.print("null");    }​    public static void main(String[] args)    {        OperationsOnDLL.addNodeAtLast(10);        OperationsOnDLL.addNodeAtLast(20);        OperationsOnDLL.addNodeAtFirst(4);        OperationsOnDLL.addNodeAtFirst(12);        OperationsOnDLL.addNodeAtFirst(5);        OperationsOnDLL.addNodeAtFirst(14);        OperationsOnDLL.insertAt(4, 200);​        System.out.println("Forward Direction");        OperationsOnDLL.printDLLForward(dllNodeHead);​        System.out.println();        System.out.println("Reverse Direction");        OperationsOnDLL.printDLLReverse(dllNodeTail);    }}

Code Output

Forward Direction
14->5->12->200->4->10->20->null
Reverse Direction
20->10->4->200->12->5->14->null

Doubly Linked List Intro

A Doubly Linked List is a type of linked list in which each node contains three components:

Key characteristics of a Doubly Linked List:

Advantages of Doubly Linked List:

Disadvantages:

Real-world applications of Doubly Linked List:

Insertion In DLL: Add a node at the beginning, end, or a specific position.

Code for Insertions In Doubly Linked List

Java Tutorial

Python Tutorial