前言：在上一篇博主介绍与实现了数据结构中的顺序表后，为了实现插入和删除元素不去移动元素，不去考虑查找元素的问题，时间复杂度做到O(1) 且数据做到随用随取，放1个数据给1个数据空间，避免浪费；弥补顺序表的缺点，我们就需要使用链表；
这篇博文主要实现与讲解链表中的 单向 无头 非循环链表
快速跳转链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
- 1. 链表节点代码的实现
- 2. 定义头节点 head
- 3.实现一个枚举类型的单向链表
- 4.打印链表数据
- 5. 查找是否包含关键字key是否在单链表当中
- 6.得到单链表的长度
- 7. 在链表中插入节点---头插法
- 8.在链表中插入节点---尾插法
- 9.任意位置插入,第一个数据节点为0号下标
- 9.1 找到index-1位置的节点的地址
- 10.删除第一次出现关键字为key的节点
- 10.1 找到要删除的关键字的前驱
- 11.删除所有为key的节点
- 12.清空链表 释放链表
- 13. 整体实现代码(MylinkedList+Test)示列
- 13.1 MylinkedList
- 13.2 Test
- 14. over
我们把链表节点定义成一个类，里面包含存放数据的数据域对象（val）以及存放引用的引用域对象(next)；
class ListNode{
public int val;
public ListNode next;
public ListNode(int val){
this.val=val;
}
}
2. 定义头节点 head
public ListNode head;3.实现一个枚举类型的单向链表
public void creatList() {
ListNode listNode1 = new ListNode(12);
ListNode listNode2 = new ListNode(23);
ListNode listNode3 = new ListNode(34);
ListNode listNode4 = new ListNode(45);
ListNode listNode5 = new ListNode(56);
listNode1.next = listNode2;
listNode2.next = listNode3;
listNode3.next = listNode4;
listNode4.next = listNode5;
this.head = listNode1;
}
4.打印链表数据
public void display() {
ListNode cur = this.head;//用cur存放head头节点，
//防止头节点变化
while (cur != null) {//null节点即为结束
System.out.print(cur.val + " ");
cur = cur.next; //链接到下一个节点
}
System.out.println();
}
5. 查找是否包含关键字key是否在单链表当中
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key) {
ListNode cur = this.head;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;//链接下一个节点
}
return false;
}
6.得到单链表的长度
//得到单链表的长度
public int size() {
int count = 0;
ListNode cur = this.head;
while (cur != null) {
count++;
cur = cur.next;
}
return count; //链接下一个节点
}
7. 在链表中插入节点—头插法
//头插法
public void addFirst(int data) {
ListNode node = new ListNode(data);
node.next = this.head; //让node节点链接原来的头节点
this.head = node;//node节点置为现在的头节点
}
实列化出一个node节点,进行插入
//尾插法
public void addLast(int data) {
ListNode node = new ListNode(data);
if (this.head == null) { //判断头节点是否是空
this.head = node;//如果是空直接插入
} else {//非空
ListNode cur = this.head;
while (cur.next != null) {
cur = cur.next;
} //找到当前尾节点
cur.next = node; //尾插
}
}
9.任意位置插入,第一个数据节点为0号下标
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index, int data) { //index是位置（相当于下标）
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);//cur即为index插入位置的前一个节点
ListNode node = new ListNode(data); //实列化一个节点
node.next = cur.next;//此时node里面存的引用就是下一个节点的
cur.next = node;//实现与新插入节点链接
}
9.1 找到index-1位置的节点的地址
public ListNode findIndex(int index) {
ListNode cur = this.head;
while (index - 1 != 0) {
cur = cur.next;
index--;
}
return cur; //此时cur节点就是index位置的前一个节点
}
看图理解插入过程是如何重新实现链接的 。
public void remove(int key) {
if (this.head == null) { //看头节点是否为空
System.out.println("单链表为空！不能删除！");
return;
}
if (this.head.val == key) { //看要查找的key是否即在头节点中
this.head = this.head.next; //直接去掉头节点
return;
}
ListNode cur=searchPerv(key); //cur即为key节点的前驱节点
if (cur==null){ //searchPerv没有找到key
System.out.println("没有你要删除的节点！");
return;
}
//删除操作
ListNode del=cur.next;
cur.next=del.next; //链接跳过了key节点，实现删除
}
10.1 找到要删除的关键字的前驱
//找到要删除的关键字的前驱
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 ListNode removeAllKey(int key){
if (this.head==null){ //判断头节点是否为null
return null;
}
ListNode prev=this.head;
ListNode cur=this.head.next;//prev节点紧跟在cur节点后面
while (cur!=null){
if (cur.val==key){
prev.next=cur.next;
cur=cur.next;//跳过key元素节点直接链接到下一个节点，实现删除
}else {
prev=cur;
cur=cur.next;//prev紧跟cur节点后面
}
}
//最后处理头节点
if (this.head.val==key){
this.head=this.head.next; //直接跳过头节点链接下一个节点，实现删除
}
return this.head;
}
12.清空链表 释放链表
//清空链表 释放链表
public void clear(){
//粗暴方法
//this.head=null; 头节点直接置空
while (this.head!=null){ //温柔方法：一个一个节点置空
ListNode curNext=head.next; //定义一个curNext
this.head.next=null;
this.head=curNext; //第一个节点置空后，curNext实现了让第二个节点变成当前头节点，继续置空操作，循环实现单链表全部置空
}
}
}
13. 整体实现代码(MylinkedList+Test)示列
13.1 MylinkedList
class ListNode{
public int val;
public ListNode next;
public ListNode(int val){
this.val=val;
}
}
public class MylinkedList {
public ListNode head;
public void creatList() {
ListNode listNode1 = new ListNode(12);
ListNode listNode2 = new ListNode(23);
ListNode listNode3 = new ListNode(34);
ListNode listNode4 = new ListNode(45);
ListNode listNode5 = new ListNode(56);
listNode1.next = listNode2;
listNode2.next = listNode3;
listNode3.next = listNode4;
listNode4.next = listNode5;
this.head = listNode1;
}
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();
}
//查找是否包含关键字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 int size() {
int count = 0;
ListNode cur = this.head;
while (cur != null) {
count++;
cur = cur.next;
}
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);
if (this.head == null) {
this.head = node;
} else {
ListNode cur = this.head;
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;
}
//找到要删除的关键字的前驱
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){ //判断头节点是否为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(){
//粗暴方法
//this.head=null;
while (this.head!=null){
ListNode curNext=head.next;
this.head.next=null;
this.head=curNext;
}
}
13.2 Test
public class Test {
public static void main(String[] args) {
// 该部分为测试MylinkedList功能实现是否成功的代码
MylinkedList mylinkedList=new MylinkedList();
mylinkedList.creatList();
mylinkedList.display();
//boolean flg= mylinkedList.contains(56);
// System.out.println(flg);
// System.out.println(mylinkedList.size());
// mylinkedList.addFirst(1);
// mylinkedList.display();
// mylinkedList.addLast(100);
// mylinkedList.display();
// mylinkedList.addIndex(12,55);
// mylinkedList.display();
mylinkedList.remove(12);
mylinkedList.display();
// System.out.println("-----------------");
// mylinkedList.clear();
// mylinkedList.display();
// ListNode ret=mylinkedList.reverseList();
// mylinkedList.reverseList();
// mylinkedList.display2(ret);
// ListNode ret=mylinkedList.FindKthToTail(4);
//System.out.println(ret.val);
}
}
14. over
✨ 目前为止有关无头单向单链表的实现以及讲解就到此为止结束了，接下来的博客会继续实现与讲解其他类型的链表，如果觉得本篇博文对自己能有帮助，欢迎大家多多点赞收藏 ~
