中国建设银行网站Ｅ路护航官网,网站搭建详细流程,北京网络营销岗位数量,浙江省工程建设协会网站目录
1. ArrayList的缺陷#xff1a;
2. 链表#xff1a;
2.1 链表的概念及结构#xff1a; 3. 链表的使用和模拟实现#xff1a;
3.1 构造方法#xff1a;
3.2 模拟实现#xff1a;
4. 源码分享#xff1a; 在我学习顺序表之后#xff0c;我就立马开始了链表的学…目录
1. ArrayList的缺陷
2. 链表
2.1 链表的概念及结构 3. 链表的使用和模拟实现
3.1 构造方法
3.2 模拟实现
4. 源码分享 在我学习顺序表之后我就立马开始了链表的学习但是在学习链表之前我就有一个疑问为什么明明有了顺序表这一种数据结构为什么我们还要有链表这一种数据结构呢
1. ArrayList的缺陷
通过对ArrayList的简单了解我们知道其实顺序表的底层是由数组来实现的他是一段连续的空间所以当ArrayList在增删元素的时候通过计算我们发现他的时间复杂度为O(n)效率比较低下如果数据很大的情况下使用顺序表进行增删操作会浪费非常多的时间所以就引入了链表这一种数据结构
2. 链表
2.1 链表的概念及结构
链表是一种物理存储结构上非连续存储结构数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
在现实生活中火车的结构就类似于我们的链表
链表的结构多种多样
1. 单向或者双向 2. 带头或者不带头 3.循环或者不循环 以上就是链表的结构所以一共有八种链表 单向不带头不循环链表 单向带头不循环链表 单向不带头循环链表 单向带头循环链表 双向不带头不循环链表 双向带头不循环链表 双向不带头循环链表 双向带头循环链表 3. 链表的使用和模拟实现
3.1 构造方法
链表源码提供了两个构造方法 这是不带参数的构造方法 这是带一个参数的构造方法将c中的全部元素都拷贝到链表中 3.2 模拟实现
首先我们需要创建一个My_LinkedList类(我们以单向不带头不循环链表为例)
在这个类中创建一个静态内部类称为ListNode一共有两个成员一个是value用来存放该节点的值的一个是next用来存放下一个节点的地址同时我们还可以写一个构造方法
再实例化一个头节点
public class My_LinkedList {static class ListNode {public int val;//数值域public ListNode next;//存储下一个节点的地址public ListNode(int val) {this.val val;}}public ListNode head new ListNode(0); //实例化头节点public My_LinkedList(int val) {head.val val; //构造方法}
} 1 addFirst方法
头插法在链表的第一个节点插入新的节点
假如我们在如图所示的链表中头插一个node节点 为了防止我们的首节点丢失我们需要先将首节点的地址传给新的节点再将新节点更新为head
/*** 头插法* addFrist*/public void addFirst(int data) {ListNode node new ListNode(data); //实例化一个节点node/*if(this.head null) {this.head node;}else {node.next this.head;this.head node;}*/node.next this.head; //将首节点的地址赋给新的节点this.head node; //将新的节点更新为head} 2 addLast方法
尾插法将新节点插入链表末端
public void addLast(int data) {ListNode node new ListNode(data); //实例化一个node节点if (head null) {head node; //若链表为空则直接将node更新为head} else {ListNode cur head; //实例化一个cur节点while (cur.next ! null) { //用cur节点去遍历链表知道cur节点为最后一个节点cur cur.next; }//cur.next null;cur.next node; //将node赋值给cur.next也就是将node节点放在了链表的最末端}} 3 size方法
得到并返回单链表的长度
//得到单链表的长度public int size() {int count 0; //创建整形变量count作为计数器ListNode cur this.head; //实例化cur 当前的头节点while (cur ! null) { //遍历整个链表count; //每遍历一个节点则countcur cur.next; //cur一直向后移动}return count; //返回单链表的长度} 4 add方法
任意位置插入将节点插入指定位置
在插入之前我先要检测给定的节点位置是否合理
private void checkIndexAdd(int index) {if (index 0 || index size()) { //如果位置不合理throw new MySingleListIndexOutOfException(任意位置插入的时候index不合法);} //若不合理则抛出异常}
MySingleListIndexOutOfException
public class MySingleListIndexOutOfException extends RuntimeException{public MySingleListIndexOutOfException() {super();}public MySingleListIndexOutOfException(String str) {super(str);}
}public void add(int index, int data) throws MySingleListIndexOutOfException {checkIndexAdd(index); //检查index位置是否合法if (index 0) { //如果index为0addFirst(data); //进行头插法return;}if (index size()) { //如果index 单链表长度addLast(data); //进行尾插法return;}ListNode node new ListNode(data); //实例化一个node节点值为dataListNode cur findIndexSubOne(index); //找到index下标的前一个节点node.next cur.next; //为了防止节点丢失先将要插入节点的next更新为前一个节点的原来的下一个节点的地址cur.next node; //将cur的next更新为新的节点的地址}
private ListNode findIndexSubOne(int index) {ListNode cur this.head; //实例化一个cur 头节点while (index - 1 ! 0) { //向后遍历index - 1次找到index下标节点的前一个节点cur cur.next;index--;}return cur; //返回当前节点 } 5 contains方法
查找是否包含关键子key在链表当中
//查找是否包含关键字key是否在单链表当中public boolean contains(int key) {if (head null) { //如果head为空则直接返回falsereturn false;}ListNode cur this.head; //实例化一个cur节点 头节点//cur ! null 说明 没有遍历完 链表while (cur ! null) { //cur不停向后遍历if (cur.val key) { //找到了keyreturn true; //返回true}cur cur.next;}return false; //循环结束cur.next null说明没有找到key返回false} 6 remove方法
删除第一次出现的值为key的节点
//删除第一次出现关键字为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 this.head; //实例化一个cur headwhile (cur.next ! null) { //遍历整个链表直到cur为最后一个节点为止if (cur.next.val key) { //如果找到了值为key的节点//进行删除了ListNode del cur.next; //实例化del节点为cur节点的下一个节点cur.next del.next; //将前一个节点的next更新为后一个节点的地址return;}cur cur.next;}System.out.println(未找到值为key的节点); //跳出循环说明没有值为key的节点} 7 removeAll方法
//删除所有值为key的节点public void removeAllKey(int key) {if (this.head null) { //如果head null则链表为空不能进行删除操作return;}//单独处理了头节点若头节点的值为key则头节点向后移动if(this.head.val key) {head head.next;}ListNode cur this.head.next; //实例化cur节点 head节点的下一个节点ListNode prev this.head; //实例化prev节点 head节点while (cur ! null) { //cur节点不断向后遍历if (cur.val key) { //如果cur.val key即找到了值为key的节点prev.next cur.next; //将prev节点即cur的前一个节点的next cur.next, 即删除了cur位置的节点cur cur.next; //cur继续向后走查找值为key的节点} else { //若cur.val ! keyprev cur; //prev和cur一起向后移动 cur cur.next;}}} 8 clear方法
clear方法的实现有两种方法
第一种
public void clear() {this.head null;}
这种做法比较粗暴直接将head置为空由于之前的链表中的节点没有了引用故会被系统给自动回收
第二种
/*** 当我们 执行clear这个函数的时候会将这个链表当中的所有的节点回收*/public void clear() {ListNode cur this.head; //令cur headListNode curNext null; //实例化一个curNextwhile (cur ! null) { curNext cur.next; //将curNext更新为cur.nextcur.next null; //再将cur节点的next置为空cur curNext; //再将cur更新为curNext一个一个的去删除链表中的所有的节点}head null; //最后将head置为空即可}
4. 源码分享
在我的模拟实现源码中我多写了createList方法和display方法即创建链表和打印链表方法为的是模拟实现后方便进行测试以找出代码的不足
public class My_LinkedList {static class ListNode {public int val;//数值域public ListNode next;//存储下一个节点的地址public ListNode(int val) {this.val val;}}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 head;while (cur ! null) {System.out.print(cur.val );cur cur.next;}System.out.println();}/*** 从指定的节点开始答应** param newHead*/public void display(ListNode newHead) {ListNode cur newHead;while (cur ! null) {System.out.print(cur.val );cur cur.next;}System.out.println();}/*** 头插法* addFrist*/public void addFirst(int data) {ListNode node new ListNode(data); //实例化一个节点node/*if(this.head null) {this.head node;}else {node.next this.head;this.head node;}*/node.next this.head; //将首节点的地址赋给新的节点this.head node; //将新的节点更新为head}//尾插法 O(n)public void addLast(int data) {ListNode node new ListNode(data); //实例化一个node节点if (head null) {head node; //若链表为空则直接将node更新为head} else {ListNode cur head; //实例化一个cur节点while (cur.next ! null) { //用cur节点去遍历链表知道cur节点为最后一个节点cur cur.next;}//cur.next null;cur.next node; //将node赋值给cur.next也就是将node节点放在了链表的最末端}}public void add(int index, int data) throws MySingleListIndexOutOfException {checkIndexAdd(index); //检查index位置是否合法if (index 0) { //如果index为0addFirst(data); //进行头插法return;}if (index size()) { //如果index 单链表长度addLast(data); //进行尾插法return;}ListNode node new ListNode(data); //实例化一个node节点值为dataListNode cur findIndexSubOne(index); //找到index下标的前一个节点node.next cur.next; //为了防止节点丢失先将要插入节点的next更新为前一个节点的原来的下一个节点的地址cur.next node; //将cur的next更新为新的节点的地址}/*** 找到index-1位置的节点** param index* return 该节点的地址*/private ListNode findIndexSubOne(int index) {ListNode cur this.head; //实例化一个cur 头节点while (index - 1 ! 0) { //向后遍历index - 1次找到index下标节点的前一个节点cur cur.next;index--;}return cur; //返回当前节点}private void checkIndexAdd(int index) {if (index 0 || index size()) { //如果位置不合理throw new MySingleListIndexOutOfException(任意位置插入的时候index不合法);} //若不合理则抛出异常}//查找是否包含关键字key是否在单链表当中public boolean contains(int key) {if (head null) { //如果head为空则直接返回falsereturn false;}ListNode cur this.head; //实例化一个cur节点 头节点//cur ! null 说明 没有遍历完 链表while (cur ! null) { //cur不停向后遍历if (cur.val key) { //找到了keyreturn true; //返回true}cur cur.next;}return false; //循环结束cur.next null说明没有找到key返回false}//删除第一次出现关键字为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 this.head; //实例化一个cur headwhile (cur.next ! null) { //遍历整个链表直到cur为最后一个节点为止if (cur.next.val key) { //如果找到了值为key的节点//进行删除了ListNode del cur.next; //实例化del节点为cur节点的下一个节点cur.next del.next; //将前一个节点的next更新为后一个节点的地址return;}cur cur.next;}System.out.println(未找到值为key的节点); //跳出循环说明没有值为key的节点}//删除所有值为key的节点public void removeAllKey(int key) {if (this.head null) { //如果head null则链表为空不能进行删除操作return;}//单独处理了头节点若头节点的值为key则头节点向后移动if(this.head.val key) {head head.next;}ListNode cur this.head.next; //实例化cur节点 head节点的下一个节点ListNode prev this.head; //实例化prev节点 head节点while (cur ! null) { //cur节点不断向后遍历if (cur.val key) { //如果cur.val key即找到了值为key的节点prev.next cur.next; //将prev节点即cur的前一个节点的next cur.next, 即删除了cur位置的节点cur cur.next; //cur继续向后走查找值为key的节点} else { //若cur.val ! keyprev cur; //prev和cur一起向后移动cur cur.next;}}}//得到单链表的长度public int size() {int count 0; //创建整形变量count作为计数器ListNode cur this.head; //实例化cur 当前的头节点while (cur ! null) { //遍历整个链表count; //每遍历一个节点则countcur cur.next; //cur一直向后移动}return count; //返回单链表的长度}/*** 当我们 执行clear这个函数的时候会将这个链表当中的所有的节点回收*/public void clear() {//this.head null;//这种做法 比较粗暴ListNode cur this.head; //令cur headListNode curNext null; //实例化一个curNextwhile (cur ! null) {curNext cur.next; //将curNext更新为cur.nextcur.next null; //再将cur节点的next置为空cur curNext; //再将cur更新为curNext一个一个的去删除链表中的所有的节点}head null; //最后将head置为空即可}
}以上就是链表的所有的内容了感谢大家的观看 制作不易三连支持 谢谢 以上的模拟实现代码未必是最优解仅代表本人的思路望多多理解谢谢 最后送给大家一句话同时也是对我自己的勉励 在心里种花人生才不会荒芜
