链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。
1.单向链表
单向链表，它包含两个域，一个信息域和一个指针域。信息域用来存储链表中要存放的值，指针域则指向下一个节点。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。其结构图如下：
2、双向链表
双向链表在单链表的基础上，每个节点新增了一个指针域，用来指向前一个节点。其结构图如下：
首先创建一个LinkedList类。
0.链表节点的对象
1.头插法
2.任意位置插入节点
insert方法为在任意位置插入节点，参数中的index为插入节点的位置，val为插入节点的值，如果index等于0，则和头插法过程相同。否则，需要先找到前一个节点， 将该节点的next指针指向前一个节点next指向的节点，然后再将前一个节点指向该节点。
插入过程图解如下：
（1）创建要插入的节点对象
（2）current节点指向next节点
（3）previous节点指向current节点，完成插入
3.尾插法
先找到原先最后一个节点，然后将其next指向要插入的节点即可。
4.删除第index个元素
找到第index-1个节点，将其直接指向第index+1个节点即可。需要注意空链表或者越界情况。
删除过程图解如下：
（1）找到要删除的节点对象current
（2）previous指针指向next节点即可删除。
5.删除val元素
删除值为val的节点，以此遍历找到值为val的节点，并对其删除即可。
6.获取第index节点的值
遍历找到即可。
7.将第Index个节点的值修改为val
找到第index节点，修改val即可。
8.创建一个链表
9.按顺序打印链表
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.bianchenghao6.com/java-jiao-cheng/6173.html