希望通过博客和大家相互交流，相互学习，如有错误，请评论区指正
文章目录
一、什么是链表
顺序表在空间利用，系统消耗，插入元素方面都是存在缺陷的。而链表是最常用的动态存储方法，克服了顺序表的缺点。
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的
链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储指向下一个结点的引用域
链表的结构很多，有以下6种情况，组合起来有8种
- 有头、无头
- 单向、双向
- 循环、非循环
在这8种情况中，我们一般重点学习其中的2种，无头单向非循环链表和无头双向循环链表
二、手撕链表
这里实现无头单向非循环链表
属性定义
我们需要有链表结点和链表对象，如下：
结点对象
public class Node {
public int data;
public Node next;
}
构造方法
public Node(int data) {
this.data = data; // 注意要用 this， 里面直接写data的话就是形参data
this.next = null;
}
链表对象
public class MyLinkedList {
public Node head;
}
构造方法
public MyLinkedList() {
this.head = null;
}
链表的实现
//头插
public void addFirst(int data);
//尾插
public void addLast(int data);
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data);
//查找是否包含关键字key
public boolean contains(int key);
//删除第一次出现关键字为key的节点
public void remove(int key);
//删除所有值为key的节点
public void removeAllKey(int key);
//得到单链表的长度
public int size();
public void display();
public void clear();
注意：在实现这些方法的时候，要注意遍历链表 while 循环判断条件应该是 cur.next != null 还是 cur != null
插入删除元素的时候考虑边界条件及特殊情况（只有一个结点、空结点等）
头插
public void addFirst(int data) {
Node newNode = new Node(data);
if (this.head == null) { // 当为空链表时，只需要让head指向该结点即可
head = newNode;
return;
}
newNode.next = head;
head = newNode;
}
尾插
注意当链表为空的时候特殊处理. 不为空时，通过遍历链表的方式找尾，然后再插入
public void addLast(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node cur = head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = newNode;
}
得到单链表的长度
public int size() {
int count = 0;
Node cur = this.head;
while (cur != null) {
cur = cur.next;
count++;
}
return count;
}
任意位置插入
设定第一个数据节点为0号下标，要注意考虑会有头插，尾插，下标不合法等情况
public void addIndex(int index, int data) {
if (index < 0 || index > this.size()) {
throw new RuntimeException("index" + ":" + index);
}
Node newNode = new Node(data);
if (index == 0) { // 头插
this.addFirst(data);
return;
}
if (index == this.size()) { // 尾插
this.addLast(data);
return;
}
Node cur = this.head;
while (index - 1 != 0) {
cur = cur.next;
index--;
}
newNode.next = cur.next;
cur.next = newNode;
}
查找是否包含关键字key
遍历链表，将结点数据和key进行比较
public boolean contains(int key) {
Node cur = this.head;
while (cur != null) {
if (cur.data == key) {
return true;
}
cur = cur.next;
}
return false;
}
删除第一次出现关键字为key的节点
遍历链表，找到第一个为key的结点然后删除,要考虑链表为空，头删，等特殊情况
public void remove(int key) {
if (this.head == null) {
return;
}
if (head.data == key) { // 头删
head = head.next;
return;
}
Node cur = this.head;
while (cur.next != null) {
if (cur.next.data == key) {
break;
}
cur = cur.next;
}
if (cur.next != null) {
cur.next = cur.next.next;
}
}
打印单链表
public void display() {
Node cur = this.head;
while (cur != null) {
System.out.print(cur.data + "->");
cur = cur.next;
}
System.out.print("null");
}
清空链表
在用完链表之后使用clear() 方法防止发生内存泄漏（查看进程号jps, 重定向 jmap -histo:live 6666 > e:\niubi.txt）
public void clear() {
this.head = null;
}
删除所有值为key的节点
注意：1. prev到底什么时候才往后跳， 第一个结点不应该刚开始就判断，而应该后面的都删完了之后再判断第一个结点
public void removeAll(int key) {
if (this.head == null) {
return;
}
Node prev = this.head;
Node cur = this.head.next;
while (cur != null) {
if (cur.data == key) {
prev.next = cur.next;
cur = cur.next;
} else {
prev = cur;
cur = cur.next; // 不是key，cur和prev都往后跳
}
}
if (this.head.data == key) {
this.head = this.head.next;
}
}
2. 双向链表
这里以双向无头非循环链表为例来介绍，如下图所示：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4Bvzi6qI-1641391981418)(C:\Users\lycre\AppData\Roaming\Typora\typora-user-images\image-20220105182248704.png)]
属性定义
结点对象及构造方法和单线表相同
链表对象
链表对象多一个tail属性，指向链表的尾结点
public class MyLinkedList{
public Node head;
public Node tail;
}
构造方法
无参构造方法
public MyLinkedList() {
this.head = null;
this.tail = null;
}
链表的实现
//头插法
public void addFirst(int data);
//尾插法
public void addLast(int data);
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data);
//查找是否包含关键字key
public boolean contains(int key);
//删除第一次出现关键字为key的节点
public void remove(int key);
//删除所有值为key的节点
public void removeAllKey(int key);
//得到链表的长度
public int size();
//打印链表
public void display();
//清空链表，释放内存
public void clear();
头插
头插的过程中要注意空链表的情况
public void addFirst(int data) {
Node newNode = new Node(data);
if (this.head == null) { // 链表为空时
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
}
尾插
public void addLast(int data) {
Node newNode = new Node(data);
if (this.head == null) { // 链表为空的情况
this.head = newNode;
this.tail = newNode;
} else {
newNode.prev = tail;
this.tail.next = newNode;
this.tail = newNode;
}
}
得到链表的长度
public int size() {
int count = 0;
Node cur = this.head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
任意位置插入
在任意位置插入元素需要考虑的情况会比较多，我们应该先将可能的情况都罗列出来，再写，避免忽略一些情况
注意对index有效性进行判断
public void addIndex(int index,int data) {
if (index < 0 || index > this.size()) {
throw new RuntimeException("index : " + index);
}
Node newNode = new Node(data);
if (index == 0) {
if (this.head == null) { // 头插
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
} else if (index == this.size()) { // 尾插
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
} else {
Node cur = this.head;
while (index != 0) {
cur = cur.next;
index--;
}
Node prevNode = cur.prev;
newNode.next = cur;
newNode.prev = prevNode;
prevNode.next = newNode;
cur.prev = newNode;
}
}
查找是否包含关键字key
直接遍历链表，逐一对比
public boolean contains(int key) {
Node cur = this.head;
while (cur != null) {
if (cur.data == key) {
return true;
}
}
return false;
}
删除第一次出现关键字为key的结点
涉及到头删，尾删，空链表等情况
public void remove(int key) {
if (this.head == null) {
return;
}
Node cur = this.head;
while (cur != null) { // 找第一个为key的结点
if (cur.data == key) {
break;
}
cur = cur.next;
}
if (cur == null) {
return; //没找到，直接返回
}
if (cur == this.head) { // 头删
this.head = head.next;
this.head.prev = null;
return;
}
if (cur == this.tail) { // 尾删
cur.prev.next = null;
this.tail = cur.prev;
return;
}
Node prevNode = cur.prev;
Node nextNode = cur.next;
prevNode.next = nextNode;
nextNode.prev = prevNode;
}
删除所有值为key的节点、
public void removeAllKey(int key) {
if (this.head == null) {
return;
}
Node prevNode = this.head;
Node cur = this.head.next;
while (cur != null) {
if (cur.data == key) {
prevNode.next = cur.next;
cur = cur.next;
if (cur == null) {
this.tail = prevNode; // 最后一个结点值为key
} else {
cur.prev = prevNode;
}
} else {
cur = cur.next;
prevNode = prevNode.next;
}
}
if (this.head.data == key) {
this.head = this.head.next;
if (this.head == null) {
this.tail = null; // 注意当链表中所有元素均为key时，在最后不仅要判断head，也要改tail
return;
}
this.head.prev = null;
}
}
打印链表
public void display() {
Node cur = this.head;
while (cur != null) {
System.out.print(cur.data + "->");
cur = cur.next;
}
System.out.print("null");
}
清空链表，释放内存
public void clear() {
if (this.head == null) {
return;
}
Node cur = this.head;
Node nextNode;
while (cur != null) {
nextNode = cur.next;
cur.prev = null;
cur.next = null;
cur = nextNode;
}
this.tail = null;
}
注意清空双向链表和单向链表是有很大区别的，不能直接将head置为null，因为后面的结点还保存这前面结点的引用，所以我们应该要将所有结点的next域和prev域置空
欢迎大家关注！！！
一起学习交流 ！！！
让我们将编程进行到底！！！
--------------整理不易，请三连支持------------------