java - 自定义链表实现的insert方法？

Question

我想要一些关于我编写的关于在链表中插入元素的方法的反馈。我得到的链表类定义是:

public class List {
  private Node head;

  private static class Node {
    public String data;
    public Node next;

    public Node(String data, Node next) {
      //Assign data and next here
    }
    //Optional Node helper methods are written here
}
//List methods and data go here

基于这个定义，我正在尝试创建一个插入方法。我不确定我得到的定义是否包含 size() 方法，但我假设它没有并试图找到一种方法来找到大小(基本上是列表中有多少个节点) 在我的插入方法中。该方法具有签名 public void insert(String s, int psn) 当给出非法索引 (psn) 值(超出范围)时，此方法还应抛出 IllegalArgumentException。我的猜测是 psn 的值范围是从 0 到第一个 null 元素出现时(如果我对此不正确，请纠正我。这是我写的方法:

public void insert(String s, int psn) {
  Node temp = head; //Save original head
  int c = 0;

  while (temp != null) { //Traverse linked list
   c++;
   temp = temp.next;
  }

  if (psn < 0 || psn >= c) { //Should throw exception when illegal value is used
    throw new IllegalArgumentException();
  } 

  if (psn == 0) { //Special case when inserting an element at the front of the list
    head = new Node(s, head);

  } else if (head != null) {
    Node current = head; //Save original head while traversing list

    while (current != null) {
      current = current.next;
      psn--;
    }

    if (current != null) { //We are at the position where we want to insert the element
      current.next = new Node(s, current.next);
    }
  }
}

有人能告诉我在查找链表长度时我是否正确使用了第一个 while 循环，以及我是否正确使用了它但有异常(exception)？这是我最关心的部分。非常感谢您!

Answer 1

您始终可以通过在某些测试用例上运行代码来测试您的代码。但这是我对这段代码的评论:

• 最后一个 if 语句 if (current != null)将始终返回 false，因为之前的 while 循环将使 current最后为空。
• 我会检查 psn < 0在第一个 while 循环之前，以减少浪费的计算。
• 我建议你在类里面保留一个字段，名为 size ，它将处理列表的大小。一开始它会被设置为 0，在每个 insert 之后每个 remove您将更新此字段。

然后代码看起来像这样:

public void insert(String s, int psn) {     
    if(psn < 0 || psn > size)
        throw new IllegalArgumentException();
    Node temp = head; //Save original head
    for(int i=0;i<psn-1;i++)
        temp = temp.next;
    temp.next = new Node(s, temp.next);
    this.size++;
}