时间戳

首页 > 解决方案 > 自定义链表实现的插入方法？

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

问题描述

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

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 到第一个空元素出现时（如果我对此不正确，请纠正我。这是我写的方法：

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 循环，以及我是否正确使用了它，但有例外？这是我最关心的部分。非常感谢您！

标签： javadata-structureslinked-listinsertnodes

解决方案

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

  • 最后一个 if 语句if (current != null)将始终返回 false，因为在此之前的 while 循环将current在最后变为 null。
  • 我会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++;
}

推荐阅读