我正在实现循环doublylinkedlist数据结构。像一个单身链接列表,双重链接列表中的节点具有对下一个节点的引用,但是与单个链接列表不同,双链接列表中的节点也具有对先前节点的引用。此外,由于列表是"循环",因此列表中最后一个节点中的"下一个"引用指向列表中的第一个节点,而列表中第一个节点中的" 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);
}
}
这是我需要帮助的方法。删除方法应删除列表中指定索引的元素。确保解决列表为空的情况和/或删除元素是列表中的第一个。如果索引参数无效,则应抛出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;
}
这一点都不容易,但是我确实找到了问题的答案。这是一个双重链接列表。在这里是:
@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--;
}