Insert at End of Doubly Linked List in DSA Python - Build from Scratch

Insert at End of Doubly Linked List

📖 Scenario: You are managing a playlist of songs. Each song is linked to the previous and next song, allowing easy navigation back and forth. You want to add a new song to the end of the playlist.

🎯 Goal: Build a doubly linked list and write code to insert a new node at the end. Finally, print the playlist from start to end.

📋 What You'll Learn

Create a Node class with data, prev, and next attributes

Create a doubly linked list with three nodes containing data 10, 20, and 30

Create a variable new_data with value 40

Write a function insert_at_end(head, data) that inserts a new node with data at the end of the list

Print the list from head to end showing node data separated by -> and ending with null

💡 Why This Matters

🌍 Real World

Doubly linked lists are used in music players, web browsers, and undo-redo features where you need to move forward and backward easily.

💼 Career

Understanding linked lists is fundamental for software developers, especially for roles involving data structure optimization and system design.

1

Create the initial doubly linked list

Create a Node class with data, prev, and next attributes. Then create three nodes with data 10, 20, and 30 linked as a doubly linked list. Assign the first node to a variable called head.

DSA Python

# Your code here

Hint

Define the Node class first. Then create three nodes and link them using next and prev pointers.

2

Create the new data to insert

Create a variable called new_data and set it to 40.

DSA Python

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

node1 = Node(10)
node2 = Node(20)
node3 = Node(30)

node1.next = node2
node2.prev = node1
node2.next = node3
node3.prev = node2

head = node1

# Your code here

Hint

Just create a variable new_data and assign it the value 40.

3

Write the function to insert at the end

Write a function called insert_at_end(head, data) that creates a new node with data and inserts it at the end of the doubly linked list starting at head. Return the head of the updated list.

DSA Python

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

node1 = Node(10)
node2 = Node(20)
node3 = Node(30)

node1.next = node2
node2.prev = node1
node2.next = node3
node3.prev = node2

head = node1

new_data = 40

def insert_at_end(head, data):
    # Your code here

Hint

Start from head and move to the last node. Then link the new node after it.

4

Print the updated doubly linked list

Call insert_at_end(head, new_data) and assign the result back to head. Then print the list from head to end. Print each node's data followed by -> , ending with null.

DSA Python

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

node1 = Node(10)
node2 = Node(20)
node3 = Node(30)

node1.next = node2
node2.prev = node1
node2.next = node3
node3.prev = node2

head = node1

new_data = 40

def insert_at_end(head, data):
    new_node = Node(data)
    if head is None:
        return new_node
    current = head
    while current.next is not None:
        current = current.next
    current.next = new_node
    new_node.prev = current
    return head

head = insert_at_end(head, new_data)

# Your code here

Hint

Traverse from head to the end, printing each node's data followed by -> . End with null.

Practice

1. What is the main purpose of inserting a node at the end of a doubly linked list?

easy

A. To reverse the list

B. To add a new element after the last node

C. To remove the first node

D. To find the middle node

Solution

1. Step 1: Understand the structure of a doubly linked list

   A doubly linked list has nodes connected forward and backward, allowing traversal in both directions.

2. Step 2: Purpose of insertion at the end

   Inserting at the end means adding a new node after the current last node, updating pointers accordingly.

3. Final Answer:

   To add a new element after the last node -> Option B

4. Quick Check:

   Insert at end = Add after last node [OK]

Hint: Insert at end means add after last node [OK]

Common Mistakes:

• Confusing insertion at end with deletion
• Thinking insertion reverses the list
• Assuming insertion happens at the start

2. Which of the following is the correct way to update the pointers when inserting a new node at the end of a doubly linked list in Python?

easy

A. new_node.prev = null; new_node.next = head; head.prev = new_node; head = new_node

B. new_node.next = head; new_node.prev = null; head.prev = new_node; head = new_node

C. new_node.next = null; new_node.prev = tail; tail.next = new_node; tail = new_node

D. new_node.prev = tail; new_node.next = tail; tail.next = new_node; tail = new_node

Solution

