1

我正在尝试在链接列表的末尾添加一个新节点,但它似乎没有做任何事情。它添加了第一个元素,因为它是一种特殊情况,但是当我逐步调试时会忽略所有其他分配。

这是我正在运行的测试:

@Test
public void testInsertElement()
{
PriorityList<String> list = new LinkedPriorityList<String>();
list.insertElementAt(0, "first");
list.insertElementAt(1, "second");
list.insertElementAt(2, "third");
assertEquals("first" , list.getElementAt(0));
assertEquals("second", list.getElementAt(1));
assertEquals("third" , list.getElementAt(2));
}

它在第二个断言上失败,因为在第一个断言之后没有添加任何内容。

这是节点对象的构造函数:

public class LinkedPriorityList<E> implements PriorityList<E> {

  private class Node
  {

    private E data;
    private Node next;

    public Node(E element)
    {
      data = element;
      next = null;
    }
  }

最后是我失败的代码:

public void insertElementAt(int index, E element) throws IllegalArgumentException
  {
      if(index>size() || index<0) //can only be between 0 and size()
            throw new IllegalArgumentException();

      if(size()==0)
          first = new Node(element); //adding the first element. This works
      else
      {
          if(index == size()) //if an element is being added to the end
          {
              Node ref = first;                //assigning ref to the first element of the list
              for(;ref!=null; ref = ref.next); //stepping through the list until ref is null
              ref = new Node(element);         //assigning the null reference a new Node. Doesn't assign
          }
          else //if an element is being inserted in the list. untested...
          {
              Node ref = first;
              Node temp = new Node(element);
              for(int i=1; i<index; i++)
                  ref = ref.next;
              temp = ref.next;
              ref = temp;
          }
      }
      size++; //keeping track of how many elements in list
  }

我认为这可行,但如果你也想要 get 方法,这里是:

public E getElementAt(int index) throws IllegalArgumentException
  {
    if(index>=size() || index<0)
        throw new IllegalArgumentException();

    Node ref = first;
    for(int i=0; i<index; i++)
        ref = ref.next;
    return ref.data;
  }
4

3 回答 3

3

index == size,您要创建一个新节点,找到列表中的最后一个节点,并将新节点分配给它的next指针。

最后一个节点是next指针为空的节点。

这应该足以让您自己实现算法。

于 2013-10-11T22:01:29.537 回答
1

这可能是你的意思:

for(; ref.next != null; ref = ref.next) {
  /* intentionally empty */
}
ref.next = new Node(element); 

请注意,我正在测试和分配ref.next,而不是ref它自己。

于 2013-10-11T22:02:51.557 回答
1

最后添加时也需要一个temp节点(以跟踪最后一个元素)

if (index == size())
{
    Node ref = first, temp = first;
    for (; ref != null; temp = ref, ref = ref.next);
    temp.next = new Node(element);    
}

只需将新分配Noderef; 它不会将其链接到当前最后一个节点的next.

于 2013-10-11T22:01:41.607 回答