前言❤️❤️
hello hello💕，这里是洋不写bug~😄，欢迎大家点赞👍👍，关注😍😍，收藏🌹🌹 上篇博客解析了顺序表的使用，顺序表有两大局限性 空间利用率低（创建后会申请一块数组空间，可能存储的数据用不完这块空间） 在中间插入元素时，需要进行搬运，效率低 这篇博客要解析的链表，就能很好的解决这两个问题 这个专栏的数据结构是代码都是用Java来写的，JavaSE专栏现在已经全部更新完成，铁汁们复习基础知识时非常推荐使用，可以试一下💪💪💪 
🎇个人主页：洋不写bug的博客 🎇所属专栏：数据结构专栏 🎇复习Java基础知识：Java学习之旅，从入门到进阶 🎇铁汁们对于数据结构基础的各种核心知识（不太常用的也有😆），都可以在上面的数据结构专栏学习，专栏正在持续更新中🐵🐵，有问题可以写在评论区或者私信我哦~
1，链表简介
- 顺序表的底层是数组，存储空间需要是连续的，而链表则没有这个要求，可以存储在离散的空间上
-
- 那既然空间是离散的，如何知道链表中有哪些元素，又如何遍历链表中的元素呢？ 在链表中，每个节点上面都引入了一个引用变量，称为"next"，使用这个引用保存下一个元素对应的内存地址，最后一个元素这个引用变量的值就是null
-
2，链表的分类
链表有两个特点：
- 空间分布是离散的
- 每个元素都记录了下个元素的地址
- 链表的每个元素也称为节点，对于链表，只要知道了第一个元素，后续整个链表就都能拿到了，因此，习惯上也用第一个节点代指整个链表
-
链表其实有很多种分类：
- 单向还是双向
- 带不带头节点（傀儡节点）
- 是不是循环的
-
单向和双向
- 前面提到的链表，每个节点存储了下一个节点的地址，知道一个中间节点，可以找到下个节点，是找不到上个节点的，这种链表就是单链表，日常使用最多的链表就是这种
- 还有双向链表，也就是每个节点上有两个引用：next和prev，存储了上个节点和下个节点的地址，知道一个节点，可以同时找出它的上下节点；双链表的功能自然是更强大，但是消耗的空间也更多了
-
带不带头节点
- 这个说法只是《数据结构》教材中规定这样，对于编程，是不严谨的也不好理解的，头节点的意思我们理解应该是“链表的第一个节点”，所有链表应该都有呀 《数据教材》这里说的有没有头节点，严格来说是有没有傀儡节点
- 傀儡节点不存储数据，在链表的最前面，只是用来占个位子，来简化代码的书写（为什么能简化铁汁们后面编程就能体会到）
- 前面提到，一般用链表的第一个节点代表整个链表，一般通过head引用指向第一个节点，现在有个储存了1、2、3、4的链表，如果head引用拿到的节点是元素1，那这个链表就不带傀儡节点
-
- 如果head引用拿到的节点不是元素1，这个节点的next才是元素1，那这个链表就带傀儡节点
-
是不是循环的
- 这个非常简单，如果最后一个节点指向null，那链表就是非循环的；如果最后一个节点指向第一个节点，那这个链表就是循环链表（循环链表就算一直next，也不会报错，因为到最后一个节点又会绕回来）
-
这三种特征看起来能排出9种链表组合，经常使用的也就两种：
- 笔试面试中：单向，不带傀儡，不循环的链表
- 实际开发中：双向，不带傀儡，不循环的链表
-
3，链表方法
链表的集合类是LinkedList，跟ArrayList都是实现了List接口，所以部分方法是通用的（例如插入都用add，删除都用remove）
1，增
- add方法插入元素，在链表中就是尾插，还可以传入参数，前面是下标，后面是元素，这里传入1和4，就是往下标为1元素前插入4（插入完成后，新插入的元素的下标就是1）
- import java.util.LinkedList;
import java.util.List;public class Test {
public static void main(String[] args) {
List<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(1,4);
System.out.println(list);
}
}
- 还有addFirst和addLast方法，就是头插和尾插，但是这里尝试调用是没有的，因为这些方法是LinkedList特有的，在List接口中是没有的，在编译阶段只看左边声明的类型 List，识别不到有这个方法
-
- 如果想要使用这些LinkedList特有的方法的话，需要在创建引用的时候把引用的类型设定为LinkedList（addLast方法和add方法的效果是完全一样的，都是尾插）
- import java.util.LinkedList;
public class Test {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.addFirst(100);
list.addLast(200);
System.out.println(list);
}
}
2，删
- remove方法传入基础数据类型，就是按下标来删除，传入包装类，就是按照元素的值来删除
- import java.util.LinkedList;
public class Test {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.remove(0);
System.out.println(list);
list.remove(Integer.valueOf(3));
System.out.println(list);
}
}
- LinkedList中有特定的尾删和头删方法，removeFirst和removeLast
- import java.util.LinkedList;
public class Test {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.removeFirst();
list.removeLast();
System.out.println(list);
}
}
3，改
set和get方法就是传入下标，按下标去读取元素或者修改元素
import java.util.LinkedList;
public class Test {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
System.out.println(list.get(0));
list.set(2,100);
System.out.println(list);
}
}
4，查
- 通过contains来判断元素是否存在，存在就返回true，否则就返回false 还可以通过indexOf方法，查到就返回元素下标，查不到就返回-1
- import java.util.LinkedList;
public class Test {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
System.out.println(list.contains(3));
System.out.println(list.indexOf(2));
}
}
5，遍历
遍历可以使用迭代器，和顺序表的使用方法相同
import java.util.Iterator;
import java.util.LinkedList;public class Test {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
}
}
- 因为链表跟顺序表使用了同一个接口，因此顺序表的方法链表基本上都能用，比如clear()方法清空链表，.size()方法统计长度等，这里就不再赘述了
-
4，链表的模拟实现
上篇博客顺序表的模拟实现，更改操作都是在数组上进行的，比较简单，链表的模拟实现就会稍微复杂一些，这里我们模拟实现就不用泛型了，就实现个String类型的链表即可
- 链表的一个节点里存储了数据信息和下个节点的引用，建一个Node类来表示链表中的节点，属性为value和next（这个next就是下个节点的引用，是Node类型），构造方法是传入value，把next默认设置为null
- public class Node {
public String value;
public Node next;public Node(String value) {
this.value = value;
this.next = null;
}
} - 我们自己实现的这个链表设定为没有傀儡节点，定义一个头节点head，头节点如果为null的话，那就说明整个链表就是空的（链表是不需要像顺序表那样搞个size来表示数组中的有效区间）
- public class MyLinkedList {
private Node head = null;
} - addFirst方法，参数传入String类型value，根据这个value来创建节点，那节点的next引用如何修改就需要画图来分析下（这里博主就拿数字类型的链表来举例，原理是一样的），最初head指向第一个元素，如下图：
-
- 这时候如果想要插入一个新的节点newNode，其实特别简单，无非就是两步操作，第一步，让newNode指向原来head指向的节点（也就是原链表的第一个节点）；第二步，让head指向newNode，这个newNode就成了新的头节点 注：第一步和第二步的顺序是不能颠倒的，如果先用head指向newNode，那原链表就相当于找不到了，Java的垃圾回收机制会把没有引用指向的链表给删除掉
- public void addFirst(String value){
Node newNode = new Node(value);
newNode.next = head;
head = newNode;
} - 如果使用addFirst的时候，链表是空的，这时候head指向null，newNode就相当于是链表中的第一个节点，依然是按照这两步来操作（newNode这时候是链表中的最后一个节点，最后一个节点就是要指向null）
-
- 写完后在main方法中测试下，虽然还没有重写toString方法，可以在最后的打印语句那里打上断点，调试一下，在调试窗口看一下这些节点的信息
-
- 重写toString方法，先创建一个StringBuilder类型的可变字符串，往里面添加元素，顺序表是通过数组下标来获取每个元素的，链表这里就需要通过节点的引用来获取元素 同样写个for循环，链表的节点每次向后走一步，直到链表的节点为空
- @Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("[");
for(Node cur = head;cur != null;cur = cur.next){
stringBuilder.append(cur.value);
if(cur.next != null){
stringBuilder.append(",");
}
}
stringBuilder.append("]");
return stringBuilder.toString();
} - 重写后在main方法中打印，就能打印出所有元素了
- addLast方法，就是在链表中进行尾插，那关键一步就是找到链表的尾节点，如何找呢，就是从head开始，一直往后next，直到再next为null，那就找到尾节点了
-
- 这样写，铁汁们在main方法中测试addLast方法的话，就会发现：如果链表中有元素的话，这个方法是能正常使用的；如果链表本身是空的，再使用这个方法，就会报错
- public void addLast(String value){
Node tail = head;
for(;tail.next != null;tail = tail.next){
}
Node newNode = new Node(value);
tail.next = newNode;
}public class Test {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addLast("a");
System.out.println(myLinkedList);
}
}
- 当链表为空时，head引用就是null，这时候tail就也是null，tail就不会进入for循环，直接tail.next = newNode，也就相当于是null.next = newNode，null`代表 “不存在的对象”，没有任何属性和方法，因此这里就会报错
- 更正代码，就是当tail的值为null时，按照addFirst那套进行操作，这样当链表为空时进行addLast就不会报错了
- public void addLast(String value){
Node newNode = new Node(value);
if (head == null){
newNode.next = head;
head = newNode;
return;
}
Node tail = head;
for(;tail.next != null;tail = tail.next){
}tail.next = newNode;
} - add方法里面可以传入下标和元素，也就是在该下标节点前插入新的节点，在链表中其实是没有下标的概念的，只是Java标准库中的LinkedList和ArrayList都实现了List接口，所以也引入了下标的概念
- 按照下标插入元素，首先要知道链表的元素个数，因为写合法性校验时必须用到，那就写个size()方法，用来统计元素的个数
- public int size(){
int size = 0;
for(Node cur = head;cur != null;cur = cur.next){
size++;
}
return size;
} - add方法是在指定下标的元素前进行首插，先分析这个元素要插在链表中间的情况，例如newNode要插到cur节点的前面，cur节点的上个节点原来是prev，如下图 操作分为两步：第一步，让newNode节点指向cur节点；第二步，让prev节点指向newNode节点（这两步的执行顺序也是不能改变的，如果先用prev节点指向newNode节点，那也就没有引用指向cur节点了，cur节点和cur节点后面的数据就丢失了）
-
- 分析清楚后，来写代码，首先进行index的合法性校验（index是可以等于size的，这样就相当于针对链表的最后一个元素进行尾插） 接着就是先找到prev的位置，这样cur也就找到了，按照前面分析的两步来操作，就完成了节点的插入
- public void add(int index,String value){
if(index < 0 || index > size()){
throw new IndexOutOfBoundsException("index：" + index + "，Size：" + size());
}
Node prev = head;
for(int i = 0;i < index – 1;i++){
prev = prev.next;
}
Node cur = prev.next;
Node newNode = new Node(value);
newNode.next = cur;
prev.next = newNode;
} - 接着考虑下特殊情况，index的值为0或者size()的情况
- 当index的值为size()的时候，这时候prev就是链表中最后一个节点，cur就是null，前面写的代码是包括这种情况的
- 当index的值为0时，这时候就没有prev了，就直接按照addFirst的操作来写即可，完整方法如下：
- public void add(int index,String value){
if(index < 0 || index > size()){
throw new IndexOutOfBoundsException("index：" + index + "，Size：" + size());
}
Node newNode = new Node(value);
if(index == 0){
newNode.next = head;
head = newNode;
return;
}
Node prev = head;
for(int i = 0;i < index – 1;i++){
prev = prev.next;
}
Node cur = prev.next;
newNode.next = cur;
prev.next = newNode;
} - contains方法，也就是判断一个元素在链表中是否存在，把链表遍历，比对一遍即可
- public boolean contains(String value){
for(Node cur = head;cur != null;cur = cur.next){
if(cur.value.equals(value)){
return true;
}
}
return false;
} - indexOf方法，查找元素，查找到就返回下标，查找不到就返回-1
- public int indexOf(String value){
int index = 0;
for(Node cur = head;cur != null;cur = cur.next){
if(cur.value.equals(value)){
return index;
}
index++;
}
return –1;
} - remove方法，删除链表中的节点，里面传入int类型就是按照下标来删除节点，先分析删除的节点位于链表中间的情况，删除操作特别简单，如果要删除某个节点，直接让这个节点的上个节点指向这个节点的下个节点即可
- 如下图，prev的引用指向下个节点后，也就没有节点指向需要删除的节点了，那根据Java的垃圾回收机制，这个节点就会被自动释放掉
-
- 写代码的时候，在index合法性校验这里，index的值就不能等于size()了，因为这是删除元素，在链表中最大的下标是到index – 1的 接下来就是定位prev，然后改一下prev的指向即可
- public void remove(int index){
if(index < 0 || index >= size()){
throw new IndexOutOfBoundsException("index：" + index + "，Size：" + size());
}
Node prev = head;
for(int i = 0;i < index – 1;i++){
prev = prev.next;
}
prev.next = prev.next.next;
} - 如果要删除的链表尾部的元素，那prev.next.next = null，接着把prev.next改为null，这时候prev就成最后一个元素了 如果删除链表头部的元素，其实也特别简单，直接让head指向head的下一位即可，完整方法如下：
- public void remove(int index){
if(index < 0 || index >= size()){
throw new IndexOutOfBoundsException("index：" + index + "，Size：" + size());
}
if (index == 0){
head = head.next;
return;
}
Node prev = head;
for(int i = 0;i < index – 1;i++){
prev = prev.next;
}
prev.next = prev.next.next;
} - 还有在remove方法中传入value，按照元素来删除，首先判断下，如果要删除的是头节点的话，就直接head = head.next
- 确定删除的不是头节点，那就需要遍历链表，需要找到待删除节点的前一个节点的位置prev，然后直接prev = prev.next.next
- 我们不妨直接写个prev的for循环，因为比较的prev.next的value和传入的value是否相等，当prev走到链表最后一个节点时，就已经遍历完成了（如下图）,for循环的条件就为prev.next != null
-
- 传入value比较时，当链表为空时，就直接返回，否则代码中用到null.next就会报错
- public void remove(String value){
if(head == null){
return;
}
if(head.value.equals(value)){
head = head.next;
return;
}
Node prev = head;
for(;prev.next != null;prev = prev.next){
if(prev.next.value.equals(value)){
prev.next = prev.next.next;
break;
}
}
} - 清空链表操作，直接让head = null，没有引用指向链表头节点时，垃圾回收机制就会把链表内存释放掉（没有引用指向头节点，头节点内存释放，头节点内存释放后，没有引用指向头节点的下个节点，头节点的下个节点内存也被释放掉，以此类推）
- public void clear(){
head = null;
}至此，我们完成了自己的模拟链表（链表常用的方法都模拟实现了🐵💪）
结语
- 链表的模拟实现是比顺序表要稍微复杂一些的，对于一些复杂的情况，还需要画图来分析
- 有关链表的算法题（下篇博客会进行解析）大部分也都需要画图分析，模拟实现链表能够提高解决链表算法题的能力，
-
以上就是今天的所有内容啦～完结撒花～🥳🎉🎉
