Удалить элементы в связанном списке

Question

Снова обращаюсь за помощью, так как мой профессор, кажется, делает ужасную работу по объяснению вещей (предполагается, что мы слишком много знаем о Java-программировании, хотя на самом деле это первый Java-класс, который посещают большинство из нас).

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

Вопрос в том, чтобы взять LinkedList и создатьфункция для удаления k-го элемента в этом списке.Я понял, как удалить первый элемент, если k == 0, но я заблудился о том, как получить доступ к нужному элементу для "k" в моем цикле.Вот что у меня есть:

public class MyLinked {
  static class Node {
    public Node(double item, Node next) {
      this.item = item;
      this.next = next;
    }

    public double item;
    public Node next;
  }

  int N;
  Node first;
  // delete the kth element (where k is between 0 and N-1 inclusive)
  public void delete(int k) {
    if (k < 0 || k >= N) throw new IllegalArgumentException();
    {
      if (k == 0) {
        remove(first.item);
      } else if (k > 0) {
        kElem = LinkedList.get();
        remove(kElem);
      }
    }
  }
}

Я пытаюсь присвоить переменную функции .get, но я определенно ошибаюсь, но не совсем уверен, как это сделать.Однако я знаю, что мне нужно получить значение k-го элемента и удалить его.

Я также знаю, что после этого мне нужно настроить указатели в LinkedList, чтобы заполнить пробел, гдеэлемент, который я удалил, был бы.

Спасибо.

Answer 1

Метод get не делает то, что вы хотите.Вам нужно будет написать код для итерации в положение k-1 и переключить указатель, как вы сказали: -

например.список 1-> 2-> 3-> 4, k = 2

итерация с использованием следующего указателя до 2, переключение следующего указателя на точку 4. Вам больше ничего не нужно делать (удалять и т. д.)

Answer 2

Ваш список ссылок выглядит следующим образом:

На этом изображении prev находится объект перед объектом, который вы хотите удалить.Cur - это объект, который вы хотите удалить.

Вы зацикливаетесь, пока следующий указатель не нацелится на объект, который вы хотите удалить.После этого вы устанавливаете следующий указатель prev на объект, который следует за cur (cur - это объект, который вы хотите удалить).

В псевдокоде это будет выглядеть так:

prev = head;
while(prev.next != cur) {
  prev = prev.next
}

После этого шага предыстория находится в правильном положении.

Вы можете видеть, что этот алгоритм работает с каждым случаем, кроме удаления головы.Вы можете проверить, удаляете ли вы голову и используете другой алгоритм или используете фиктивный узел.Используйте dummy-узел в качестве головы, а dummy-узел - в качестве хвоста (здесь не отображается, но используется в списках с двойными связями).Эти фиктивные узлы называются часовыми.Вы никогда не удалите этого стража, но ваш алгоритм работает без дополнительной проверки, потому что вы удалите элементы> 0.

Источники: https://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked%20Lists/linked%20lists.html

В комментариях я видел обсуждение очистый код.Если вы изучаете чистый код, вы увидите, что многие алгоритмы легче понять, если переменные выражают свое назначение.Например, N должно быть размером.Но в другом контексте это может быть верхний предел элементов для кэша.На эту тему есть хорошая книга: Чистая архитектура: Руководство мастера по структуре и дизайну программного обеспечения (серия Роберта С. Мартина)

Как вы думаете, что легче читать:

int[][] a = new int[100][200];
for(int i = 0; i < a.length) {
  for(int j = 0; j < a[i].length) {
    a[i][j] = i*j;
  }
 }

или это:

 int[][] productOfRowColumns = new int[100][200];
 for(int row = 0; i < productOfRowColumns.length) {
  for(int column = 0; j < productOfRowColumns[row].length) {
    productOfRowColumns[row][column] = row*column;
  }
 }

Answer 3

Сначала перейдите к элементу k-1.Установите element.next = element.next.next.Вот как вы пропускаете элемент, который должен быть удален.

Исключение: Когда k = 0 (элемент head), просто установите head = head.next.

При желании вы можете установить следующее =NULL для удаленного элемента (когда вы выбрали k-1 элементов, удалите = element.next перед установкой element.next = element.next.next. Затем произнесите delete.next = null, чтобы очистить его следующий указатель.

---

Существует также второй распространенный способ перехода к элементу kth, но вы всегда сохраняете предыдущий (k-1) элемент в переменной. Производительность хуже, потому что вы обновляете 2 переменные на каждом шагеЭто может быть более интуитивно понятно. Проверьте это видео: https://www.youtube.com/watch?v=2RwWsHePdr8 (я надеюсь, что на SO разрешены yt-ссылки)

---

Кстати, ваш

  static class Node {
    public Node(double item, Node next) {
      this.item = item;
      this.next = next;
    }

    public double item;
    public Node next;
  }

  int N;
  Node first;

ваша реализация списка. LinkedList - реализация, предоставляемая java. https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html. Вы не можете смешивать их.

---

Подсказки:

• Don 'не забудьте уменьшить размер списка (N -;)
• Вы можете "перейти" к n-му элементу с помощьюth "Узел тока = голова;for (int i = 0; i
• То, что я имею в виду под" головой ", означает" ваш первый ". Это первый элемент списка.