CODEWITHSUNDEEP
javaobjectlinked-list
h7779
h7779

Reputation: 1

Doubly Linked List, Removing First Occurrence

I am having trouble figuring out how to remove a first occurrence node.

So far here is my code for removing the first occurrence node.

public boolean remove(E doomedElt)
{
    if (head == null)
        return false;

    else if (doomedElt.equals(head.data))
    {
        removeFirst();
        return true;
    }
    else
    {
        DLLNode<E> cursor = head;
        while(cursor.next != null && !cursor.next.data.equals(doomedElt))
            cursor = cursor.next;

        if (cursor.next.next == null && cursor.next.data.equals(doomedElt))
        {
            removeLast();
            return true;
        }
        else
        {
            cursor.next = cursor.next.next;
            cursor.next.next.prev = cursor.prev;  //<---Stuck here.
            cursor.prev = cursor.prev.prev;       //<---And here.

            return true;
        }

    }
}

Here is the code for removing last:

public E removeLast()
{
    if (tail == null)
        throw new NoSuchElementException("Cannot removeFirst from empty list");
    else if (head == tail)
    {
        E firstOne = head.data;      
        head = tail = null;
        return firstOne;
    }
    else
    {
        E lastOne = tail.data;     
        tail = tail.prev;
        tail.next = null;
        return lastOne;
    }
}

Here is the code for removing first:

public E removeFirst()
{
    if (head == null)
        throw new NoSuchElementException("Cannot removeFirst from empty list");
    else if (head == tail)
    {
        E firstOne = head.data;     
        head = tail = null;
        return firstOne;
    }
    else
    {
        E firstOne = head.data;     
        head = head.next;
        head.prev = null;
        return firstOne;
    }
}

When I run my driver, which will add (4, 5, 6 ,5, 7, 6). From there I tell it to remove the first 6. What I should be getting is a (4, 5, 5, 7 ,6) following the .next link (which I do get), and following the .prev link I should be getting (6, 7, 5, 5, 4). Instead, I am getting (6, 7, 4).

However, when I remove the cursor.next.next.prev = cursor.prev; and cursor.prev = cursor.prev.prev; The .prev link goes back to the original but just backwards. Which means that my logic for reconnecting the .prev link in incorrect.

Can someone please help to with the logic for reconnect the .prev link, by bypassing the node.

Upvotes: 0

Views: 990

Answers (1)

nhouser9
nhouser9

Reputation: 6780

This:

cursor.next = cursor.next.next;
cursor.next.next.prev = cursor.prev;  //<---Stuck here.
cursor.prev = cursor.prev.prev;       //<---And here.

Should be changed to this:

cursor.next = cursor.next.next;
cursor.next.prev = cursor;

Because cursor is the position before the element removed. I.e. if you have A B and C and you are removing B, the next of A should become C and the previous of C should become A.

Note this code is untested but it should work - let me know if not and I will help more.

Upvotes: 1

Related Questions