【一起学数据结构与算法】快速教你了解并实现单链表
2023-04-18 16:09:37 时间
目录
前言
此篇是对单链表知识的学习和实现，基本上大体的方法实现和思路都已经表达，如果有不对的地方，还请各位大佬多多指教！
一、单链表的概念
单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
二、单链表内一些方法的实现
2.1 单链表长什么样子？
像上面这样式的就是一种单链表！
由上图可以看出我们一些属性来表示单链表！
class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
2.2 创建单链表
创建链表之前我们需要定义一个成员变量head表示链表的头结点！
//成员变量
public ListNode head;//链表的头引用
由于咱们是初步学习单链表，所有咱们就简单的创建的单链表
public void createList() {
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;
}
2.3 打印单链表
public void display() {
ListNode cur = this.head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
为什么会定义一个cur来指向head了？
那是因为如果拿head来遍历链表，那么最后head就指向了null，就找不到链表的头了，所以使用cur来完成操作！
2.4 查找是否包含关键字key是否在单链表中
我们只需要拿cur去遍历链表，看cur是否等于key，如果有就返回true，没有就返回false。
实现cur遍历的过程的代码就是：cur = cur.next;
//查找是否包含关键字key是否在单链表中
public boolean contains(int key) {
ListNode cur = this.head;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
2.5 得到单链表的长度
一样的操作，此处通过定义一个count作为计数器，直到cur遍历完整个链表就停止.
//得到单链表的长度
public int size() {
int count = 0;
ListNode cur = this.head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
2.6 addFirst – 头插
//头插法
public void addFirst(int data) {
ListNode node = new ListNode(data);
node.next = this.head;
this.head = node;
/*if (this.head == null) {
this.head = node;
} else {
node.next = this.head;
this.head = node;
}*/
}
2.7 addLast – 尾插
//尾插法
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;
}
}
2.8 addIndex – 任意位置插入
/**
* 找到index - 1 位置结点的地址
* @param index
* @return
*/
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位置不合法!");
}
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;
}
2.9 remove – 删除第一次出现的key
/**
* 找到要删除关键字的前驱
* @param key
* @return
*/
public ListNode searchPrev(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 = searchPrev(key);
if (cur == null) {
System.out.println("没有你要删除的结点！");
return;
}
ListNode del = cur.next;
cur.next = del.next;
}
2.10 removeAllkey – 删除所有值为key的结点
//删除所有值为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;
}
1.如果先处理头，则需要写成循环，因为当链表所有结点都是待删除的情况时，一个if条件语句处 理不了
2.while循环里面的条件不能写成cur.next == null，因为removeSubOne函数如果没找到待删除 的结点，它返回的是一个null，如果写成cur.next != null，则可能会报空指针异常
2.11 清空单链表
public void clear() {
this.head = null;
}
三、MyLinkedList.java
import java.util.LinkedList;
@SuppressWarnings({"all"})
class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public class MyLinkedList {
//成员变量
public ListNode head;//链表的头引用
public void createList() {
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();
}
//查找是否包含关键字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;
/*if (this.head == null) {
this.head = node;
} else {
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;
}
}
/**
* 找到index - 1 位置结点的地址
* @param index
* @return
*/
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位置不合法!");
}
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;
}
/**
* 找到要删除关键字的前驱
* @param key
* @return
*/
public ListNode searchPrev(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 = searchPrev(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() {
this.head = null;
}
}
四、Test.java
public class Test {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
/* myLinkedList.createList();
myLinkedList.display();
boolean flag = myLinkedList.contains(34);
System.out.println(flag);
int size = myLinkedList.size();
System.out.println(size);*/
myLinkedList.addFirst(12);
myLinkedList.addFirst(23);
myLinkedList.addLast(39);
myLinkedList.addLast(37);
myLinkedList.addIndex(0,99);
myLinkedList.addIndex(5,99);
myLinkedList.addIndex(3,99);
myLinkedList.display();
myLinkedList.remove(12);
myLinkedList.removeAllKey(99);
myLinkedList.display();
myLinkedList.clear();
myLinkedList.display();
}
}
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法：眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络？
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final，JSR-299 的框架
- JavaFX 2012：彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight：基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE：用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络：结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击