java单向链表和双向链表浅析

读到了这篇文章,写的很清晰明了,摘抄下了一些自认为比较清晰明了的部分,然后整理了一下

何为链表

链式结构是一种使用对象引用变量来创建对象间的链的数据结构。
对象引用变量可用于创建链式结构
对象引用变量所存储的特定地址一般无关紧要。换句话说，重要的是能够使用引用变量来访问对象，而对象在内存中的特定存储位置并不重要。因此，我们一般将引用变量描述为一个“指向”对象的名称，而不是显示其地址，按照这种理解，引用变量有时称为“指针”,我个人理解为内存的地址值

//这就是一个链式结构
public class Person {
    private String name;
    private String address;
    private Person next;    // Person对象的引用
}

这种类型的对象有时称为自引用对象。
这种关系构成了链表的基础。链表是一种链式结构，该结构中的每个对象都指向下一个对象，从而构成了链表中对象的线性次序。。链表中存储的对象一般称为链表的节点。

image.png

注意，链表单独需要一个引用变量，用以表示其第一个结点。如果某个结点的next引用为null，则表示链表在该结点处终止

实现一个单向链表

插入结点

可能会在链表的任何位置插入一个结点：在链表的首部，或在链表中任何内部结点之间，或在链表的尾部。
（1）在首部插入结点
第一步，设置所添加结点的next引用，使其指向链表中当前的第一个结点。
第二步，重新设置指向链表首部的引用，使其指向这个新添加的结点。

image.png

在链表的首部插入一个结点
注意：如果上述这些步骤颠倒了，则将会遇到困难。如果首先重置front引用，则将失去这个唯一指向现有链表的引用，而且再也不能获取它。

（2）在其他部分插入结点
首先，设置新节点的next引用，使其指向current锁引用结点的下一个结点。然后，重新设置当前结点的next引用，使其指向这个新的结点。

在链表的中部插入一个结点

image.png

删除结点

对链表中的第一个结点的处理一般也比较特殊。
要删除链表的第一个结点，则要重新设置指向链表首部的引用，使其指向链表中当前的第二个结点。
删除链表的第一个结点

image.png

一旦找到索要删除的结点，则重新设置前一个结点的next引用，使其指向的结点与当前结点的next引用所指向的结点相同。然后，可以根据需要使用这个删除的结点。

删除链表内部结点

image.png

实现一个双向链表

双链表（双向链表）：双链表和单链表相比，多了一个指向尾指针（tail），双链表的每个结点都有一个头指针head和尾指针tail,双链表相比单链表更容易操作，双链表结点的首结点的head指向为null，tail指向下一个节点的tail;尾结点的head指向前一个结点的head，tail 指向为null，是双向的关系；

image.png