我需要帮助我在java中的add方法。它适用于双链表。
我正在实现循环DoublyLinkedList数据结构。与单链表一样,双链表中的节点具有对下一节点的引用,但与单链表不同,双链表中的节点也具有对前一节点的引用。此外,因为列表是“循环”的,所以列表中最后一个节点中的“下一个”引用指向列表中的第一个节点,列表中第一个节点中的“prev”引用指向最后一个节点。列表。
该方法的作用是将value参数插入列表中的指定索引处。请务必解决列表为空和/或添加的元素是列表中的第一个的情况。如果index参数无效,则应抛出IndexOutOfBoundsException。
这是我的代码如下:
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(index < 0)
{
throw new IndexOutOfBoundsException();
}
if(index > size)
{
throw new IndexOutOfBoundsException();
}
if (first.data == null)
{
throw new NullPointerException();
}
if (index == 0)
{
first = new Node(value, null, null);
first.next = first;
first.prev = first;
}
else
{
Node current = first;
for (int i = 0; i < index; i++)
{
current = current.next;
}
current.prev.next = new Node(value, current, current.prev); // This is the line where I get lost on.
current.prev = current.prev.next;
}
size++;
}
我的其余代码就在这里。请关注我正在研究的方法。谢谢!
@SuppressWarnings("unchecked")
public void remove(int index)
{
if(index < 0)
{
throw new IndexOutOfBoundsException();
}
if(index > size)
{
throw new IndexOutOfBoundsException();
}
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; i++)
{
current = current.next;
}
// current.prev = current.next;
current.next = current.next.next;
}
size--;
}
@SuppressWarnings("unchecked")
public E get(int index)
{
if(index < 0)
{
throw new IndexOutOfBoundsException();
}
if(index > size)
{
throw new IndexOutOfBoundsException();
}
Node current = first;
for (int i = 0; i < index; i++)
{
current = current.next;
}
return (E) current.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 String toString()
{
if (isEmpty())
{
return "[]";
}
else
{
String result = "[" + first.data;
Node current = first.next;
for(int i = 0; i < size-1; i++)
{
result += ", " + current.data;
current = current.next;
}
result += "]";
return result;
}
}
}
这根本不容易,但我想出了我的问题的答案。
@SuppressWarnings("unchecked")
public void add(int index, E value)
{
if(index > size || index < 0)
{
throw new IndexOutOfBoundsException();
}
if (first == null)
{
Node n = new Node(value, null, null);
n.next = n;
n.prev = n;
first = n;
}
else
{
Node current = first;
for (int i = 0; i < index; i++)
{
current = current.next;
}
//current points to node that will follow new node.
Node n2 = new Node(value, current, current.prev);
current.prev.next = n2;
current.prev = n2;
//update first if necessary.
if(index == 0)
{
first = n2;
}
}
size++;
}