Posted on by Kalkicode
Code Doubly linked list

Delete the last node from doubly linked list

The problem revolves around the deletion of the last node from a doubly linked list. In a doubly linked list, each node holds a data element and two pointers, one pointing to the next node and the other pointing to the previous node. The objective is to remove the last node from the end of the list.

Problem Statement

Given a doubly linked list, the task is to delete the last node from the end of the list.

Example

Consider the following doubly linked list:

1 <-> 2 <-> 3 <-> 4 <-> -5 <-> 6 <-> 7 <-> 8

After deleting the last node, the list should be:

1 <-> 2 <-> 3 <-> 4 <-> -5 <-> 6 <-> 7

Idea to Solve

To address this problem, you need to find the last node in the doubly linked list and modify the pointers to remove it.

Pseudocode

function deleteLastNode():
    if head is null:
        print "Empty Linked List"
        return
    
    temp = head
    
    // Find the last node
    while temp's next is not null:
        move temp to the next node
    
    if temp equals head:
        set head to null
    else:
        set temp's previous node's next pointer to null

Algorithm Explanation

  1. Start by initializing temp to the head.
  2. Traverse the doubly linked list using the temp pointer:
    • Move temp to the next node until you reach the last node.
  3. After traversing, check if temp is equal to the head:
    • If it is, there's only one node in the list, so set head to null.
    • Otherwise, set the previous node's next pointer of temp to null.

Program List

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the doubly linked list. In the worst case, you might need to traverse the entire list to find the last node.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment