Java：单链表，虚节点，插入

Question

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。列表是空的还是非空的，它是一样的吗？

Answer 1

这并不是一个糟糕的方法，尽管为“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++; 
    } 

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

Answer 2

假设这是您的插入在头的方法，我不明白为什么你需要传递索引英寸理想情况下，我想只有1插入方法。但是因为你特别要求插入头部。

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

     } 

Answer 3

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

Answer 4

我不认为你真的需要在列表的前面插入一个特殊情况。在列表的前面插入与在列表中的其他位置插入不同。

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.getElement（）将总是返回null - 它不是列表中的真正部分。我不确定这是否是您想要的实现，但是当您说您使用head元素开始列表时，即使列表应该是空的，它似乎最有意义。