Doubly Linked List – Create Operation

Creating a Doubly Linked List

Creating a doubly linked list involves adding nodes one by one, where each node holds a value, a pointer to the next node, and a pointer to the previous node. This two-way linkage allows for traversal in both directions.

Just like singly linked lists, doubly linked lists grow dynamically, but offer more flexibility when it comes to insertion and deletion at both ends or in the middle of the list.

Visual Example

We will build a doubly linked list by inserting the following values one by one: [10, 20, 30, 40]

Initial Empty List

Step 1: Insert 10

• Create a new node with value 10.
• Since the list is empty, this node becomes the head.

Step 2: Insert 20

• Create a new node with value 20.
• Set 20.prev to 10 and 10.next to 20.

Step 3: Insert 30

• Create a new node with value 30.
• Set 30.prev to 20 and 20.next to 30.

Step 4: Insert 40

• Create a new node with value 40.
• Set 40.prev to 30 and 30.next to 40.

At this point, the doubly linked list has been created successfully with all nodes properly linked in both forward (next) and backward (prev) directions.

Complete Pseudocode: Create Doubly Linked List by Appending

This pseudocode builds a doubly linked list by appending each new node to the end and updating both prev and next links.

function createDoublyLinkedList():
    head = null
    tail = null

    while input has values:
        value = next input
        node = new DllNode(value)

        if head == null:
            head = node
            tail = node
        else:
            tail.next = node
            node.prev = tail
            tail = node

    return head

Let’s walk through each part of the code to understand what it does.

function createDoublyLinkedList():
    head = null
    tail = null

Explanation: We begin with an empty list. head will point to the first node, and tail will track the end for efficient appending.

---

while input has values:
    value = next input
    node = new DllNode(value)

Explanation: We loop through the input (e.g., [10, 20, 30]) and create a new node for each value.

---

    if head == null:
        head = node
        tail = node

Explanation: For the very first value, both head and tail are set to the new node.

---

    else:
        tail.next = node
        node.prev = tail
        tail = node

Explanation: For subsequent values, we update the current tail.next and the new node's prev, then move tail forward.

---

return head

Explanation: The head node gives us access to the full doubly linked list, which we can now traverse in both directions.

Doubly Linked List Creation Examples

The following examples show how nodes are added one by one to build a doubly linked list dynamically. Each node maintains both prev and next pointers.

Insert Sequence	Final Linked List	Explanation
[10, 20, 30]	null ← 10 ⇄ 20 ⇄ 30 → null	Three nodes are inserted sequentially. Each new node is linked to both the previous and the next node using prev and next pointers.
[5]	null ← 5 → null	Only one node is inserted. Its prev and next pointers are both null, making it both head and tail.
[]	null	No values are provided, so the list is empty and head = null.
[1, 2, 3, 4, 5]	null ← 1 ⇄ 2 ⇄ 3 ⇄ 4 ⇄ 5 → null	Five nodes are added to build a complete doubly linked list. Each node is connected to its neighbors with two-way links.

Time Complexity of Doubly Linked List Create Operation

Creation Case	Time Complexity	Explanation
Creating list by appending with tail pointer	O(n)	Each node is appended in O(1) time using the tail pointer. Creating n nodes takes linear time overall.
Creating list by inserting at head	O(n)	Each node is inserted at the beginning in constant time. Repeating this for n nodes results in O(n) time.
Creating list by traversing to insert at end (no tail)	O(n2)	Each insert at end requires a full traversal (O(n)), done n times. Leads to quadratic time overall.

Space Complexity of Doubly Linked List Create Operation

Creation Case	Space Complexity	Explanation
Creating a list of n nodes	O(n)	Each node requires space for its value, a pointer to the next node, and a pointer to the previous node. Thus, total space grows linearly with the number of nodes.

Key Takeaways

• A Doubly Linked List (DLL) consists of nodes that store data, a next pointer, and a prev pointer.
• Each node is linked in both directions, enabling efficient forward and backward traversal.
• Creating a DLL involves inserting nodes and updating both next and prev references appropriately.
• The head node’s prev is always null, and the tail node’s next is always null.
• Space complexity is O(n) since each of the n nodes stores additional pointers.
• DLLs are more flexible than singly linked lists but use slightly more memory per node due to the extra pointer.