Posted on by Kalkicode
Code Doubly linked list

Delete alternate nodes of a Doubly Linked List

The problem at hand involves deleting alternate nodes from a given doubly linked list. The task is to remove every second node in the list, starting from the first node. The solution should modify the pointers of the adjacent nodes to maintain the integrity of the doubly linked list.

Before Delete alternate nodes of a Doubly Linked List After Delete alternate nodes of a Doubly Linked List

Problem Statement

Given a doubly linked list, the goal is to delete alternate nodes from it, effectively retaining only every other node while maintaining the connectivity and order of the remaining nodes.

Idea to Solve

The core idea to solve this problem is to iterate through the linked list while maintaining a flag that toggles between true and false. This flag determines whether the current node should be deleted or not. On each iteration, you check the flag: if it's true, you delete the current node, and if it's false, you move to the next node.

Pseudocode

Here's the pseudocode that outlines the algorithm to delete alternate nodes of a doubly linked list:

class LinkNode:
    int data
    LinkNode next
    LinkNode prev

class DoublyLinkedList:
    LinkNode head

    function deleteAlternate():
        If head is null:
            Print "Empty linked list"
            Return
            
        Initialize a pointer temp to head
        Initialize a boolean flag as false
        
        While temp is not null:
            If flag is true:
                If temp.next is not null:
                    Set temp.next.prev to temp.prev
                If temp.prev is not null:
                    Set temp.prev.next to temp.next
            Move temp to temp.next
            Toggle the value of the flag

Create a DoublyLinkedList object
Insert nodes into the list using the insert function
Display the original linked list using the display function
Delete alternate nodes using the deleteAlternate function
Display the modified linked list

Algorithm Explanation

  • The deleteAlternate function begins by checking if the list is empty. If it is, it prints a message and returns.
  • It initializes a pointer temp to the head of the linked list and a boolean flag to determine whether the current node should be deleted.
  • The algorithm iterates through the list. If the flag is true, it deletes the current node by adjusting the pointers of the adjacent nodes. Then, it moves the temp pointer to the next node and toggles the value of the flag.
  • This process continues until the end of the list is reached.

Code Solution

Time Complexity

Deleting alternate nodes requires visiting each node in the list once, so the time complexity is O(N), where N is the total number of nodes in the list.

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