数据结构：链表（1）

顺序表的优缺点

缺点：

1.插入数据必须移动其他数据，最坏情况下，就是插入到0位置。时间复杂度O(N)

2.删除数据必须移动其他数据，最坏情况下，就是删除0位置。时间复杂度O(N)

3.扩容之后，有可能会浪费空间。

优点：

在给定下标进行查找的时候

总结：顺序表比较适合进行给定下路查找的场景

🆗链表可以完美解决顺序表的缺点

---

链表是什么？

一个链表其实就是一辆火车

火车的每个车厢相当于一个节点，链表节点长这样

其中，数据域存储数据 

而火车之间要有挂钩链接，这就需要next域出马了，next读取下一个节点的地址并把它记录在next域里面，下面这个图也是单向链表，一条路走到黑

分类

有六种分类

常见的是红色圈起来的两个

带头的长啥样？头部存的数据是无效的，跟这个链表没有关系，这个头节点的值永远不会改变

循环的？

双向的？两边都能走

链表结构特点：物理上不一定是连续的，但逻辑上是连续的

---

单向链表

手搓一个

初始化

实现方法有下面这些

//IList.java 接口
public interface IList {//头插法void addFirst(int data);//尾插法void addLast(int data);//任意位置插入,第一个数据节点为0号下标void addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中boolean contains(int key);//删除第一次出现关键字为key的节点void remove(int key);//删除所有值为key的节点void removeAllKey(int key);//得到单链表的长度int size();void clear();void display();
}

再新建一个模块重写这些方法

public class MySingleList implements IList{@Overridepublic void addFirst(int data) {}@Overridepublic void addLast(int data) {}@Overridepublic void addIndex(int index, int data) {}@Overridepublic boolean contains(int key) {return false;}@Overridepublic void remove(int key) {}@Overridepublic void removeAllKey(int key) {}@Overridepublic int size() {return 0;}@Overridepublic void clear() {}@Overridepublic void display() {}
}

ok！接下来我们要设置一个节点的内部类把要用到的属性加上

    static class ListNode{public int val;public ListNode next; //定义next域//节点类构造方法public ListNode(int val){this.val = val;}}

为什么是static呢？因为每个节点都一样，都由数据域和next域组成的，直接static定义共同特点。

那第三行的ListNode next 怎么理解呢？因为next指向的是下一个节点的地址，而下一个节点的类型也是ListNode，所以这里的next一定是ListNode类型

---

好接下来定义一个链表的头

public ListNode head;

注意不要放到内部类里面，因为head是链表的成员而不是节点的成员

给几个节点赋上值

1.如何让node1的下一个节点是node2

node1.next = node2 //表示node2地址0x46给到node1

node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;

node1是局部变量，整个过程走完之后node1会被回收怎么办？

两种方法：

第一种，把刚刚那个函数类型改成ListNode，函数返回node1

第二种，我们不是定义了head了吗，直接在函数末尾写上

this.head = node1;    这样就行了

检验结果

---

遍历列表

1.怎么从一个节点走到下一个节点

2.怎么判断所有节点都遍历完了

一个循环，循环终止条件是head为空，我们按照这个思想把display代码完成

这个代码有一个问题，遍历完列表之后head为空，整个头节点地址和值全都无了

解决办法是创一个中间变量cur把head锁死，遍历完之后cur为空了，但是head本质上不会变

    @Overridepublic void display() {ListNode cur = this.head;while(cur != null){System.out.println(cur.val + " ");cur = cur.next;}}

有这个代码的基础，链表长度和包含函数也不在话下

    @Overridepublic int size() {int count = 0;ListNode cur = this.head;while(cur != null){cur = cur.next;count++;}return count;}@Overridepublic boolean contains(int key) {ListNode cur = this.head;while(cur != null){if(cur.val == key){return true;}cur = cur.next;}return false;}

---

头插法

链表里面有节点

三步走

1. 实例化一个节点

2.改变插入节点的next

3.改变head

无节点

直接把head定义成这个节点

    @Overridepublic void addFirst(int data) {//实例化节点对象ListNode node = new ListNode(data);//无节点if(this.head == null){this.head = node;//有节点}else{node.next = this.head;this.head = node;}}

注意这个插入是倒叙插入 

---

尾插法

指的是将待插入的节点存放到链表的最后一个位置

步骤：

1.实例化一个节点

2.把cur走到最后一个节点

3.cur.next = node; //插入下一个节点

    @Overridepublic void addLast(int data) {ListNode node = new ListNode(data);ListNode cur = this.head;if (this.head == null){this.head = node;}else {//找到尾巴while (cur.next != null) {cur = cur.next;}//cur现在指向最后一个节点cur.next = node;}}

如果想要让cur停在最后一个节点的位置 cur.next != null;

如果想把整个链表都遍历完，就是cur != null;

注意：尾插法时间复杂度是O(N)，因为要遍历完整个链表n个节点后才插入元素

---

在任意位置插入节点

1.让cur走index-1步

2.node.next = cur.next;

cur.next = node;

在插入一个节点的时候，一定要先绑定后面这个节点

    @Overridepublic void addIndex(int index, int data) {if(index < 0 || index > size()){return;}if(index == size()){addLast(data);return;}ListNode cur = searchPrev(index);ListNode node = new ListNode(data);node.next = cur.next;cur.next = node;}private ListNode searchPrev(int index){ListNode cur = this.head;int count = 0;while(count!=index-1){cur = cur.next;count++;}return cur;}

---

删除元素

现在我们想删除第三个节点，把第三个节点设成del

在一个循环里面让cur遍历整个链表

判断 cur.next.val == key，找到cur的位置

后面cur = cur.next

    @Overridepublic void remove(int key) {if(this.head == null){//一个节点都没有，删除不了return;}//删除头节点if(this.head.val == key){this.head = this.head.next;return;}//1、找到前驱ListNode cur = findPrev(key);//2、判断返回值是否为空？if(cur == null){System.out.println("没有你要删除的数字");return;}//3、删除ListNode del = cur.next;cur.next = del.next;}//找到关键字key的前一个节点的地址private ListNode findPrev(int key){ListNode cur = this.head;while(cur.next!=null){if(cur.next.val == key){return cur;}}return null;}

---

删除所有值为key的节点 

比如下面删除所有值为23的节点

定义cur为当前要删除的节点

prev为当前要删除的节点的前驱

cur找到了就直接把prev的next地址改成cur下一个节点的地址，cur继续往下遍历

while(cur!=null){

        if(cur.val == key){

                prev.next = cur.next; //删除操作

                cur = cur.next;

        }else{

                prev = cur;

                cur = cur.next

        }

}

    @Overridepublic void removeAllKey(int key) {if(this.head == null){return;}ListNode prev = head;ListNode cur = head.next;while(cur!=null){if(cur.val == key){prev.next = cur.next;cur = cur.next;//不等于就往下走}else{prev = cur;cur = cur.next;}}if(head.val == key){head = head.next;}}

---

清空链表

把一个节点的val = null, next = null

再把链表的head = null

注意：这里的val = null不是直接让你 cur.val = null，拿第一个节点来说，如果你把值置为空，那么0x46被替换成null，cur找不到下一个节点的地址0x46了

我们可以拿一个变量curNext来记录cur下一个节点的位置，把cur.next 置为空之后，cur往后挪到curNext的位置，继续置空下一个节点

注意别忘了头节点，整个遍历完之后还要把头节点也置为空

    @Overridepublic void clear() {ListNode cur = this.head;while(cur!=null){ListNode curNext = cur.next;cur.next = null;cur = curNext;}head = null;}