链表

链表基础理论

什么是链表，链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。

链表的入口节点称为链表的头结点也就是head。

链表的类型

单链表

单链表每个节点只能指向下个节点且有头有尾

双链表

每个节点有两个指针域，一个指向下个节点，一个指向上个节点。

双链表既可以向前查询也可以向后查询。

循环列表

循环列表，顾名思义，就是链表收尾相连。

循环链表可以用来解决约瑟夫环问题。

链表的储存放肆

了解完链表的类型，在说说链表在内存中的储存方式。
数组是在内存中是连续分布的，但是链表在内存中不是连续分布的。

链表是通过指针域的指针链接在内存中各个节点。

所以链表中的节点在内存中不是连续分布的，而是散乱分布在内存中的某地址上，分配机制取决于操作系统得到内存管理。

链表的定义

接下来说说一说链表的定义。

链表节点的定义，很多同学在面试的时候都写不好。

这是因为平时再刷力扣的时候，链表的节点都默认定义好了，直接用就行了，所有同学们都没有注意到链表节点是如何定义的。

在面试的时候，一旦要自己写链表，就写的漏洞百出。

定义链表的方式：
golang：

type ListNode struct {
    Val int
    Next *ListNode
}

链表的操作

删除节点

有个一个A->C->D->E的链表

删除D节点只需要将C的next指向E就行了。

那有同学说了，D节点不是依然还存在内存里么？只不过没在这个链表里而已。

是这样的，所有在C++里最好是在手动释放这个D节点，释放这块内存。

其他语言例如JAVA、GOALNG就有自己的垃圾回收机制，就不用自己手动释放了。

添加节点

有个一个A->C->D->E的链表

添加F到CD中间只需要将，C的下个指向F，F的下一个指向D就可以了。

可以看出链表的添加和删除都是O(1)操作，也不会影响到其他节点。

但要注意的是，要是删除最后一个节点，需要从头节点查找到倒数第二个节点进行删除操作，操作的时间复杂度是O(n)。

性能分析

在吧链表的特性和数组的特性进行一个对比

数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要从新定义个新数组。

链表的长度可以是不固定的,并且可以动态增删，适合数据量不固定，频繁增删，查询较少的场景。

相信大家已经对链表足够的了解，后面我会讲解关于链表的高频面试题目，我们下期见.