一.链表
1.什么是链表
- 链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。
- 链表的结构有多种多样，我们学习的主要有两个，单向不带头非循环与双向不带头非循环，还有例外几种没有这两种常用，所以我们暂时不学哈哈。
2.链表的用途
? 在你使用顺序表时，是不是每次插入和删除元素，必须得移动元素，然后顺序表扩容也是一个问题，顺序表满了我们都是乘2来扩容，顺序表容量少还好，如果我们的容量达到了一个很大值，是不是会浪费很多空间。链表就解决了这些问题，链表在物理上并不是一定连续的，但在逻辑上是连续的，我们可以做到不移动元素进行插入和删除，在内存层面上可以做到随用随取，增加元素就加一个空间，只要使它的逻辑上连续就行了。
二.用代码实现一个链表
学习链表前一定要知道的几个概念
前驱，后继，头结点，尾结点，前驱和后继明白了对学习链表真的很重，笔者在这方面吃过亏(哭了)，
除了头结点其它每个结点多有一个前驱，
除了尾结点其它每个结点多有一个后继。[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
这张表里面的listNode2是listNosd3的前驱listNode4是listNode3的后继。
我们用listNode2.val就能拿到listNode2里面的值，
用listNode2.next就能拿到下一个结点的地址
1.生成一个链表
-
第一步需要创建一个结点类这样我们就能像超市批发一样成批生成结点。
class ListNode{ public int val;//结点值 public ListNode next;//结点 public ListNode(int val){ this.val=val; } } -
生成一个头结点用来执行接下来的一系列操作
ListNode head;//链表头 -
接下来就到我们生成第一个链表的时候了（穷举法）
public void createList(){ ListNode listNode1=new ListNode(21);//创建第一个结点 ListNode listNode2=new ListNode(65);//创建第二个结点 ListNode listNode3=new ListNode(48);//创建第三个结点 ListNode listNode4=new ListNode(13);//创建第四个结点 ListNode listNode5=new ListNode(98);//创建第五个结点 //把所有的结点链接起来 this.head=listNode1; listNode1.next=listNode2; listNode2.next=listNode3; listNode3.next=listNode4; listNode4.next=listNode5; }下面这张图就是我们的链表[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
2.打印链表
-
接下来可以写个打印函数来打印我们的链表了
-
第一种从头开始打印
public void display(){ ListNode cur=this.head; while (cur!=null){ System.out.print(cur.val+" "); cur=cur.next; } System.out.println(); } //运行结果：21 65 48 13 98程序开始我们把链表头赋给了cur，如果不生成cur这个变量的话，我们的链表就变成一次性的了，这一个点要注意下，cur.val用来拿链表里的值，cur.next指向的是下个链表，这个可以结合上面图理解一下，好了到了这里我们生成了一个链表并打印出来了。
-
第二种方法从指定的地方开始打印
public void display2(ListNode newHead){ ListNode cur=newHead; while (cur!=null){ System.out.print(cur.val+" "); cur=cur.next; } System.out.println(); }
-
3.链表大小
-
要想得到链表的大小，第一步你是怎么想的，是不是通过遍历链表来实现呀，对！目前就是用遍历来实现的
//得到单链表的长度 public int size(){ ListNode cur = this.head; int count=0; while (cur!=null){ cur=cur.next; count++; } return count; }小技巧：每次我我们要遍历链表的时候多要把链表头，赋给一个临时遍历，这样可以避免链表称为一次性的，爱护环境人人有责，循环利用才是最好的，开个玩笑哈哈。
4.查找包含的元素
-
只需要遍历链表的值来和要查找的元素比较就行了
-
具体代码实现
//查找是否包含关键字key是否在单链表当中 public boolean contains(int key){ ListNode cur = this.head; while (cur!=null){ if(cur.val==key){ return true; } cur=cur.next; } return false; }
5.头插法
-
头插法就如它的名字一样从头部开始插入[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
图中，实现头插法是要记得要先绑定后面结点，在绑定前面的结点，图中蓝色的框里的赋值就是没有先绑定后面的形成了一个自己指向自己的闭环结点， -
头插头法的具体实现
//头插法 public void addFirst(int data){ ListNode node=new ListNode(data); node.next=this.head; this.head=node; }第一步生成了一个新的结点，第二步把一开是的链表头head给node.next,第三步把node给head。
6.尾插法
-
前面我么学尾插法时是从头部插的，这个尾插法肯定就是从未尾部开始插的哈哈下面先看下画的思维图[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
-
代码的具体实现
//尾插法 public 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.next=node; } }这里我们要注意的时循环条件变了，不是cur了而是cur.next看图我们可以发现cur！=null会走到listNode5后面才能结束循环(listNode6先不看这是我们插入的)cur.next走到最后一个就会停。
7.任意位置插入
-
在任意地方插入的时候要考虑三个方面，如在头结点插入，在尾结点插入，还有在中间插入，这里里面最难的就是在中间插入，插入头和尾可以分别调用头插入函数和尾插入函数就行，但在中间插入我们需要找到要插入位置的前驱或后继才能插入[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
-
代码具体实现
-
找到index-1位置的节点的地址
public ListNode findIndex(int index){ ListNode cur=this.head; while (index-1!=0){ cur=cur.next; index--; } return cur; } -
任意位置插入
//任意位置插入,第一个数据节点为0号下标 public void addIndex(int index,int data){ if(index<0||index>size()){ System.out.println("index不合法！"); return; } if(index==0){ addFirst(data); return; } if(index==size()){ addLast(data); return; } ListNode cur=findIndex(index); ListNode node=new ListNode(data); node.next=cur.next; cur.next=node; }
-
8.删除第一次出现关键字为key的节点
-
要实现这函数要搞清楚head.val 和head.next.val的区别[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
-
代码具体实现
- 找到 要删除的关键字的前驱
public ListNode searchPerv(int key){ ListNode cur=this.head; while (cur.next!=null){ if(cur.next.val==key){ return cur; } cur=cur.next; } return null; }-
删除第一次出现关键字为key的节点
public void remove(int key){ if (this.head==null){ System.out.println("链表为空"); return; } if(this.head.val==key){ this.head=this.head.next; return; } ListNode cur = searchPerv(key); if(cur==null){ System.out.println("没有删除的结点"); return; } ListNode del=cur.next; cur.next=del.next; }我们利用cur.next.val可以找到我们要删的结点，任何把他的前驱发回来，在进行操作，cur就是前驱。
9.删除所有值为key的节点
-
定义了两个变量，可以理解成一个大哥(cur)和一位小弟(perv)，大哥在前面冲锋陷阵，小弟跟在大哥后,大哥确认安全了才会叫小弟来
-
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
?
-
具体代码实现
public ListNode removeAllKey(int key){ if(this.head==null){ System.out.println("没有要删除的结点"); return null; } ListNode perv=this.head;//链表头 ListNode cur=this.head.next;//第二个结点 while (cur!=null){ if(cur.val==key){ perv.next=cur.next; cur=cur.next; }else { perv=cur; cur=cur.next; } } if (this.head.val==key){ this.head=this.head.next; } return this.head; }
10.删除整条链表
-
删除整条链表有两种方法实现[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
-
暴力法
public void clear(){ this.head=null; } -
相对温柔
public void clear(){ while (this.head!=null){ ListNode curNext = head.next; this.head.next=null; this.head=curNext; } }
-
三.单链表完整代码
0.代码模板
//头插法
public void addFirst(int data);
//尾插法
public void addLast(int data);
//任意位置插入,第一个数据节点为0号下标
public boolean 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();
1.text
package com.wei.two;
/**
* Created with IntelliJ IDEA.
* Description:
* User:WLW
* Data:2021-11-08
* Time:23:48
*/
public class TextDome {
public static void main(String[] args) {
MyLinkedList myLinkedList=new MyLinkedList();
// myLinkedList.createList();
// myLinkedList.addFirst(21);
// myLinkedList.addFirst(65);
// myLinkedList.addFirst(48);
// myLinkedList.addFirst(13);
// myLinkedList.addFirst(98);
myLinkedList.addLast(21);
myLinkedList.addLast(65);
myLinkedList.addLast(48);
myLinkedList.addLast(21);
myLinkedList.addLast(21);
myLinkedList.display();
//myLinkedList.addIndex(2,33);
//myLinkedList.addIndex(1,33);
// myLinkedList.addIndex(5,33);
// myLinkedList.display();
// System.out.println(myLinkedList.size());
// System.out.println(myLinkedList.contains(100));
//myLinkedList.display2();
myLinkedList.remove(21);
myLinkedList.removeAllKey(21);
// myLinkedList.clear();
myLinkedList.display();
}
}
2.MyLinkedList
package com.wei.two;
/**
* Created with IntelliJ IDEA.
* Description:
* User:WLW
* Data:2021-11-08
* Time:23:49
*/
//创建一个结点
class ListNode{
public int val;
public ListNode next;
public ListNode(int val){
this.val=val;
}
}
public class MyLinkedList {
ListNode head;//链表头
//创建一个链表
public void createList(){
ListNode listNode1=new ListNode(21);//创建第一个结点
ListNode listNode2=new ListNode(65);//创建第二个结点
ListNode listNode3=new ListNode(48);//创建第三个结点
ListNode listNode4=new ListNode(13);//创建第四个结点
ListNode listNode5=new ListNode(98);//创建第五个结点
//把所有的结点链接起来
this.head=listNode1;
listNode1.next=listNode2;
listNode2.next=listNode3;
listNode3.next=listNode4;
listNode4.next=listNode5;
}
public void display(){
ListNode cur=this.head;
while (cur!=null){
System.out.print(cur.val+" ");
cur=cur.next;
}
System.out.println();
}
public void display2(ListNode newHead){
ListNode cur=newHead;
while (cur!=null){
System.out.print(cur.val+" ");
cur=cur.next;
}
System.out.println();
}
//得到单链表的长度
public int size(){
ListNode cur = this.head;
int count=0;
while (cur!=null){
cur=cur.next;
count++;
}
return count;
}
//头插法
public void addFirst(int data){
ListNode node=new ListNode(data);
node.next=this.head;
this.head=node;
}
//尾插法
public 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.next=node;
}
}
public ListNode findIndex(int index){
ListNode cur=this.head;
while (index-1!=0){
cur=cur.next;
index--;
}
return cur;
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data){
if(index<0||index>size()){
System.out.println("index不合法！");
return;
}
if(index==0){
addFirst(data);
return;
}
if(index==size()){
addLast(data);
return;
}
ListNode cur=findIndex(index);
ListNode node=new ListNode(data);
node.next=cur.next;
cur.next=node;
}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key){
ListNode cur = this.head;
while (cur!=null){
if(cur.val==key){
return true;
}
cur=cur.next;
}
return false;
}
public ListNode searchPerv(int key){
ListNode cur=this.head;
while (cur.next!=null){
if(cur.next.val==key){
return cur;
}
cur=cur.next;
}
return null;
}
//删除第一次出现关键字为key的节点
public void remove(int key){
if (this.head==null){
System.out.println("链表为空");
return;
}
if(this.head.val==key){
this.head=this.head.next;
return;
}
ListNode cur = searchPerv(key);
if(cur==null){
System.out.println("没有删除的结点");
return;
}
ListNode del=cur.next;
cur.next=del.next;
}
//删除所有值为key的节点
public ListNode removeAllKey(int key){
if(this.head == null) return null;
ListNode prev = this.head;
ListNode cur = this.head.next;
while (cur != null) {
if(cur.val == key) {
prev.next = cur.next;
cur = cur.next;
}else {
prev = cur;
cur = cur.next;
}
}
//最后处理头
if(this.head.val == key) {
this.head = this.head.next;
}
return this.head;
}
public void clear(){
while (this.head!=null){
ListNode curNext = head.next;
this.head.next=null;
this.head=curNext;
}
}
}