java - 删除链表中的元素

Question

再次寻求帮助，因为我的教授似乎在解释事情方面做得很糟糕(假设我们对 Java 编程了解太多，而事实上，这是我们大多数人上的第一门 Java 类(class))。

不是在寻找为我编写代码的人，而是寻找可以让我知道我是否走在正确轨道上并引导我朝正确方向前进的人。我真的很想学习这些东西，而不是填鸭式的，但是教授让我很难做到这一点，所以我来这里寻求帮助。

问题是获取一个 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

您的链接列表如下所示:

在此图像上，prev 是要删除的对象前面的对象。 Cur 是您要删除的对象。

循环直到下一个指针指向要删除的对象。之后，将 prev 的 next 指针设置为 cur 后面的对象(cur 是要删除的对象)。

在伪代码中，它看起来像这样:

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

完成此步骤后，上一个将位于正确的位置。

您可以看到，该算法适用于除去除头部之外的所有情况。您可以检查是否要移除头部并使用不同的算法或者使用虚拟节点。使用虚拟节点作为头，使用虚拟节点作为尾部(这里不显示，但在双链表中使用)。这个虚拟节点称为哨兵。您永远不会删除此哨兵，但您的算法无需额外检查即可工作，因为您将删除> 0的元素。

来源: https://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked%20Lists/linked%20lists.html

在评论中我看到了关于干净代码的讨论。如果你正在学习干净的代码，你会发现，如果变量表达了它们的目的，很多算法会更容易理解。例如，N 应该是大小。但在不同的上下文中，它可能是缓存的元素上限。关于这个主题有一本好书:《Clean Architecture: A Craftsman's Guide to Software Structure and Design》(Robert C. Martin 系列)

您认为什么更容易阅读:

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;
  }
 }