CODEWITHSUNDEEP
javalinked-listdoubly-linked-listcircular-reference
Citut
Citut

Reputation: 907

Removing nodes from a circular doubly linked list (Java)?

I am writing some code where I need to remove an item in a circularly linked list (who's head acts as a dummy node) and return it (if removing the first node). I think I have the code just about right, but I'm not sure.

Am I understanding this correctly? (starting with a dummy node)

dummy -> A -> B -> C -> D -> dummy (wrap around to the dummy node)

So if I want to remove the first actual piece of data(A), I would need to assign it to a temp variable. So Node first = head.next. Then I need to have the dummy head reference "b" so I would need to do head.next = first.next. Is this all that needs to be done?

private Node remove()
{
     Node returnNode = head.next;
     head.next = returnNode.next;
     return returnNode;
}

In the case of removing any node N from the list (assuming it is on the list), it is sort of the same concept? So from the example above, lets say we want to remove node B. In this case, we need to set B.next = B.previous and B.previous = B.next correct? Or do I need to do something like B.previous.next = B.next and B.next.previous = B.previous? Do I need to traverse the list to find the element to remove?

private void removeNode(Node n)
{
    n.next = n.previous; // or n.previous.next = n.next
    n.previous = n.next; // or n.next.previous = n.previous
}

Upvotes: 0

Views: 1137

Answers (2)

Naveen Yadav
Naveen Yadav

Reputation: 233

In any case you need to traverse the list to remove or add, whether you are using single linked list or doubly linked list or circular LL.

Now as per your question, you haven't mentioned whether it is a doubly LL or not but I am assuming it is as you have used node.previous in your second example.

As per my understanding if you are having a node of circular LL, You don't have to worry about whether this node is head or not because anyhow all the nodes will be accessible, using this node.

Now If I am able to understand your problem correctly, then for your first example,

if you need to delete a node(A in this case), u need that node in your function parameter. Something like this...

// assuming the key exists in your LL.

    private Node remove(Node nodeToBeRemoved)
    {   
        Node returnNode = nodeToBeRemoved
        while(currentNode.data = nodeToBeRemoved.data) {
            returnNode = returnNode.next
        }
        returnNode.previous.next = returnNode.next
        return returnNode;
    }

Same should be the case for the second example as well.

Upvotes: 0

JoeFox
JoeFox

Reputation: 1081

A double linked list means that each node has also a connection to the previouse node.

Your example would only switch the next and previous references. You should set:

n.next.previous = n.previous n.previous.next = n.next

Since you have a circular linked list there should only be special cases when adding the first element or removing the last element.

Upvotes: 0

Related Questions