什么是链表？
定义：链表是一种物理存储单元上非连续、非顺序的存储结构，元素的逻辑顺序是通过链表中的指针链接次序实现的
以上定义拆分来看
1.数据元素在内存上是离散的
2.数据元素的内存在逻辑上是关联的，通过指针
.如上图 每一个element的内存都是离散的，但是他们之间能通过指针p连接起来。
单向链表
单向链表顾名思义肯定是顺着一个方向，上图为单向链表的结构图，一个结点有两部分组成，data和next，data存储的是数据元素，next存储的是下个结点的地址。
还有一点需要注意，单项链表还有个head指针，其实也可理解为就是申明链表时的变量，其存储的值就是单向链表头结点的地址。这应该很好理解，我们只需要只要头结点地址，其他任何位置的元素我们都能找到。
相信说到这里，我们都能对单向链表是什么有个概念。接下来我们手写一个简单的单向链表
结点结构
上面这段代码就是一个结点的结构，data可以存储类型，next指向下一个节点，关于其增删改查在这里我就用一段逻辑体现一下大概添加的步骤。
逻辑伪代码如下
这里就简单介绍了增加一个元素的简单逻辑，关于单链表的至于具体的实现就不贴出来了，主要因为截图截不全还麻烦...
双向链表
下面我们介绍一下双向链表
从上面的单向链表中我们可以推测出双向链表的结构，就是多了一个方向而已
一个结点结构分为三部分，上一个结点地址、数据元素、下一个结点地址。代码表示大概如下
下面只要把结点连接起来 就是一个双向链表结构了。关于双向链表的知识，还是一起看一下LinkedList的源码
LinkedList源码
结点结构
添加元素的方法我们主要看三种，表头添加，中间插入，表尾添加
表头插入
表尾插入
这两个我就不介绍了，我们着重介绍一下中间插入
这是一个插入流程，主要看linkBefore()，我们要根据一个index插入元素，肯定是插入在原本这个位置的元素之前。
逻辑图
原则：我们插入的时候要遵循着 先连后断，我们可以看到在linkBefore()方法中初始化newNode的时候连接就已经完成了，后面的逻辑就是3，4两步断开过程。
在增删改查的过程中 如果看懂了增加的方法，其他的都相对较简单，就不再一一介绍了
网友评论