静态网站开发工具,公众号绑定网站教程,网站推广费用大概需要多少钱,济南mip网站建设公司链表#xff08;一#xff09; 文章目录 链表#xff08;一#xff09;01 引入02 概念及结构03 单向不带头不循环链表实现3.1 创建节点类型3.2 简易创建一个链表3.3 遍历链表每个节点3.4 获取链表长度3.5 查找是否包含关键字key是否在单链表当中3.6 头插法3.7 尾插法3.8 任…链表一 文章目录 链表一01 引入02 概念及结构03 单向不带头不循环链表实现3.1 创建节点类型3.2 简易创建一个链表3.3 遍历链表每个节点3.4 获取链表长度3.5 查找是否包含关键字key是否在单链表当中3.6 头插法3.7 尾插法3.8 任意位置插入3.9 删除第一次出现关键字为key的节点3.10 删除所有值为key的节点3.11 清空 01 引入
接上文顺序表我们可以知道ArrayList的缺陷。当在ArrayList任意位置插入或者删除元素时就需要将后序元素整体往前或者往后搬移时间复杂度为O(n)效率比较低因此ArrayList不适合做任意位置插入和删除比较多的场景。因此java集合中又引入了LinkedList即链表结构。
那么下面让我们来了解了解链表。
02 概念及结构
链表是一种物理存储结构上非连续存储结构数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。其实就是节点组成一个节点类似于火车一个车厢那样 下面是一个单向带头非循环链表 下面是链表的种类
单向双向不带头带头非循环循环 通过彼此间的排列组合一共可以分为8种如下
单向 不带头 非循环单向 不带头 循环单向 带头 非循环单向 带头 循环双向 不带头 非循环双向 不带头 循环双向 带头 非循环双向 带头 循环
这里着重介绍单向 不带头 非循环 和 双向 不带头 非循环。
无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。无头双向链表在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。
03 单向不带头不循环链表实现
3.1 创建节点类型
链表是由一个一个节点组成的每一个节点对应每一个对象如果我们去抽象他他其实有两个域值所以我们可以把节点定义成内部类。
创建一个ListNode类来作为节点类型包含两个成员变量val域用来储存数据数据域next用来存储下一个节点的地址指针域。 再创建一个带参的构造方法来实例化对象同时给val赋值next的默认值是null。接下来我们用代码来实现一下
//静态内部类static class ListNode{public int val; //节点的值域public ListNode next; //下一个节点的地址//实例化节点对象public ListNode(int val){this.val val;}}3.2 简易创建一个链表
public ListNode head;//表示当前链表的头节点//以穷举的方式创建一个链表public void createList(){ListNode node1 new ListNode(12);ListNode node2 new ListNode(23);ListNode node3 new ListNode(34);ListNode node4 new ListNode(45);ListNode node5 new ListNode(56);}此时创建的链表如图 目前各节点间不存在关系。
那么接下来的操作就是要让node1-node2-node3-node4-node5
//以穷举的方式创建一个链表public void createList(){ListNode node1 new ListNode(12);ListNode node2 new ListNode(23);ListNode node3 new ListNode(34);ListNode node4 new ListNode(45);ListNode node5 new ListNode(56);node1.next node2;node2.next node3;node3.next node4;node4.next node5;this.head node1;}这里我们不妨在编译器里debug来看看 3.3 遍历链表每个节点
public void display() {while (head ! null){System.out.println(head.val );head head.next;}}这里我们可以在测试类中debug一下看看 虽然这里的确是将链表遍历完全但是这里的头节点head null
那么这样就会造成一个后果鬼都不知道头节点head死哪里去了那咋办
这个后果虽然很严重但是解决办法其实也很容易既然head它不能乱来那它可以叫个分身cur代替它去呀。
public void display() {ListNode cur head;while (cur ! null){//如果cur null说明把链表遍历完成System.out.println(cur.val );cur cur.next;//cur每次向后走一步}System.out.println();}3.4 获取链表长度
这个其实也就是基于3.3 遍历链表得来的。
//得到单链表的长度public int size(){int count 0;ListNode cur head;if (cur!null){while(cur ! null){cur cur.next;count;}return count;}else{return -1;}}3.5 查找是否包含关键字key是否在单链表当中
这个其实也一样是基于3.3 遍历链表得来的。
//查找是否包含关键字key是否在单链表当中public boolean contains(int key){ListNode cur head;while(cur ! null){if (key cur.val){return true;}cur cur.next;}return false;}3.6 头插法
头插法指的是在链表的头节点位置插入一个新的节点定义一个node表示插入的新节点然后将node.next head,head node即可。
形象一点来看如图 //头插法public void addFirst(int data){ListNode node new ListNode(data);node.next head;head node;}3.7 尾插法
尾插法指的是在链表的尾巴节点位置插入一个新节点定义一个node表示新节点如同头插法那样对原尾巴节点的next进行赋值。下面是尾插链表出现的情况 当链表不为空的时候定义一个cur来代替head这里其实和遍历节点的道理一致直到cur.next null 的时候就跳出遍历cur.next node,这样即可完成尾插。 当链表为空的时候不论我们定义什么去代替head,都是竹篮打水一场空都无法进入遍历同时也会报空指针异常解决方法其实也很简单直接让head node即可。
具体分析见以下
如图 其实这其中也有遍历链表那味了其思想就是遍历到链表最后一个节点然后再进行尾插就行了。 //尾插法public void addLast(int data){ListNode node new ListNode(data);ListNode cur head;while (cur.next ! null){cur cur.next;}cur.next node;}但是这个代码是具有一定的问题的情景如下图 这个问题其实就是此时head是空的同时我们定义一个cur head那么cur也是空那么就无法进入到while循环中。修正如下
//尾插法public void addLast(int data){ListNode node new ListNode(data);ListNode cur head;if (cur null){head node;return;}//找到链表的尾巴注意是cur.next 不是curwhile (cur.next ! null){cur cur.next;}cur.next node;}3.8 任意位置插入
思路
定义cur走index-1步找到要插入位置的前一个节点进行插入
给一个情景定义cur index - 1,在1号、2号间插入node.
关键就在于我们要将0x66 - 0x777,null - 0x32,即node.next cur.next,cur.next node.
需要将head先移至2号位置注意用cur代替head防止head丢失然后
node.next cur.next使该节点的next域改为下一节点的地址再cur.next node.next使前一节点的next域改为该节点的地址。 //任意位置插入,第一个数据节点为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 node new ListNode(data);ListNode cur head;int tmp index - 1;while (tmp ! 0){cur cur.next;tmp--;}node.next cur.next;cur.next node;*///将上面这一坨封装ListNode cur findIndexSubOne(index);ListNode node new ListNode(data);node.next cur.next;cur.next node;}/*** 找到要删除节点位置的前一个节点* param index* return*/private ListNode findIndexSubOne(int index){ListNode cur head;int tmp index - 1;while (tmp ! 0){cur cur.next;tmp--;}return cur;}3.9 删除第一次出现关键字为key的节点
效果图如下 对于删除第一次出现的key值的节点若不是头节点我们只需将key值对应的节点的前一节点的next的域改为key值对应的节点的next域即可。 对于头节点直接head head.next即可。
找到要删除节点的前一个节点此时要删除的节点del cur.next;进行删除cur.next del.next //删除第一次出现关键字为key的节点public void remove(int key){if (head null){return;}//单独删除头节点if (head.val key){head head.next;return;}ListNode cur searchPrev(key);if (cur null){System.out.println(没有你要删除的数字);return;}ListNode del cur.next;cur.next del.next;}/*** 找到关键字key的前驱* param key* return*/private ListNode searchPrev(int key){ListNode cur head;while (cur.next ! null){if (cur.next.val key){return cur;}cur cur.next;}return null;}3.10 删除所有值为key的节点
情景如下
将值为23的删除
有种暴力的方法我们只需要多次调用3.9种的remove函数即可但是这并不是我们真正想要的要求遍历一遍就要删除完。
如图分析 //删除所有值为key的节点public void removeAllKey(int key){ListNode prev head;ListNode cur head.next;if (head null){return;}while (cur ! null){if(cur.val key){prev cur.next;cur cur.next;}else {prev cur;cur cur.next;}}if (head.val key){head head.next;}}3.11 清空
简单粗暴
public void clear() {this.head null;}温柔 public void clear(){while(this.head ! null){ListNode curNext this.head.next;this.head.next null;this.head cur.next;}}
