0

我正在实现一个循环的 DoubleLinkedList 数据结构。与单链表一样，双向链表中的节点具有对下一个节点的引用，但与单链表不同的是，双向链表中的节点也具有对前一个节点的引用。另外，由于列表是“循环的”，所以列表中最后一个节点中的“next”引用指向列表中的第一个节点，列表中第一个节点中的“prev”引用指向列表中的最后一个节点名单。

我的删除方法在使用某些尺寸时遇到问题。这是我在运行测试时收到的信息。

这是我的代码：

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);
    }
}

这是我需要帮助的方法。remove 方法应该删除列表中指定索引处的元素。请务必解决列表为空和/或删除的元素是列表中第一个的情况。如果 index 参数无效，则应抛出 IndexOutOfBoundsException。

@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;

    }
}

这是其余的代码。get 方法不正确，但我在另一个问题中提出了这个问题。

    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;
}
4

1 回答 1

0

这一点都不容易，但我确实找到了我的问题的答案。这是一个循环双向链表。这里是：

 @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--;
}
于 2019-03-21T20:24:12.673 回答