0

I am implementing a cyclic DoublyLinkedList data structure. Like a singly linked list, nodes in a doubly linked list have a reference to the next node, but unlike a singly linked list, nodes in a doubly linked list also have a reference to the previous node. Additionally, because the list is "cyclic", the "next" reference in the last node in the list points to the first node in the list, and the "prev" reference in the first node in the list points to the last node in the list.

I am having trouble with my remove method with some size usage. It's the message I'm getting when I run my tests.

Here's my code:

public class DoublyLinkedList<E>
{
private Node first;
private int size;

@SuppressWarnings("unchecked")
public void add(E value)
{
    if (first == null)
    {
        first = new Node(value, null, null);
        first.next = first;
        first.prev = first;
    }
    else
        {
        first.prev.next = new Node(value, first, first.prev);
        first.prev = first.prev.next;
    }
    size++;
}
private class Node<E>
{
    private E data;
    private Node next;
    private Node prev;

    public Node(E data, Node next, Node prev)
    {
        this.data = data;
        this.next = next;
        this.prev = prev;
    }
}
@SuppressWarnings("unchecked")
public void add(int index, E value)
{
    if (first.data == null)
    {
        throw new IndexOutOfBoundsException();
    } else if (index == 0)
    {
        first = new Node(value, first.next, first.prev);
    }
    else
        {
        Node current = first;
        for (int i = 0; i < index - 1; i++)
        {
            current = current.next;
        }
        current.next = new Node(value, current.next, current.prev);
    }
}

Here is the method I need help with. The remove method should remove the element at the specified index in the list. Be sure to address the case in which the list is empty and/or the removed element is the first in the list. If the index parameter is invalid, an IndexOutOfBoundsException should be thrown.

@SuppressWarnings("unchecked")
public void remove(int index)
{
    if (first.data == null)
    {
        throw new IndexOutOfBoundsException();
    }
    else if (index == 0)
    {
        first = first.next;
    }
    else
        {
            Node current = first.next;
            for (int i = 0; i < index - 1; i++)
        {
            current = current.next;
        }--size;
            current.next = current.next.next;

    }
}

Here is the rest of the code. The get method is incorrect, but I asked that in a different question.

    public E get(int index)
    {
   if(index >= size)
    {

    }
    return null;
    //return first.data;
}
@SuppressWarnings("unchecked")
public int indexOf(E value)
{
    int index = 0;
    Node current = first;
    while (current != current.next)
    {
        if (current.data.equals(value))
        {
            return index;
        }
        index++;
        current = current.next;
    }
    return index;
}
public boolean isEmpty()
{
    if (size == 0)
    {
        return true;
    }
    else
        {
        return false;
    }
}
public int size()
{
    return size;
}
7
  • Check out my other methods, I'm struggling with them too. Commented Mar 18, 2019 at 19:55
  • stackoverflow.com/questions/55228367/… Commented Mar 18, 2019 at 19:55
  • and stackoverflow.com/questions/55214062/… Commented Mar 18, 2019 at 19:56
  • Your method is half-way there, but you aren't updating the reference to the previous node in the list, or handling the last node case correctly. Also think about what needs to happen when there is only one node in the list. I feel you will learn more by working out the correct implementation yourself. Commented Mar 18, 2019 at 21:51
  • What would I assign current.prev to then? current.next? Commented Mar 18, 2019 at 21:58

1 Answer 1

0

This was not easy at all, however I did find the answer to my question. This is a cyclic doubly linked list. Here it is:

 @SuppressWarnings("unchecked")
 public void remove(int index)
 {
    if(index < 0 || index > size)
    {
        throw new IndexOutOfBoundsException();
    }
    Node n = first;
    for(int i = 0; i < index; i++)
    {
        n = n.next;
    }
    // n points to node to remove
    n.prev.next = n.next;
    n.next.prev = n.prev;
    if (index == 0)
    {
        if(size == 1)
        {
            first = null;
        }
        else
        {
            first = first.next;
        }
    }
    size--;
}
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.