链表 - 单向链表、双向链表 - LinkedList

什么是链表？

定义：链表是一种物理存储单元上非连续、非顺序的存储结构，元素的逻辑顺序是通过链表中的指针链接次序实现的

以上定义拆分来看

    1.数据元素在内存上是离散的

    2.数据元素的内存在逻辑上是关联的，通过指针

.如上图 每一个element的内存都是离散的，但是他们之间能通过指针p连接起来。

单向链表

单向链表顾名思义肯定是顺着一个方向，上图为单向链表的结构图，一个结点有两部分组成，data和next，data存储的是数据元素，next存储的是下个结点的地址。

还有一点需要注意，单项链表还有个head指针，其实也可理解为就是申明链表时的变量，其存储的值就是单向链表头结点的地址。这应该很好理解，我们只需要只要头结点地址，其他任何位置的元素我们都能找到。

相信说到这里，我们都能对单向链表是什么有个概念。接下来我们手写一个简单的单向链表

结点结构

上面这段代码就是一个结点的结构，data可以存储类型，next指向下一个节点，关于其增删改查在这里我就用一段逻辑体现一下大概添加的步骤。

逻辑伪代码如下

这里就简单介绍了增加一个元素的简单逻辑，关于单链表的至于具体的实现就不贴出来了，主要因为截图截不全还麻烦...

双向链表

下面我们介绍一下双向链表

从上面的单向链表中我们可以推测出双向链表的结构，就是多了一个方向而已

一个结点结构分为三部分，上一个结点地址、数据元素、下一个结点地址。代码表示大概如下

下面只要把结点连接起来  就是一个双向链表结构了。关于双向链表的知识，还是一起看一下LinkedList的源码

LinkedList源码

结点结构

添加元素的方法我们主要看三种，表头添加，中间插入，表尾添加

表头插入 表尾插入

这两个我就不介绍了，我们着重介绍一下中间插入

这是一个插入流程，主要看linkBefore()，我们要根据一个index插入元素，肯定是插入在原本这个位置的元素之前。

逻辑图

原则：我们插入的时候要遵循着 先连后断，我们可以看到在linkBefore()方法中初始化newNode的时候连接就已经完成了，后面的逻辑就是3，4两步断开过程。

在增删改查的过程中 如果看懂了增加的方法，其他的都相对较简单，就不再一一介绍了