Posted on by Kalkicode
Code Doubly linked list

Delete initial n nodes in a doubly linked list

The problem involves deleting the initial n nodes from a doubly linked list. In a doubly linked list, each node contains a data element and two pointers, one pointing to the next node and another pointing to the previous node. The task is to remove the first n nodes from the beginning of the list.

Problem Statement

Given a doubly linked list and an integer n, the objective is to delete the first n nodes from the beginning of the list.

Example

Consider the following doubly linked list:

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

If we want to delete the first 5 nodes from the beginning of the list, the resulting list should be:

6 <-> 7 <-> 8

Idea to Solve

To solve this problem, you need to traverse the list while keeping track of the number of nodes you have visited. Once you have visited n nodes, you can manipulate the pointers of the nodes to remove them from the list.

Pseudocode

function deleteFirstN(n):
    if head is null or n is less than or equal to 0:
        return
    
    temp = head
    counter = 0
    while temp is not null and counter < n:
        increment counter by 1
        move temp to the next node
    
    if counter is greater than or equal to n:
        counter = n
        while counter > 0 and head is not null:
            temp = head
            head = temp.next
            if head is not null:
                head.prev = null
            if temp equals tail:
                tail = null
            temp = null
            decrement counter by 1
    else:
        print "Deleted node " + n + " not exist"

Algorithm Explanation

  1. Start by initializing temp to the head of the list and counter to 0.
  2. Traverse the doubly linked list using the temp pointer:
    • Increment the counter by 1.
    • Move temp to the next node.
  3. After traversing, check if counter is greater than or equal to n:
    • If it is, you have visited at least n nodes.
    • Initialize counter to n.
    • Loop through n times and delete nodes from the beginning:
      • Update the head pointer to point to the next node.
      • If the new head is not null, update its prev pointer.
      • If the node being deleted is the tail, update tail to null.
    • Set temp to null after each deletion.
    • Decrement counter by 1 after each deletion.
  4. If counter is less than n, print a message indicating that the node to be deleted doesn't exist.

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 delete the initial n nodes.

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