【数据结构与算法】4.自主实现单链表的增删查改
1. 前言
在上一篇《顺序表》中，我们已经熟悉了 ArrayList 的使用并且进行了简单的模拟实现。ArrayList底层使用数组来存储元素，由于其底层是一段连续的空间，当ArrayList 任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后移动，时间复杂度为O(n)，效率比较低，因此ArrayList 不适合做任意位置插入和删除比较多的场景。因此：Java集合这种又引入了 LinkedList，即链表结构。
2. 链表
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中引用链接次序实现的。
注意：
- 从上图可看出，链表结构正在逻辑上是连续的，但是在物理上（内存）不一定连续。
- 现实中的节点一般都是从堆上申请出来的。
- 从堆上申请的空间，是按照一定的额策略来分配的，两次申请的空间可能连续，也可能不连续。
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
- 单向或者双向
- 带头或者不带头
- 循环或者非循环
虽然有这么多的链表结构，但是我们重点掌握两种：
- **无头单向非循环链表：结构简单**，一般不会单独用来存放数据。实际中更多是作为**其他数据结构的子结构**，如哈希桶、图的邻接表等等。
- **无头双向链表**：在Java的集合类中`LinkedList`底层实现就是无头双向循环链表3. 单链表的实现
创建一个链表
public class MySingleList {
// 节点
static class ListNode {
public int val; // 数值域 - 存放当前节点的值
public ListNode next; // next域 指向下一个节点
public ListNode(int val) {
this.val = val;
}
}
// 链表的属性 链表的头节点
public ListNode head; // null
public void createList() {
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);
node1.next = node2;
node2.next = node3;
node3.next = node4;
this.head = node1;
}
}画图表示：
3.1 打印链表
- 怎么从第一个节点走到第二个节点？
答：
head = head.next - 什么时候算是把节点都遍历完成？
答：
head == null
代码实现：
/***
* 打印链表
*/
@Override
public void display() {
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;// 让cur这个节点 可以从一个节点走到下一个节点
}
System.out.println();
}3.2 头插法
在链表的第一个位置插入元素。
思路：
- 插入元素的
next指向head head指向插入元素
代码实现：
/**
* 头插法
* @param data
*/
@Override
public void addFirst(int data) {
ListNode node = new ListNode(data); // 定义一个节点
node.next = head;
head = node;
}3.3 尾插法
在链表的最后个位置插入元素
思路：
- 判断链表中是否有元素。
- 如果没有元素，直接添加头结点即可。
- 如果有元素，将原链表最后一个元素
next指向插入的元素。
代码实现：
/**
* 尾插法
* @param data
*/
@Override
public void addLast(int data) {
ListNode node = new ListNode(data); // 定义一个节点
if (head == null) { // 链表一个元素都没有
head = node;
} else {
ListNode cur = head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
}3.4 任意位置插入元素
思路：
- 判断
index是否合法（index < 0 或者 index 大于链表长度），如果不合法则抛出异常。 - 判断
index等于0或者index等于链表长度，则使用头插法或尾插法 cur找到index - 1位置- 插入元素的
next指向cur的next cur的next指向插入的元素
代码实现：
/**
* 在index位置 插入data
* @param index
* @param data
*/
@Override
public void addIndex(int index, int data) throws IndexException{
if (index < 0 || index > size()) {
throw new IndexException("index不合法：" + index);
}
ListNode node = new ListNode(data); // 定义一个节点
if (head == null) {
head = node;
return;
}
if (index == 0) {
addFirst(data);
return;
}
if (index == size()) {
addLast(data);
return;
}
ListNode cur = searchPrevIndex(index);
node.next = cur.next;
cur.next = node;
}
/**
* 找到index-1的位置
* @param index
* @return
*/
private ListNode searchPrevIndex(int index) {
ListNode cur = head;
int count = 0;
while (count != index - 1) {
cur = cur.next;
count++;
}
return cur;
}异常类：
public class IndexException extends RuntimeException{
public IndexException() {
}
public IndexException(String msg) {
super(msg);
}
}3.5 查找元素
代码实现：
/***
* 求当前链表 是否存在key
* @param key
* @return
*/
@Override
public boolean contains(int key) {
ListNode cur = head;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}3.6 链表节点个数
代码实现：
/**
* 求当前链表 有多少个节点
* @return
*/
@Override
public int size() {
ListNode cur = head;
int count = 0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}3.7 删除元素
思路：
- 判断链表是否为空，如果为空直接返回
- 判断删除元素是否为头节点，如果是则
head指向head的next - 定义指针找到要删除节点的前一个节点
- 前一个节点的
next指向删除节点的next
代码实现：
/**
*
* @param key
*/
@Override
public void remove(int key) {
if (head == null) {
return;
}
if (head.val == key) {
head = head.next;
return;
}
ListNode cur = findPrevKey(key);
if (cur == null) {
return;// 链表里要没有删除的数字
}
ListNode del = cur.next;
cur.next = del.next;
}
/**
* 找到删除节点的前一个节点
* @param key
* @return
*/
private ListNode findPrevKey(int key) {
ListNode cur = head;
while (cur.next != null) {
if (cur.next.val == key) {
return cur;
} else {
cur = cur.next;
}
}
return null;
}3.8 删除链表中指定的所有元素
思路:
- 判断链表是否为空，如果是空直接返回
- 定义指针
cur：可能要删除的节点 - 定义指针
prev：可能要删除的节点的前驱 - 判断
cur的val是不是要删除的元素，如果是prev的next指向cur的next，cur指向cur的next；否则prev指向cur，cur指向cur的next - 判断头节点的
val是否为的元素，如果是头节点指向头节点的neext
代码实现：
/**
* 删除链表中所有的key
* @param key
*/
@Override
public void removeAllKey(int key) {
if (head == null) {
return;
}
ListNode prev = head; // 表示当前可能要删除的节点
ListNode cur = head.next; // 可能要删除节点的前驱
while (cur != null) {
if (cur.val == key) {
prev.next = cur.next;
cur = cur.next;
} else {
prev = cur;
cur = cur.next;
}
}
if (head.val == key) {
head = head.next;
}
}3.9 清空链表
当一个对象，没有被引用的时候，就会被回收掉
/**
* 清空链表
*/
@Override
public void clear() {
head = null;
}4. 代码
5. OJ题
本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2024-02-15，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。