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

Delete from End of Doubly Linked List

📖 Scenario: You are managing a playlist of songs using a doubly linked list. Each song is a node with a title. You want to remove the last song from the playlist.

🎯 Goal: Build a doubly linked list with 3 songs, then delete the last song from the list, and finally print the updated playlist from start to end.

📋 What You'll Learn

Create a doubly linked list with exactly 3 nodes containing song titles: 'Song1', 'Song2', 'Song3'

Create a variable called head that points to the first node

Create a function called delete_from_end that deletes the last node from the doubly linked list

Print the playlist from start to end after deletion in the format: Song1 -> Song2 -> null

💡 Why This Matters

🌍 Real World

Doubly linked lists are used in music players, browsers, and other apps to move forward and backward through items efficiently.

💼 Career

Understanding linked lists and how to modify them is a key skill for software developers working with data structures and memory management.

1

Create the doubly linked list with 3 songs

Define a class called Node with attributes data, prev, and next. Then create 3 nodes with data 'Song1', 'Song2', and 'Song3'. Link them to form a doubly linked list. Finally, create a variable called head that points to the first node.

DSA Python

# Define Node class and create 3 linked nodes
# Your code here

Hint

Remember to link each node's next and prev pointers correctly to form the doubly linked list.

2

Create a helper variable to track the current node

Create a variable called current and set it equal to head. This will help us traverse the list.

DSA Python

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

node1 = Node('Song1')
node2 = Node('Song2')
node3 = Node('Song3')

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

head = node1

# Create a variable current and set it to head
# Your code here

Hint

This variable will help us move through the list to find the last node.

3

Write the function to delete the last node

Define a function called delete_from_end that takes head as input. Inside, use a variable current to traverse to the last node. Then update the second last node's next to None to remove the last node. Return the updated head.

DSA Python

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

node1 = Node('Song1')
node2 = Node('Song2')
node3 = Node('Song3')

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

head = node1

current = head

def delete_from_end(head):
    # Your code here

Hint

Traverse to the last node, then disconnect it by setting the previous node's next to None.

4

Print the playlist after deleting the last song

Call delete_from_end(head) and update head with the returned value. Then use a while loop with a variable current starting at head to print each song's data followed by ' -> '. After the loop, print 'null'.

DSA Python

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

node1 = Node('Song1')
node2 = Node('Song2')
node3 = Node('Song3')

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

head = node1

current = head

def delete_from_end(head):
    if head is None:
        return None
    current = head
    while current.next is not None:
        current = current.next
    if current.prev is not None:
        current.prev.next = None
    else:
        head = None
    return head

# Delete last node and print playlist
# Your code here

Hint

After deleting the last node, print all remaining nodes followed by ' -> ', then print 'null'.

Practice

1. What happens when you delete a node from the end of a doubly linked list that has multiple nodes?

easy

A. The last node is removed and the second last node becomes the new tail.

B. The first node is removed and the second node becomes the new head.

C. All nodes are deleted and the list becomes empty.

D. The middle node is removed and the list remains unchanged at the ends.

Solution

1. Step 1: Identify the last node and update pointers

   In a doubly linked list, the last node is the tail node which has its next pointer as null. Deleting the last node means updating the tail pointer to the previous node and setting its next pointer to null. The second last node becomes the new tail.

2. Final Answer:

   The last node is removed and the second last node becomes the new tail. -> Option A

3. Quick Check:

   Delete end node = tail moves back [OK]

Hint: Last node removed, tail moves to previous node [OK]

Common Mistakes:

• Removing the head instead of the tail
• Not updating the tail pointer
• Leaving the next pointer of new tail non-null

2. Which of the following is the correct syntax to delete the last node in a doubly linked list in Python?

easy

A. head = head.prev; head.next = None

B. tail = tail.next; tail.prev = None

C. head = head.next; head.prev = None

D. tail = tail.prev; tail.next = None

Solution

1. Step 1: Move tail pointer and update next

   To delete the last node, move tail to tail.prev (second last node), then set tail.next to None to mark the end of the list.

2. Final Answer:

   tail = tail.prev; tail.next = None -> Option D

3. Quick Check:

   Correct tail update syntax = tail = tail.prev; tail.next = None [OK]

Hint: Tail moves back, next pointer set to None [OK]

Common Mistakes:

• Moving tail forward instead of backward
• Setting prev pointer instead of next
• Changing head pointer instead of tail

3. What will be the output after deleting the last node from the doubly linked list shown below?

Initial list: 10 <-> 20 <-> 30 <-> 40 <-> None
Operation: Delete from end

What is the resulting list?

medium

A. 10 <-> 20 <-> 30 <-> 40 <-> None

B. 10 <-> 20 <-> 30 <-> None

C. 20 <-> 30 <-> 40 <-> None

D. 10 <-> 20 <-> None

Solution

1. Step 1: Identify last node and update

   The last node is 40, which is removed by setting node 30's next pointer to None, making it the new tail. Result: 10 <-> 20 <-> 30 <-> None.

2. Final Answer:

   10 <-> 20 <-> 30 <-> None -> Option B

3. Quick Check:

   Last node 40 removed, tail is 30 [OK]

Hint: Remove last node, update previous node's next to None [OK]

Common Mistakes:

• Not updating the next pointer of new tail
• Removing the wrong node (head or middle)
• Leaving dangling pointers causing errors

4. Consider the following code snippet to delete the last node from a doubly linked list:

if tail is None:
    print('List is empty')
else:
    tail = tail.prev
    tail.next = None

What error can occur when this code runs on a list with only one node?

medium

A. AttributeError because tail.prev is None and tail.next is accessed

B. No error, code works fine for single node list

C. SyntaxError due to missing colon

D. IndexError because tail is out of range

Solution

1. Step 1: Trace execution for single node

   For one node, tail.prev is None, so tail = None, then tail.next = None accesses None.next causing AttributeError.

2. Final Answer:

   AttributeError because tail.prev is None and tail.next is accessed -> Option A

3. Quick Check:

   Single node delete needs extra check [OK]

Hint: Check if tail.prev is None before setting tail.next [OK]

Common Mistakes:

• Not handling single node list case
• Assuming tail.prev always exists
• Ignoring NoneType attribute errors

5. You have a doubly linked list with nodes: 5 <-> 15 <-> 25 <-> 35 <-> 45 <-> None. You delete the last node twice in a row. What will be the final list?

hard

A. 5 <-> 15 <-> 25 <-> 35 <-> 45 <-> None

B. 5 <-> 15 <-> 25 <-> 35 <-> None

C. 5 <-> 15 <-> 25 <-> None

D. 15 <-> 25 <-> 35 <-> None

Solution

1. Step 1: Perform two deletions

   Initial: 5 <-> 15 <-> 25 <-> 35 <-> 45. First delete removes 45 (tail=35). Second delete removes 35 (tail=25). Final: 5 <-> 15 <-> 25 <-> None.

2. Final Answer:

   5 <-> 15 <-> 25 <-> None -> Option C

3. Quick Check:

   Two deletes remove last two nodes [OK]

Hint: Each delete removes one tail node [OK]

Common Mistakes:

• Deleting only one node instead of two
• Not updating tail pointer after each delete
• Confusing head and tail nodes