上行2m可以做网站,郑州百姓网招聘信息官网,施工企业会计核算办法2021,网站搭建的费用1. 前言
在上一篇《Java数据结构篇——实现顺序表的增删查改》#xff0c;我们已经熟悉了 ArrayList 的使用并且进行了简单的模拟实现。ArrayList底层使用数组来存储元素#xff0c;由于其底层是一段连续的空间#xff0c;当ArrayList 任意位置插入或者删除元素时#xff…1. 前言
在上一篇《Java数据结构篇——实现顺序表的增删查改》我们已经熟悉了 ArrayList 的使用并且进行了简单的模拟实现。ArrayList底层使用数组来存储元素由于其底层是一段连续的空间当ArrayList 任意位置插入或者删除元素时就需要将后序元素整体往前或者往后移动时间复杂度为O(n)效率比较低因此ArrayList 不适合做任意位置插入和删除比较多的场景。因此Java集合这种又引入了 LinkedList即链表结构。
2. 链表
链表是一种物理存储结构上非连续存储结构数据元素的逻辑顺序是通过链表中引用链接次序实现的。 注意
从上图可看出链表结构正在逻辑上是连续的但是在物理上内存不一定连续。现实中的节点一般都是从堆上申请出来的。从堆上申请的空间是按照一定的额策略来分配的两次申请的空间可能连续也可能不连续。
3. 单链表的实现
创建一个链表
public class MySingleList {// 节点static class ListNode {public int val; // 数值域 - 存放当前节点的值public ListNode next; // next域 指向下一个节点public ListNode(int val) {this.val val;}}// 链表的属性 链表的头节点public ListNode head; // nullpublic 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
代码实现 /**** 打印链表*/Overridepublic void display() {ListNode cur head;while (cur ! null) {System.out.print(cur.val );cur cur.next;// 让cur这个节点 可以从一个节点走到下一个节点}System.out.println();}3.2 头插法
在链表的第一个位置插入元素。
思路
插入元素的next指向headhead指向插入元素 代码实现 /*** 头插法* param data*/Overridepublic void addFirst(int data) {ListNode node new ListNode(data); // 定义一个节点node.next head;head node;}3.3 尾插法
在链表的最后个位置插入元素
思路
判断链表中是否有元素。如果没有元素直接添加头结点即可。如果有元素将原链表最后一个元素next指向插入的元素。 代码实现 /*** 尾插法* param data*/Overridepublic 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的nextcur的next指向插入的元素 代码实现 /*** 在index位置 插入data* param index* param data*/Overridepublic 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*/Overridepublic boolean contains(int key) {ListNode cur head;while (cur ! null) {if (cur.val key) {return true;}cur cur.next;}return false;}3.6 链表节点个数
代码实现 /*** 求当前链表 有多少个节点* return*/Overridepublic 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*/Overridepublic 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 [删除链表中指定的所有元素](203. 移除链表元素 - 力扣LeetCode)
思路:
判断链表是否为空如果是空直接返回定义指针cur可能要删除的节点定义指针prev可能要删除的节点的前驱判断cur的val是不是要删除的元素如果是prev的next指向cur的nextcur指向cur的next否则prev指向curcur指向cur的next判断头节点的val是否为的元素如果是头节点指向头节点的neext 代码实现 /*** 删除链表中所有的key* param key*/Overridepublic 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;}}LeetCode运行结果 3.9 清空链表
当一个对象没有被引用的时候就会被回收掉 /*** 清空链表*/Overridepublic void clear() {head null;}[4. 代码](MySingleList/src · 白日依山璟/JavaSE_code - 码云 - 开源中国 (gitee.com))
