- 重要！
- 一、ArrayList的缺陷
- 二、链表
- 1. 链表的概念及结构
- 2. 链表的实现（无头单向非循环）
- 三、链表面试题
- THINK
重要！
努力不一定成功 但是不努力一定不会成功！
学习链表一定要画图！！！！
加油呀！每天进步一点点
一、ArrayList的缺陷ArrayList的底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此：ArrayList不适合做任意位置插入和删除比较多的场景。
so：java集合中又引入了LinkedList，即链表结构。
- 小结：ArrayList底层是连续空间，插入/删除元素时时间复杂度为O(n)。
- 数据元素之间以链式的方式进行存储，物理存储上不一定是紧挨在一起的。
- 链表：物理上不一定连续，但是逻辑上一定是连续的。
- 注意：
- 顺序表在逻辑上是连续的，在物理上也是连续的。
（底层是数组） - 链表在物理上不一定连续，但是逻辑上连续。
- 书面概念：链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
- 有8种链表结构，主要学习掌握两种就行。
（8种链表结构就是以下3个任意组合：单向和双向、带头和不带头、循环和非循环）
- 单向不带头非循环（考试重点）：无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
- 双向不带头非循环（LinkedList底层是这样子的）
- 带头和不带头的区别：带头的会永远标识头结点的位置（不变）；不带头的会随结点的值是否存在而改变。
- 定义结点时常用的变量：
- val：当前结点的值 next：下一结点的地址
- head：存第一个结点的地址
- 定义类型Node：含有变量val、next
（此时所写的是无头单向非循环的链表的实现）
- 代码主要关注点：
- 头插法：时间复杂度O(1)
头插法：修改头结点的指向：node.next=head; head = node;即：先绑住后面！- 尾插时间复杂度O(N)
尾插法：头节点是否为空的判断- 自定义类型的值是地址！！ -Node是自定义类型，所以在用该类型变量直接赋值时赋值的是变量的地址！
- 链表的遍历：head = head.next;
while(this.head != null)
// 最好加this
// 一般定义一个局部/临时变量，让局部变量动而head不动！- 位置插入：判断是否为头尾插，如果不是则找到插入前元素，指向要插入的元素地址，然后再指向原本的地址节点
此时写一个方法进行前一个结点的下标的寻找，并返回该结点- 删除第一次出现key的节点：找到该结点，并且该节点的前一节点直接指向后一节点
写一个方法找到关键字key的前驱：cur = this.head; 然后进行循环；
考虑头结点即要删除的节点的情况- 删除所有值为key的节点：在头结点不是null的条件下设置两个结点：cur=head.next; prev=head; （如果是null就直接进行return）
if(cur.val==key) prev=cur.next; cur=cur.next;
else prev=cur; cur=cur.next;
但是这些都在一个while循环中进行实现的while(cur!=null)
单独处理头结点问题（注意一定要放到最后！！！
不然会存在改变后的头结点依旧是key值的问题）:
即如果头结点就是key
注意一个：Node node= new Node(-1); // 注意该
方法插入属于头插还是尾插
- 代码如下：
- Node.java
public class Node {
public int val; // 存储实际值
public Node next; // 存储下一个结点的地址 是自定义类型！！！（因为赋值时赋值的是结点
// 创建一个构造方法
public Node(int val) {
this.val = val;
}
}
- IndexException.java
public class IndexException extends RuntimeException { // 非受检异常
public IndexException() {
}
public IndexException(String message) {
super(message);
}
}
- SingleLinkedList.java
// 无头单向非循环链表模拟实现
// 注意 任意位置插入（√）、清空操作 以及 删除关键字（单个√）、（all√）
// 1、无头单向非循环链表实现
public class SingleLinkedList {
public Node head; // 定义头结点
public void createList() {
//通过穷举的方式 创建一个链表出来
Node node1 = new Node(8);
Node node2 = new Node(2);
Node node3 = new Node(1998);
node1.next=node2;
node2.next=node3;
head = node1; //注意该赋值方式：相当于把next赋值，赋值后指向node1，但是val不赋值，默认值just
}
//头插法: 时间复杂度O(1)
// 头插法：修改头结点的指向：node.next=head; head = node;即：先绑住后面！
public void addFirst(int data) {
// 首先进行新数据的节点创建
Node node = new Node(data);
node.next = this.head;
this.head = node; // 注意一定要写这一步！！ 头结点完成变换！！
}
//尾插法：尾插时间复杂度O(N)
// 尾插法需要进行头结点是否为null的判断
public void addLast(int data) {
// 首先进行新数据的节点创建
Node node = new Node(data);
if(this.head == null) {
head = node; //注意此处是否正确
return ;
} else {
Node cur = this.head; // 要创建临时变量，保持头结点位置不变！！!
while(cur.next != null) { //cur.next==null：指向最后一个结点位置
cur = cur.next;
}
cur.next = node;
}
}
// 检查下标是否合法
// 错误示范：返回类型！！ 实际应该不返回，下标不合法则抛出异常
private void checkIndex(int index) {
if(index<0 || index>size()) { // 此时可以等于把长度是因为增加节点可以到该长度！
throw new IndexException("sorry 下标不合法！");
}
}
// 拿到index之前的结点-写一个方法找到 index-1 位置上的节点：需要走index-1次就可以走到index-1位置
private Node findIndexOfPre(int index) {
Node cur = this.head;
while(index-1 !=0) {
cur = cur.next;
// 一定要注意循环条件的改变！！
index--;
}
// 出来就说明已经循环拿到了想要的值
return cur;
}
//任意位置插入,第一个数据节点为0号下标
public boolean addIndex(int index,int data) {
// 首先要检查下标是否合法
checkIndex(index);
Node node = new Node(data);
// 如果是0，则进行头插
if(index==0) {
addFirst(data);
return true;
} else if(index==size()) {
// 如果是长度，则进行尾插
addLast(data);
return true;
} else {
// 其他则进行另外方法:注意怎么拿到index-1位置的节点--写一个方法
Node cur = findIndexOfPre(index);
node.next = cur.next;
cur.next = node;
return true;
}
// 再有一种方法是直接插入到cur走到的位置，最后再将前驱val和其值进行互换
}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key) {
// 进行遍历：
Node cur = this.head;
// 该方法比较麻烦！
// 以下为更加简便的修改！
while (cur != null) {
while (cur.val == key) {
return true;
}
// 出来就是不等
cur = cur.next;
}
// 再出来就是有两种情况：==null 以及！=key
return false;
}
// 写一个方法找到前一个结点:注意该方法的书写！！
private Node preNodeOfKey (int key){
// 正确方法如下：
Node cur = this.head;
// 循环条件是只到最后一个结点，并不需要遍历完all！！
// 就算是删除最后一个结点，也只需要遍历到倒数第二个结点就行！
// 头节点之前是没有之前节点的，所以此时不用单独考虑头节点的问题
while(cur.next != null) { // 注意循环条件
while(cur.next.val==key) { // 注意这里的循环条件：因为头节点单独处理
return cur;
}
// 跳出则说明不相等，不相等就进行条件的变换
cur = cur.next;
}
return cur;
}
//删除第一次出现关键字为key的节点
public void remove(int key) {
// 以下是错误代码！！
// 改正：
// 另外情况处理：头节点如果就是所找的要删除的节点的情况
if(head.val == key) {
this.head = head.next;
return ; // 不能忘记return； ！！
}
Node cur = preNodeOfKey(key);
// 要进行判断！！！是否为null
if(cur == null) {
return ;
}
Node del =cur.next; // 注意此处写法！！
cur.next = del.next;
// 或者： cur.next = cur.next.next;
}
//删除所有值为key的节点
// 注意写法！！画图分析！！
public void removeAllKey(int key) {
// 进来首先进行头结点是否为空的判断！！
if(this.head == null) {
return;
}
// 需要一个循环:把整个链表都遍历完
Node pre = this.head;
Node cur = this.head.next;
while (cur != null) {
if(cur.val == key) {
pre.next = cur.next;
cur = cur.next;
} else {
pre = cur;
cur = cur.next;
}
}
// 单独处理头节点的问题，刚刚没有处理头节点问题！！
if(this.head.val == key) { // 注意是if，不用while循环，因为上面已经处理了所有头结点之后的节点
this.head = head.next;
}
// 注意把头结点的处理放在最后！！：因为如果是从头结点开始连续存在要删除的key值，头结点将会变换至下一个key，也就是会一直保留一个key在头结点位置
}
//得到单链表的长度
public int size() {
// 进行链表遍历：直至cur==null则表明遍历完成
Node cur = this.head;
int count =0;
while(cur != null) {
count++;
cur = cur.next;
}
return count;
}
// 打印链表（全部打印）
public void display() {
// 循环判断是否为空null
// 错误代码：
// 画图判断修改！！
Node curNode = this.head;
while(curNode != null) { // curNode==null时 说明遍历完链表
System.out.print(curNode.val+" ");
curNode = curNode.next;
}
System.out.println();
}
// 重写（指定位置开始打印）
public void display(Node node) {
Node curNode = node; // 注意看赋值是否正确！！
while(curNode != null) { // curNode==null时 说明遍历完链表
System.out.print(curNode.val+" ");
curNode = curNode.next;
}
System.out.println();
}
// 清空：去掉所有的连接地址-null
// 目前的问题代码！！！
public void clear() {
// 使用头连接指向置空：则无人引用--直接粗暴型！
System.out.println("使用头连接指向置空：");
/// 改：直接将头结点置空！！ 而不是将next置空！！
this.head = null;
// 完全置空：先拴住后面，再进行置空
System.out.println("完全置空：先拴住后面，再进行置空:");
// 修改：
Node cur = this.head;
while(cur != null) {
Node curNext = cur.next;
cur.next = null; // 此处又进行区分：是将指向置空！
cur = curNext;
}
// 注意此处：将头结点指向置空之后，头结点的val依旧有保存值，打印时依旧会进行打印，要把头结点也置空
this.head = null;
}
}
- Main.java
public class Main {
public static void main(String[] args) {
SingleLinkedList singleLinkedList = new SingleLinkedList();
System.out.println("使用穷举法进行链表创建：");
singleLinkedList.createList();
System.out.println("进行完全打印：");
singleLinkedList.display();
System.out.println("头插法插入：");
singleLinkedList.addFirst(1998);
singleLinkedList.display();
System.out.println("尾插法插入：");
singleLinkedList.addLast(725);
singleLinkedList.display();
System.out.println("计算链表长度：");
System.out.println(singleLinkedList.size());
System.out.println("位置插入：");
singleLinkedList.addIndex(2,1998);
singleLinkedList.display();
System.out.println("判断链表是否包含关键字key：");
System.out.println(singleLinkedList.contains(8));
System.out.println("删除首次关键字key：");
singleLinkedList.remove(1998);
singleLinkedList.display();
System.out.println("删除所有出现的关键字key:");
singleLinkedList.removeAllKey(1998);
singleLinkedList.display();
System.out.println("进行链表清空：");
singleLinkedList.clear();
singleLinkedList.display();
}
}
三、链表面试题
该part一共有11个面试题，具体答案见：链表面试题
-
删除链表中等于给定值 val 的所有节点。 移除链表元素
-
反转一个单链表。反转链表
-
给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结
点。链表的中间结点 -
输入一个链表，输出该链表中倒数第k个结点。链表中倒数第k个结点
-
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。合并两个有序链表
-
编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。链表分割
-
链表的回文结构。链表的回文结构
-
输入两个链表，找出它们的第一个公共结点。相交链表
-
给定一个链表，判断链表中是否有环。环形链表
-
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL。环形链表II
-
其他练习可以去 牛客 或力扣 自己练习。力扣链表 + 牛客网
THINK
- 无头单向非循环的模拟实现
- 无头单向非循环的面试题（注意 快慢结点的使用）
- 顺序表与链表（顺序表是物理与逻辑均连续，链表只有逻辑连续； 链表是通过引用链接次序来实现逻辑顺序的）
