如何找到链表中的第一个值？

Question

我有一个给定的链接列表，我需要通过 getFirst 方法找到列表中的第一个值。如果该值为空，我需要显示一条错误消息并退出程序。链接列表已经给了我链接，所以：

class MyLinkedList
{
   private class Node            // inner class
   {
      private Node link;
      private int x;
   }
   //----------------------------------
   private Node first = null;    // initial value is null
   //----------------------------------
   public void addFirst(int d)
   {
      Node newNode = new Node(); // create new node
      newNode.x = d;             // init data field in new node
      newNode.link = first;      // new node points to first node
      first = newNode;           // first now points to new node
   }
   //----------------------------------
   public void traverse()
   {
     Node p = first;
      while (p != null)            // do loop until p goes null
      {
         System.out.println(p.x);  // display data
         p = p.link;               // move p to next node
      }
   }
}
//==============================================
class TestMyLinkedList
{
   public static void main(String[] args)
   {
      MyLinkedList list = new MyLinkedList();
      list.addFirst(1);
      list.addFirst(2);
      list.addFirst(3);
      System.out.println("Numbers on list");
      list.traverse();
   }
}

这是我尝试过的方法：

 public static Node getFirst(Node list)
  {
    if (list == null)
    {
      System.out.println("Error!");
      System.exit(1);
    }
    return MyLinkedList.first;
  }

我知道这并不完全正确，我们刚刚在课堂上开始这个，所以我很难理解它是怎么回事。谢谢！

Answer 1

我认为您应该查看 https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html 并首先了解链表的行为。一旦您了解了它的行为方式，您就可以考虑如何围绕它添加功能。现在你只有一个方法，你调用的次数超出了你应该调用的次数。创建一个接口并记录它也可能有所帮助，这样您就知道每个方法应该做什么。

Answer 2

您应该检查第一个不为空，以便执行您在问题中描述的操作。另外，第一个节点自动引用自身有点奇怪，因为通常它会保留为空，直到添加另一个节点

Answer 3

请注意，第一个值通过

Node

链接到第一个

null

。那么你必须检查两件事

1. Node == null

   （你明白了）

2. Node.next == null

   （你必须这样做）

当

Node.next == null

时。这意味着

Node

是第一个值，因为它通过 is

Node

链接到初始

null

。

那么你就有了

public static Node getFirst(Node list)
{
    // if the list is empty
    if (list == null)
    {
      System.out.println("Error!");
      System.exit(1);
    } else if(list.link == null) {
      // this is the first value!
      return list;
    } else {
    // keep searching recursive with the next Node
    return getFirst(list.link);
    }
}

Answer 4

您问题中的类

MyLinkedList

遵循堆栈数据结构的模式（在我写这个答案时）。也就是说：每当您添加新元素时，新元素都会替换先前添加的元素作为第一个元素。

我猜你想将

1

作为你的第一个元素，如果你按顺序添加了元素

1

,

2

,

3

。如果我错了请纠正我。

在这种情况下，你的链接列表及其检索应该是这样的：

（注意：我避免了

private

vars 、

public

getter 、 settter 等；以使代码易于阅读。但读者应该添加它们。）

class Node{ int x; Node next; }

class LinkedList
{ Node head,tail;
  void add(int y)
  { Node node = new Node();
    node.x=y;
    if(head==null)
      head = tail = node;
    else
      tail = tail.next = node;
  }
  int getFirst()
  { if(head!=null)
      return head.x;
    else
      throw new java.util.NoSuchElementException("List is empty");
  }
}

如果你看一下

java.util.LinkedList

，你会发现链表中传统使用的方法。如果这不是一个家庭作业问题，那么我建议你不要重新发明轮子。只需使用现有的库即可。

如果您必须使用堆栈数据结构，并且无法更改它，那么我建议您必须像这样更改您的

getFirst()

：

  int getFirst()
  { if(tail!=null)
      return tail.x;
    else
      throw new java.util.NoSuchElementException("List is empty");
  }

如果您不允许在代码中添加

Node tail

，那么您的

getFirst()

将如下所示：

  int getFirst()
  { if(head==null)
      throw new java.util.NoSuchElementException("List is empty");
    Node node = head;
    while(node.next!=null)
      node=node.next;
    return node.x;
  }