0 
public class A<E> extend AbstractList<E>{

private SLNode<E> Head = new SLNode<E>
private int length = 0;     // length of the list

 // I will skip the class of SLNode<E>
 // Head's element and successor is initialized as null in the class SLNode<E>

     public void add(int index, E element)  // insert an element in the list 
     {
         // if index is less than 0 or greater than the length
          if( (index < 0) || (index > length ) )
               throw new IndexOutOfBoundsException();

          if(index ==0)
          {
              SLNode<E> newnode = new SLNode<E>(element, null);  // make new node
              newnode.setSuccessor(Head.getSuccessor());  
              Head.setSuccessor( newnode);
              length++;
          }
       }

Q1。这是在列表前面添加元素的正确方法吗？（使用虚拟头节点，但没有尾） Q2。列表是空的还是非空的都一样吗？

4

4 回答 4

0

这不是一个糟糕的方法，尽管对“head”使用“dummy”节点有点不寻常。

但它的优点是您可以将“Head”替换为“current”，将其初始化为“Head”，然后“爬取”列表index节点并进行插入，并且您不必将零情况特殊化.

 public void add(int index, E element)  // insert an element in the list 
 {
     // if index is less than 0 or greater than the length
      if( (index < 0) || (index > length ) ) {
           throw new IndexOutOfBoundsException();
      }

      // Find insertion point
      SLNode<E> current = Head;
      for (int i = 0; i < index; i++) {
          current = current.getSuccessor();
      }

      // Create & insert new node
      SLNode<E> newnode = new SLNode<E>(element, null);
      newnode.setSuccessor(current.getSuccessor());  
      current.setSuccessor( newnode);
      length++;
  }

（但请注意，标准命名约定是为类名保留初始大写的名称。）

于 2012-10-25T03:02:50.310 回答
0

假设这是您在头部插入的方法，我不明白您为什么需要传入索引。理想情况下，我希望只有一种插入方法。但是由于您特别要求在头部插入。

public void addToHead(E element)  // insert an element at head
     {
         if(length==0)
             throw new Exception("head does not exist");

         element.setSuccessor(head);
         head = element;


         length++;

       }
于 2012-10-25T03:13:10.253 回答
0

Q1。这是在列表前面添加元素的正确方法吗？（使用虚拟头节点，但没有尾巴）

编辑：重新阅读您的问题并尝试您的代码后，我会说是的。

Q2。列表是空的还是非空的都一样吗？

编辑：是的，它似乎在一个空列表上工作。

dummy_header_list<String> theList = new dummy_header_list<String>();
System.out.println(theList);
theList.add(0,"first add");
System.out.println(theList);
theList.add(0,"second add");
System.out.println(theList);
theList.add(0,"third add");
System.out.println(theList);

给出：

[]
[first add]
[second add,first add]
[third add,second add,first add]

有了这个 toString：

public String toString()
{
   String output = "[";
   SLNode<E> temp = Head.getSuccessor();
   while ( temp != null ) {
      if ( output.length() == 1 ) {
         output = output + temp.toString();
      }
      else {
          output = output + "," + temp.toString(); 
      }
      temp = temp.getSuccessor();
   }
   output = output + "]";
   return output;
}
于 2012-10-25T03:33:31.893 回答
0

我认为您真的不需要在列表前面插入特殊情况。在此列表的前面插入与在列表中的其他任何位置插入没有什么不同。

public void add(int index, E element)
{
    // if index is less than 0 or greater than the length
    if ((index < 0) || (index > length))
        throw new IndexOutOfBoundsException();

    SLNode<E> previousNode = head;
    for ( int i = 0; i < index; i++ ) {
        previousNode = previousNode.getSuccessor();
    }

    SLNode<E> newNode = new SLNode<E>(element, previousNode.getSuccessor());
    previousNode.setSuccessor(newNode);
    length++;
}

基本上，这只是遍历列表以找到要插入的正确节点 - 如果索引为 0，它会立即停止在开头。一旦有了要插入的节点，就执行以下三个步骤：

  1. 创建一个新节点并将其后继节点设置为前一个节点的后继节点
  2. 设置前一个节点的后继节点为新节点
  3. 列表长度加一

我对此进行了一些小测试，它似乎工作得很好。

请注意，这种方法几乎假定 head 实际上永远不会被视为列表中的元素。它实际上只是一个开始列表的地方。我的意思是 head.getElement() 将始终返回 null - 它实际上并不是列表的一部分。我不确定这是否是您想要的实现，但是当您说您以 head 元素开始列表时，这似乎是最有意义的，即使列表应该是空的。

于 2012-10-25T03:34:35.783 回答