Вставить метод для реализации пользовательского связанного списка?

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) Этот метод также должен выдавать исключение IllegalArgumentException, когда задано недопустимое значение индекса (psn) (вне границ).Я предполагаю, что диапазон значений 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, когда дело доходит до определения длины связанного списка, и правильно ли я использовал его за исключением? Это та часть, которая меня больше всего беспокоит. Заранее большое спасибо!

Answer 1

• Да, это правильный способ получения количества элементов в LinkedList без сохранения размера.

• Это один недостаток связанного спискаэто O (n) обход, но 1 вставка, если мы храним элемент "tail".

• См. Также предложения Матана Кинцлингера по логике

Этот веб-сайт имеет отличное описание связанных списков

Answer 2

В существующем состоянии ваш insert дважды перебирает весь список: один для определения размера, а другой для поиска узла.Самая базовая реализация, в которой нет данных, помогающих вам подобрать поле размера, обновляемое с каждой записью, нужно пройти только один раз, потому что вы узнаете, что нужная позиция недействительна, если вы нажмете sentinel раньше, чеможидается.Вот как я бы это реализовал:

public void insert(String item, int position) {
  if(position == 0) {
    head = new Node(item, head);
    return;
  }

  List.Node previousNode = head;

  for(int i = 1; i < position && previousNode != null; ++i) {
    previousNode = previousNode.next;
  }

  if(position < 0 || previousNode == null) {
    throw new IllegalArgumentException("index " + position + " is out of bounds");
  }

  previousNode.next = new Node(item, previousNode.next);
}

Некоторые другие соображения:

• Попробуйте использовать описательные имена переменных вместо таких сокращений, как psn, так как ониможет быть трудно читать без полного контекста.В большинстве реальных сценариев более важно оптимизировать для удобства чтения человеком, потому что чем проще людям будет отлаживать и поддерживать код для его понимания, тем меньше вероятность появления ошибок.Много раз имена переменных на самом деле являются вашей самой первой подсказкой к тому, что происходит, и настоящим спасателем здравомыслия!В прошлый раз, когда я был спасен хорошо заданным именем переменной, пытаясь понять, почему код во внешней библиотеке npm ломался, буквально несколько дней назад.

• Попробуйтеиспользовать охранные пункты и досрочное возвращение во избежание кода стрелки . Несколько точек возврата не обязательно являются плохими , и их обнаружение не является проблемой, если вы избегаете чрезмерной цикломатической сложности в ваших методах.Например, в этом случае особый случай вставки в нулевую позицию - это одна возможность досрочного возврата, поскольку нет необходимости в проверках и после ее выполнения ничего не нужно делать.

• Сделайте ваши исключениямаксимально полезно.Это означает, что когда вы генерируете исключение из-за того, что перехватили другое, включите перехваченное вами в качестве причины, чтобы не прерывать трассировку стека ;в этом случае, когда не существует более раннего исключения, должно быть достаточно полезного сообщения, помогающего разработчику выяснить, что произошло.В этом случае IllegalArgumentException не говорит нам много о том, что вызвало это исключение, отсюда и сообщение.Практически каждый конструктор исключений допускает сообщение и причину Throwable.

Answer 3

Вы всегда можете проверить свой код, запустив его в некоторых тестовых случаях.Но вот мои комментарии к этому коду:

• последний оператор 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++;
}