通过手写Java代码实现数据结构中的单链接列表和Java访谈问题的链接列表的反向链接

LinkedList是一个链表. 链表有两种类型，单链表和双链表. 它们之间有什么区别

单链表概念模型

这幅画不好看，重点不在看它. 每个黑框表示一个元素，红色框表示元素的后节点，该节点指的是下一个元素，依此类推，直到表中的最后一个元素，此时他的后节点为空，这是链结构链表，那么既然有一个单链表，那么就必须有一个双链表，不用担心，让我们首先看一下如何反转单链表. 为什么要撤消它？使用数据结构的选择条件是它具有特殊功能. 链表的特征之一是它可以颠倒. 怎么做？链表反转是一个常见的基本面试问题.

这很简单. 如果不简单，则不会使用链接列表. 从最后开始，它的post节点最初是空的，现在引用了倒数第二个元素. 倒数第二个元素的post节点最初指向原始的end元素，它是反转后的第一个节点. ，现在更改为指向倒数第二个节点java 链表，依此类推，直到反向之前的第一个元素，并且其后节点此时都无效，指向null. 链表反转有一个常见的应用，即以反向顺序和反向顺序排列，可以快速完成反转，但是单个链表有一个缺点. 如何找到最后一个元素，我需要遍历整个链表，然后在元素后找到带有空节点的元素，然后将其放在链表的末尾. 如果现在删除链接列表中的最后一个元素怎么办？我们需要在链表中找到倒数第二个元素，然后将其后节点设置为空. 此时，原始的结束元素将被丢弃，并且GC将在没有任何对象引用的情况下对其进行回收. 现在需要解决的问题是如何在链表中找到倒数第二个元素. 有必要遍历链表两次并使用计数器. 为此，我们封装了一种删除end元素的方法.

这是一个Node节点类. 我们以节点为单位，因为每个节点都存储下一个元素的信息，然后节点存储该元素，然后该元素存储该节点，这称为自关联，这有点复杂. 逻辑上，变量next表示下一个节点，变量element表示该元素存储的对象. numberCounter是一个公共计数器，将在下面使用. Node的构造方法需要传入存储在当前元素中的对象，然后传入该节点. lastOne变量将值作为方法返回，指示链接列表中的最后一个元素. 如前所述，最后一个元素的特征是什么？也就是说，节点信息为空，那么我们只需要迭代地找出下一个为空的节点并返回. 该代码实现使用递归方法. LastOne用于保存当前元素信息. 经过多少次递归后，如果if中的条件为false，则当前元素lastOne为最后一个元素，只需返回即可.

这是删除单链列表最后一个元素的方法. 我已经在上面提到了两个迭代+一个计数器索引. 让我说说如何使用Node创建链表，只要构造方法中的第一个参数节点是不断新的新节点，直到该节点为null为止. 接下来，我们调用该方法以找到最后一个元素. 这是第一次迭代. 调用它的目的是我需要计算numberCounter编译所有元素所需的次数. 为什么？当遍历numberCounter-1次时java 链表，当前元素是倒数第二个元素，我们可以为其节点信息分配null. 当然，还有另一种方法，就是我在图片中写的方式，结果是相同的，当index = 0时，可以找到倒数第二个元素. 其中，红色框包围的方法是打印倒数第二个元素的方法. 倒数第二个元素是String类型的值3，蓝色框是第一个元素的打印方法，粉红色框是打印第一个元素和倒数第二个元素之间的方法，当我们最终知道index = 0时，我们将倒数第二个元素节点的值分配为null，最后一个元素被删除. 此方法实现两个遍历+一个计数器，第一个遍历在n.findLastOne（）;中. 该方法使用递归遍历，第二个是上面的for循环. 那如果我想在倒计时后删除两个元素怎么办？两次调用此方法就足够了，但是此操作非常有缺陷，并且极大地浪费了性能.

双向链表恰好改善了这部分缺陷. 它使用双节点形式来存储元素信息的前后，因此可以减少一次迭代. 请参阅我的下一篇文章，以了解双向链表的实现代码！

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-202292-1.html