java - 我在自己的 LinkedList 类中引用我的 'head' 节点时遇到问题

Question

我已经用 Node 首先和最后编写了自己的链接类代码，因为最后存在一个 Node，当我尝试在 main 中手动创建 LinkedList 时，我遇到了有关引用和指针操作的问题方法并进行测试。

我非常熟悉“addFirst”、“addLast”和“remove”方法中实现的递归，但现在不知何故，在 addFirst 方法之后，对 Node First 的引用变成了 null。

public class LinkedList<T> {
  Node first,last,temp;

   public class Node{
     T value;
     Node next;

     public Node(T value, Node next) {
        this.value = value;
        this.next = next;
     }

     public String toString(){
        if(next == null){
            return value.toString();
        }
        else{
            return value.toString() + " " + next.toString();
        }
     }

     public T getLL(int index){
        if(index == 0){
            return value;
        }
        if(next == null){
            throw new 
               IndexOutOfBoundsException("have reached the end of the list, none found");
        }
        return next.getLL(index-1);
     }

     public T removeLL(int x){
        if(x == 1){
            T value = next.value;
            next = next.next;
            return value;
        }
        else if(next == null){
            throw new 
              IndexOutOfBoundsException("have reached the end of the list, none found");
        }
        else{
            return next.removeLL(x-1);
        }
     }
  }

  public LinkedList(T value) {

    temp =  new Node(value,null);
    first = new Node(value,null);
    last = temp;
  }

  public static void main(String[] args) {
    /**
     * [120,110,100,90,80];
     */
    LinkedList L = new LinkedList(100);
    L.addFirst(110);
    L.addFirst(120);
    L.addLast(90);
    L.addLast(80);
    System.out.println(L.size());
    System.out.println(L.remove(0));
    System.out.println(L.last.toString());
    //return null which causes the remove method not to work.
    System.out.println(L.first);
  }

  public void addFirst(T value){
    first = new Node(value,first);
  }

  public void addLast(T value){
    Node p = first;
    if( p == null){
        first = last = new Node(value,null);
    }

    while(p.next!= null){
        p = p.next;
    }
    last.next = new Node(value,null);
    last = new Node(value,null);

  }

  public T get(int index){
    if(first == null){
        throw new IndexOutOfBoundsException("empty list");
    }

    return first.getLL(index);


  }

  public int size(){
    int c = 0;
    while(first != null){
        first = first.next;
        c++;
    }
    return c;
  }

  public T remove(int x){
    if(first == null){

        throw new IndexOutOfBoundsException("Tried to remove from empty list");
    }
    if (x == 0) {
        T value = first.value;
        first = first.next;
        return value;
    }
    return first.removeLL(x);
  }
}

我期望 Node 首先指向 LinkedList 的第一个元素，而不是指向 null。同时，这不会影响最后一个Node的指针。

Answer 1

看起来像是 AddLast 函数内部的问题。你停止了名单。不应该是这样吗？

public void addLast(T value){
   Node p = first;
   if( p == null){
      first = last = new Node(value,null);
   }

   while(p.next!= null){
     p = p.next;
   }
   p.next = new Node(value,null);
   last = p.next;
   //last = new Node(value,null);
 }

更新关于您的评论和更新的答案。

1. 您的尺寸函数错误:

   public int size(){
     int c = 0;
     while(first != null){
       first = first.next; // <-- now first point to the last and length is 1
       c++;
     }
     return c;
   }
   

当你删除第一个元素时，第一个元素为空。您必须创建临时变量来遍历列表。要检查此注释，请检查您计算大小的行。

你实际上不太正确 last.next = new Node(value,null); 指向新节点。但是，您没有再次连接 last = last.next 您的新节点消失了，因为您为最后一个创建了新节点，但 last.next 指向新节点，因此最后一个是不再持续了。 (我想你明白我的意思)