1. Step 1: Identify pointer updates for insertion at end

   The new node's next pointer should be null because it will be the last node. Its prev pointer should point to the current tail.

2. Step 2: Update the tail's next pointer and move tail

   The current tail's next pointer should point to the new node, then update tail to the new node.

3. Final Answer:

   new_node.next = null; new_node.prev = tail; tail.next = new_node; tail = new_node -> Option C

4. Quick Check:

   New node next = null, prev = tail [OK]

Hint: New node next is null, prev points to tail [OK]

Common Mistakes:

• Setting new_node.next to head instead of null
• Not updating tail pointer after insertion
• Confusing prev and next pointers

3. What will be the printed output of the doubly linked list after executing the following code?

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def insert_end(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node

    def print_list(self):
        current = self.head
        result = []
        while current:
            result.append(current.data)
            current = current.next
        print(' -> '.join(map(str, result)) + ' -> null')

dll = DoublyLinkedList()
dll.insert_end(10)
dll.insert_end(20)
dll.insert_end(30)
dll.print_list()

medium

A. 10 -> 20 -> 30 -> null

B. 30 -> 20 -> 10 -> null

C. 10 -> 20 -> null

D. null

Solution

1. Step 1: Insert nodes 10, 20, 30 at the end

   Each insert_end call adds a new node at the tail, linking nodes in order: 10, then 20, then 30.

2. Step 2: Print the list from head to tail

   print_list traverses from head, collecting data: 10, 20, 30, then prints with arrows and 'null' at end.

3. Final Answer:

   10 -> 20 -> 30 -> null -> Option A

4. Quick Check:

   Insert end adds at tail, print from head [OK]

Hint: Insert end adds at tail; print from head shows order [OK]

Common Mistakes:

• Confusing print order as reversed
• Missing last node in output
• Printing null instead of 'null'

4. Identify the error in the following code snippet that inserts a node at the end of a doubly linked list:

def insert_end(self, data):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node
    else:
        self.tail.next = new_node
        new_node.prev = self.tail
        self.tail = new_node

medium

A. new_node.next should point to head

B. new_node.prev should be null when list is empty

C. self.head should be updated after insertion at end

D. Missing update of tail when list is empty

Solution

1. Step 1: Check tail update when list is empty

   When the list is empty, only head is set to new_node, but tail is not updated, so tail remains null.

2. Step 2: Correct tail assignment

   Tail must also be set to new_node when list is empty to keep tail pointer valid.

3. Final Answer:

   Missing update of tail when list is empty -> Option D

4. Quick Check:

   Empty list needs tail = new_node too [OK]

Hint: Update tail when list is empty [OK]

Common Mistakes:

• Not updating tail on empty list
• Setting new_node.next incorrectly
• Confusing head and tail updates

5. Given a doubly linked list with nodes containing values [5, 15, 25], you want to insert a new node with value 35 at the end. After insertion, what will be the correct sequence of node values when traversing from head to tail and tail to head respectively?

hard

A. 5 -> 15 -> 25 -> 35 -> null and 35 -> 25 -> 15 -> 5 -> null

B. 35 -> 5 -> 15 -> 25 -> null and 25 -> 15 -> 5 -> 35 -> null

C. 5 -> 15 -> 25 -> null and 35 -> null

D. 5 -> 15 -> 25 -> 35 -> null and 5 -> 15 -> 25 -> 35 -> null

Solution

1. Step 1: Insert 35 at the end of the list

   The new node with value 35 is added after the current tail (25), updating pointers accordingly.

2. Step 2: Traverse from head to tail and tail to head

   From head: 5 -> 15 -> 25 -> 35 -> null; From tail: 35 -> 25 -> 15 -> 5 -> null.

3. Final Answer:

   5 -> 15 -> 25 -> 35 -> null and 35 -> 25 -> 15 -> 5 -> null -> Option A

4. Quick Check:

   Forward and backward traversal show correct order [OK]

Hint: Forward order adds new node at end; backward reverses [OK]

Common Mistakes:

• Mixing forward and backward traversal order
• Forgetting to update prev pointer of new node
• Assuming new node is added at head