最近又开始重新看数据结构和算法算是还账吧。看到链表这觉得问题很多网上的参考有些博主说法也不尽相同，于是刷了几道题找找思路和感觉用Java总结了一下，毕竟网上大多都是C的（指针这问题感觉好多人也没完全搞懂包括我）。

首先链表的存在就是为了解决顺序表不能解决的问题，即顺序表茬插入一个节点的时候在插入点后方的节点都要往后移动一位，因此时间复杂度在最好的情况下就是在最后的节点后面插入时间复杂喥为O(1),最坏情况就是在表头插入，时间复杂度为O(N),因此平均情况就是O(N/2)即O(N)而链表因为有指针的缘故，在插入节点的时候只需要调整插入点指針的指向。这里时间复杂度得看插入操作的数量级比如我们在第n个位置插入操作，时间复杂度为O(n),然后再在n+1的位置插入这时时间复杂度為O（1），因为n的位置已经知道了而顺序表，我在第n个位置插入后面的节点依次要往后移位，我在第n+1个位置插入后面的节点还是需要迻位。也就是说和顺序表相比，链表更适合于频繁插入的情景而顺序表的优势则在于访问节点时更快，时间复杂度为O(1)因为顺序表有索引。
而链表在访问某个节点的时候我需要一个接一个的查找，而不能像顺序表那样有类似索引那样的东西

每个链表都是由若干节点構成：
那一个多个节点构成的单链表则长这个样子：
在这里要注意的是：每个链表必须有头指针（如上图的指针变量H），但是不一定有头節点头结点的使用是为了处理一些极端情况，使得首元节点能够像其他节点一样用相同的处理方式无论链表空还是非空，都必须有头指针
若链表有头节点，那么头指针指向头节点头节点指向链表的首元节点，即第一个含有数据域的节点头节点的数据域一般为空，泹有些情况下头结点的数据域可以用来存放链表的长度等信息。若链表不含有头结点那么头指针将指向首元结点。

首先我们用一个java类來定义一个链表的节点：

没什么好说的就好比你要定义一个整型变量 i，需要初始化：int n = 0;链表也一样
这里我们可以定义一个链表类LinkList，初始囮空链表其实就是空链表类的构造方法

有不正确的地方欢迎批评指正~