山东嘉邦家居用品公司网站 加盟做经销商多少钱 有人做过吗,宜城网站建设网络推广,执法局网站建设目的,南昌seo专业团队文章目录 链表1、基本介绍2、单向链表2.1 带头节点的单向链表测试类#xff1a;链表实现类#xff1a; 2.2 不带头节点的单向链表2.3 练习测试类#xff1a;链表实现类#xff1a; 3、双向链表测试类#xff1a;双向链表实现类#xff1a; 4、单向环形链表**测试类**链表实现类 2.2 不带头节点的单向链表2.3 练习测试类链表实现类 3、双向链表测试类双向链表实现类 4、单向环形链表**测试类****实现类** 链表
1、基本介绍 什么是链表 链表Linked List是用链式存储结构实现的线性表。链表示意图 链表的组成数据域引用域数据域和引用域合称结点或元素 数据域存放数据元素自身的数据引用域存放相邻结点的地址 链表的特点 链表中元素的联系依靠引用域 具有线性结构的特点链表所使用的逻辑结构是线性结构 具有链式存储结构的特点所使用的物理存储结构是链式存储 链表的分类 单向链表单链表是一种最简的链表只有一个引用域1next 特点通过next可以访问到后继结点终端结点的引用域指向null 双向链表具有两个引用域prev和nextprev用来保存前驱结点的地址next用来保存后继结点的地址 特点通过next可以访问后继结点终端结点的next指向null通过prev可以访问到前驱节点起始结点的prev指向null 循环链表循环链表本质是一种特殊的单向链表只是它的终端结点指向了开始结点也就是next存放了开始结点的地址 特点所有结点都能具有前驱节点和后继结点 链表的使用场景对查找速度要求不高但对插入和删除速度要求高时可以使用链表。常见的比如
2、单向链表 单向链表简称单链表有带头结点的单链表也有不带头链表的单链表。 单链表的基本操作 非空判断判断链表中是否含有元素求表长度获取链表中所有元素的个数插入结点在单链表中添加一个新的结点删除结点删除单链表中的结点取表元素更具所给索引确定该索引所在链表的结点定位元素根据所给值确定该元素所在链表的索引号修改元素根据所给索引修改对应的结点清空链表清空链表中所有的元素
2.1 带头节点的单向链表 带头结点就是先固定一个头节点用来标识链表的初始位置它的data域不存任何东西它的next域用来第一个结点的地址每次遍历链表或定位结点都需要借助一个辅助变量temp来实现。 插入结点示意图 删除结点示意图 修改结点示意图 遍历经验总结当我们想要进行的操作的结点依赖于前一个结点时比如插入、删除、修改等操作操作就必须从head结点开始遍历否则会出现空指针异常当我们想要进行的操作不依赖前一个结点时就无须从head结点开始遍历比如根据id获取结点非空判断、获取链表长度、展示链表等操作。 测试类
package com.hhxy.linkedlist;import java.util.Scanner;import com.hhxy.queue.ArrayQueue2;
/*** 单向链表测试类* author ghp* 测试数据* 1 宋江 及时雨* 2 林冲 豹子头* 3 鲁智深 花和尚* 4 吴用 智多星*/
public class SingleLinkedListTest {public static void main(String[] args) {Scanner sc new Scanner(System.in);SingleLinkedListDemo1 sll new SingleLinkedListDemo1();//创建链表OUT:while(true) {System.out.println(-------------------单向链表操作界面-----------------);System.out.println(请输入操作指令);System.out.println(0 : 退出程序);System.out.println(1 : 在链尾添加结点);System.out.println(2 : 按id从小到大的顺序添加结点);System.out.println(3 : 根据id获取结点);System.out.println(4 : 根据id删除结点);System.out.println(5 : 获取链表中元素的个数);System.out.println(6 : 展示链表中所有的元素);System.out.println(7 : 根据id修改结点);System.out.println(8 : 清空链表);//用于接收用户输入int id;String name;String alias;Student student null;switch(sc.next()) {case 0: //退出程序System.out.println(正在退出程序~~~);break OUT;case 1: //在链尾添加结点System.out.println(请按照 id name alias 的格式输入要添加的元素);id sc.nextInt();name sc.next();alias sc.next();student new Student(id,name,alias);if(sll.add(student)) System.out.println(结点student添加成功);break;case 2://按id从小到大的顺序添加结点System.out.println(请按照 id name alias 的格式输入要添加的元素);id sc.nextInt();name sc.next();alias sc.next();student new Student(id,name,alias);if(sll.addById(student)) System.out.println(结点student添加成功);break;case 3://根据id获取结点System.out.println(请输入要获取结点的id号);id sc.nextInt();try {student sll.get(id);System.out.println(id号结点为student);}catch(Exception e){System.out.println(e.getMessage());}break;case 4://根据id删除结点System.out.println(请输入要删除结点的id号);id sc.nextInt();try {if(sll.remove(id)) System.out.println(结点删除成功);}catch(Exception e) {System.out.println(e.getMessage());}break;case 5://获取链表中结点的个数不包括头节点System.out.println(链表中的结点个数为sll.size());break;case 6://展示链表中所有的结点不包括头节点sll.show();break;case 7://根据id修改结点System.out.println(请按照 id name alias 的格式输入要修改的元素);student new Student(sc.nextInt(),sc.next(),sc.next());try {if(sll.update(student)) System.out.println(修改成功);}catch(Exception e) {System.out.println(e.getMessage());}break;case 8://清空链表if(sll.clear()) System.out.println(链表已成功清空);break;default:System.out.println(请输入有效指令);break;}}System.out.println(程序已退出);}
} 链表实现类
package com.hhxy.linkedlist;//结点类
class Student{//数据域将成员变量设置为public方便外部访问public int id;public String name;public String alias;//引用域public Student next;public Student(int id, String name, String alias) {this.id id;this.name name;this.alias alias;}Overridepublic String toString() {return [id id , name name , alias alias ];}
}//链表类
public class SingleLinkedListDemo1 {//初始化头结点Student head new Student(-99,,);/*** 判断链表是否为空* return true表示链表为空*/public boolean isEmpty() {//因为头节点是链表位置的标识不能动所以使用一个辅助引用来遍历链表Student temp head.next;if(temp!null) {//head后面存在至少一个元素所以链表不为空return false;}return true;}/*** 在链尾添加结点* param student 待添加的结点* return true表示添加成功*/public boolean add(Student student) {//同理因为链表头节点不能动。//注意需要是从头节点开始遍历因为链表可能为空如果从头节点后一个遍历当链表为空时会报空指针异常Student temp head;//遍历寻找尾结点。因为temphead所以是从头节点开始遍历while(temp.next ! null) {temp temp.next;}//已找到链表尾结点进行指向temp.next student;return true;}/*** 按照id从小到大的顺序添加结点* param student 待添加的结点* return true表示添加成功*/public boolean addById(Student student) {Student temp head;boolean flag true;//用于判断链表是加在尾结点还是加在结点之间while(temp.next ! null) {if(student.id temp.next.id) {//说明是添加在结点之间flag false;break;}temp temp.next;}if(flag) {//如果添加的结点是在尾结点temp.next student;}else {//添加的结点是在结点之间student.next temp.next;//切记先改变后一个指向再改变前一个指向temp.next student;}return true;}/*** 根据id获取结点* param id * return 返回对应id的结点*/public Student get(int id) {if(isEmpty()) {throw new RuntimeException(该链表为空);}Student temp head.next;//从head结点后面开始遍历boolean flag false;//判断链表中是否存在待获取的结点while(temp ! null) {if(temp.id id) {//找到id对应的结点flag true;break;}temp temp.next;}if(flag) {//如果找到id对应结点return temp;}else {//如果没有找到id对应的结点throw new RuntimeException(待获取的结点不存在);}}/*** 根据id删除结点* param id 待删除结点的id* return true表示删除成功*/public boolean remove(int id) {if(isEmpty()) {throw new RuntimeException(链表为空);}Student temp head;//删除结点需要依赖前一个结点所以从头节点开始遍历boolean flag false;//判断链表中是否存在待删除的结点while(temp.next ! null) {if(temp.next.id id) {//找到该结点flag true;break;}temp temp.next;}if(flag) {//如果找到了要删除的结点temp.next temp.next.next;}else {//如果没有找到id对应的结点throw new RuntimeException(待删除的结点不存在);}return true;}/*** 获取链表中结点的个数不包括头节点*/public int size() {Student temp head;int count 0;//这里虽然遍历了头节点但是没有遍历尾结点while(temp.next ! null) {count;temp temp.next;}return count;}/*** 展示链表中所有的结点不包括头节点*/public void show() {if(isEmpty()) {System.out.println(链表为空);return;}//注意不需要展示头节点Student temp head;while(temp.next ! null) {System.out.println(temp.next);temp temp.next;}}/*** 根据id修改结点* param student 待修改的结点* return true表示修改成功*/public boolean update(Student student) {if(isEmpty()) {throw new RuntimeException(链表为空);}Student temp head;boolean flag false;//判断链表是否修改成功while(temp.next ! null) {if(temp.next.id student.id) {//找到要修改的链表flag true;student.next temp.next.next;temp.next student;break;}temp temp.next;}if(flag) {//如果修改成功return true;}else {//如果链表中没有找到待删除的结点throw new RuntimeException(链表中不存在该结点);}}/*** 清空链表* return true表示清空成功*/public boolean clear() {/*方式一直接将头节点指向空(节约时间但占内存)* head.next null;* 除头节点以外其它结点存在引用JVM不会回收结点内存仍然会占据内存* 这种清楚方法很费内存 *///方式二将所有结点占据的内存都进行释放耗时但不占内存Student2 temp head;//这里需要从后往前遍历逐步去掉所有结点的引用否则无法遍历下取while(head.next ! null) {for (int i size(); i 1; i--) {temp temp.next;}temp.next null;}return true;}
}2.2 不带头节点的单向链表 略……逻辑思路都差不多只是将头节点换成一个头指针 不带头节点和带头结点的主要区别带头结点遍历的时候、不能将头节点进行计数而不带结点能够直接进行遍历
本质上两者并没有什么太大区别带头节点的链表没有指针头结点就相当于头指针而不带头节点的链表是由头指针的
注意这里所谓的指针和结点其实都是结点对象只是指针初始值为null结点要进行初始化
2.3 练习
反转链表示意图 合并链表示意图 测试类
/*** 练习题1获取链表倒数第k个结点* 练习题2将链表反转* 练习题3从尾到头打印链表的结点* 练习题4合并两个有序链表合并后仍然有序*/
//测试类
public class SingleLinkedListDemo3{public static void main(String[] args) {Node node1 new Node(1);Node node2 new Node(2);Node node3 new Node(3);SingleLinkedList sll new SingleLinkedList();sll.add(node1);sll.add(node2);sll.add(node3);System.out.println(链表原始状态);sll.show();System.out.println(------------------------);//测试1测试获取链表倒数第k个结点Node t sll.findLastIndexNode(sll, 1);System.out.println(sll.findLastIndexNode(sll,1));System.out.println(sll.findLastIndexNode(sll,2));System.out.println(sll.findLastIndexNode(sll,3));System.out.println(-------------------------);//测试2测试将链表反转sll.reverset(sll);System.out.println(反转后的链表);sll.show();System.out.println(-------------------------);//测试3从头到位打印链表System.out.println(反向打印链表);sll.reversetPrint(sll);System.out.println(-------------------------);//测试4将两个有序链表合并合并后仍然有序SingleLinkedList list1 new SingleLinkedList();SingleLinkedList list2 new SingleLinkedList();Node node4 new Node(4);Node node5 new Node(5);Node node6 new Node(6);Node node7 new Node(7);Node node8 new Node(8);Node node9 new Node(9);Node node10 new Node(10);Node node11 new Node(11);list1.add(node4);list1.add(node7);list1.add(node8);list1.add(node10);list1.add(node11);System.out.println(链表1);list1.show();System.out.println(链表2);list2.add(node5);list2.add(node6);list2.add(node9);list2.show();SingleLinkedList list new SingleLinkedList();list list.combine(list1, list2);System.out.println(合并后的链表);list.show();}
}链表实现类
package com.hhxy.linkedlist;import java.util.Stack;//结点类
class Node {int n;Node next;public Node(int n) {this.n n;}Overridepublic String toString() {return [n n ];}
}
//链表类
public class SingleLinkedList {//初始化头节点public Node head new Node(-99);/*** 添加结点*/public void add(Node node) {Node current head;while(current.next ! null) {current current.next;}current.next node;}/*** 获取链表的长度* return*/public int size() {Node current head.next;int count 0;while(current ! null) {count;current current.next;}return count;}/*** 展示*/public void show() {Node current head.next;while(current ! null) {System.out.println(current);current current.next;} }/*--------------------核心方法-------------------------*//*** 寻找链表倒数第k个结点* param index* return*/public Node findLastIndexNode(SingleLinkedList sll,int index) {Node head sll.head;if(index 0 || indexsll.size() || head.next null) {return null;}Node current head.next;//将指针从第二个结点开始往后移动index位for (int i 0; i size()-index; i) {current current.next;}return current;}/*** 将链表反转* param sll 待反转的链表*/public void reverset(SingleLinkedList sll) {Node head sll.head;if(head.next null || head.next.next null) {//当前链表为空或者只有一个结点直接返回return;}SingleLinkedList sllTemp new SingleLinkedList();//创建一个新链表Node headTemp sllTemp.head;Node temp null;//用来存旧链表的引用方便遍历旧链表Node current head.next;//辅助遍历旧链表while(current ! null) {temp current.next;//不保存新链表就会断开就无法进行遍历了current.next headTemp.next;//指向新创建的头结点的后面的结点headTemp.next current;//新创建的头结点指向插入的结点current temp;//指针往后移}head.next headTemp.next;}/*** 反向打印链表* param sll*/public void reversetPrint(SingleLinkedList sll) {Node head sll.head;if(head.next null) {return;}/*//方式一使用findLastIndexNode方法要先实现findLastIndexNode方法不值得推荐for(int i1;isll.size();i) {System.out.println(sll.findLastIndexNode(sll, i));}//方式二使用reverset方法要先实现reverset方法并且改变了链表的结构不值得推荐reverset(sll);sll.show();*///方式三使用栈强烈推荐StackNode stack new Stack();Node current head.next;while(current ! null) {stack.push(current);current current.next;}while(stack.size()0) {System.out.println(stack.pop());}}/*** 合并两个有序链表合并后仍然有序(这里我是默认按从小到大排序的)*/public SingleLinkedList combine(SingleLinkedList sll1,SingleLinkedList sll2) {Node head1 sll1.head.next;//用于遍历sll1链表Node head2 sll2.head.next;if(head1 null || head2 null) {//只要有一个链表为空就直接返回return head1 ! null ? sll1 : sll2;}SingleLinkedList sll new SingleLinkedList();//合并后的链表Node tempsll.head;//用来给sll链表添加结点的while (head1 ! null head2 ! null){if (head1.n head2.n){//链表1的结点是当前最小结点temp.next head1;//新链表连接最小结点temp temp.next;//每新增一个结点temp就往后移一位保证他在尾结点方便连接新结点head1 head1.next;//链表1的指针也往后移一位}else{//链表2的结点是当前最小结点temp.next head2;temp temp.next;head2 head2.next;}}if (head1 ! null head2 null){//经过一一段时间的合并后sll2的链表为空了直接就将sll1链表后面的结点拼接上去temp.next head1;}if (head1 null head2 ! null){temp.next head2;}return sll;}/*------------------------------------------------*/
}3、双向链表 双向链表相对单向链表就较为简单了因为每个结点既能往后遍历又能往前遍历 对于插入、删除、修改都无需像单链表一样依靠前一个结点。 与单链表的主要区别 遍历不仅可以往前遍历还可以往后遍历 插入、删除、修改不需要依赖前一个结点在链尾插入需要依赖尾结点 添加的时候需要进行双向绑定 双向链表插入示意图 双向链表删除示意图
测试类 和单向链表的测试方法相同 示意图 双向链表实现类 其实只要理解了单向链表再来看双向链表就会觉得so easy单向链表的方法双向链表都能使用只是添加和修改的时候需要多修改下prev的的指向。 package com.hhxy.linkedlist.doubles;
//结点类
class Student2{public int id;public String name;public String alias;public Student2 prev;//指向前一个结点public Student2 next;//指向后一个结点public Student2(int id, String name, String alias) {super();this.id id;this.name name;this.alias alias;}Overridepublic String toString() {return Student [n id , name name , alias alias ];}
}
//链表类
public class DoubleLinkedListDemo1 {//初始化头节点public Student2 head new Student2(-99,,);/*** 判断链表是否为空* return true表示链表为空*/public boolean isEmpty() {//因为头节点是链表位置的标识不能动所以使用一个辅助引用来遍历链表Student2 temp head.next;if(temp!null) {//head后面存在至少一个元素所以链表不为空return false;}return true;}/*** 在链尾添加结点* param student2 待添加的结点* return true表示添加成功*/public boolean add(Student2 student2) {//同理因为链表头节点不能动。//注意需要是从头节点开始遍历因为链表可能为空如果从头节点后一个遍历当链表为空时会报空指针异常Student2 temp head;//遍历寻找尾结点。因为temphead所以是从头节点开始遍历while(temp.next ! null) {temp temp.next;}//形成双向链表temp.next student2;student2.prev temp;return true;}/*** 按照id从小到大的顺序添加结点* param student2 待添加的结点* return true表示添加成功*/public boolean addById(Student2 student2) {Student2 temp head;boolean flag true;//用于判断链表是加在尾结点还是加在结点之间while(temp.next ! null) {if(student2.id temp.next.id) {//说明是添加在结点之间flag false;break;}temp temp.next;}if(flag) {//如果添加的结点是在尾结点//形成双向链表temp.next student2;student2.prev temp;}else {//添加的结点是在结点之间注意要形成双向指向student2.next temp.next;//切记先改变后一个指向再改变前一个指向temp.next.prev student2;//前面一根线temp.next student2;student2.prev temp;}return true;}/*** 根据id获取结点* param id * return 返回对应id的结点*/public Student2 get(int id) {if(isEmpty()) {throw new RuntimeException(该链表为空);}Student2 temp head.next;//从head结点后面开始遍历boolean flag false;//判断链表中是否存在待获取的结点while(temp ! null) {if(temp.id id) {//找到id对应的结点flag true;break;}temp temp.next;}if(flag) {//如果找到id对应结点return temp;}else {//如果没有找到id对应的结点throw new RuntimeException(待获取的结点不存在);}}/*** 根据id删除结点* param id 待删除结点的id* return true表示删除成功*/public boolean remove(int id) {if(isEmpty()) {throw new RuntimeException(链表为空);}//使用双向链表可以进行自我删除Student2 temp head.next;//删除结点需要依赖前一个结点所以从头节点开始遍历boolean flag false;//判断链表中是否存在待删除的结点while(temp ! null) {if(temp.id id) {//找到该结点flag true;break;}temp temp.next;}if(flag) {//如果找到了要删除的结点temp.prev.next temp.next;//前一根线if(temp.next ! null) {//要排除最后一个结点的可能否则会出现空指针异常temp.next.prev temp.prev;//后一根线}}else {//如果没有找到id对应的结点throw new RuntimeException(待删除的结点不存在);}return true;}/*** 获取链表中结点的个数* return*/public int size() {Student2 temp head;int count 0;while(temp.next ! null) {count;temp temp.next;}return count;}/*** 展示链表中所有的结点*/public void show() {if(isEmpty()) {System.out.println(链表为空);return;}Student2 temp head;while(temp.next ! null) {System.out.println(temp.next);temp temp.next;}}/*** 根据id修改结点* param student2 待修改的结点* return true表示修改成功*/public boolean update(Student2 student2) {if(isEmpty()) {throw new RuntimeException(链表为空);}Student2 temp head.next;boolean flag false;//判断链表是否修改成功while(temp ! null) {if(temp.id student2.id) {//找到要修改的链表flag true;//后一根线student2.next temp.next;if(temp.next!null) {//排除最后一个节点temp.next.prev student2;}//前一根线temp.prev.next student2;student2.prev temp.prev;break;}temp temp.next;}if(flag) {//如果修改成功return true;}else {//如果链表中没有找到待删除的结点throw new RuntimeException(链表中不存在该结点);}}/*** 清空链表* return*/public boolean clear() {/*方式一直接将头节点指向空(节约时间但占内存)* head.next null;* 除头节点以外其它结点存在引用JVM不会回收结点内存仍然会占据内存* 这种清楚方法很费内存 * return true;*///方式二将所有结点占据的内存都进行释放耗时但不占内存Student2 temp head;//这里需要从后往前遍历逐步去掉所有结点的引用否则无法遍历下取Student2 current head;while(current.next ! null) {current temp;current.next null;current.prev null;temp temp.next;}return true;}
}4、单向环形链表 基本和单向链表类似也可以分为带头节点和不带头结点点这里演示的是不带头结点的单向环形链表单向环形链表和单向链表唯一的区别尾结点的next不指向空而是指向开始节点。 主要思想还是在单链表那一节只要掌握单向链表这些双向链表还有单向循环链表就是弟弟(′д )…彡…彡直接套用第一节的接口实现所有的方法 测试类 和2.1一样换个对象就行了这个测试类真渣 实现类 这里主要记录以下按顺序插入结点的思路怕以后忘记了。其实主要思想还是和单向链表的addById方法的逻辑是一致的主要是要考虑循环思路主要如下 先将链表添加分为两大类首结点的添加 和 非首结点的添加因为首结点的添加需要自动成环再将非首结点的添加又分为在 添加在首结点之前 和 之后之前需要移动first指针之后不需要移动 示意图 删除结点 先将删除分为两大类删除头结点 和 删除普通结点删除头结点又可以分为两类链表只有一个头结点 和 除了头结点还有其它结点删除普通结点时需要注意链表是单向的删除操作需要依赖待删除结点的前一个结点 修改结点的逻辑思路和删除类似不在赘述示意图 清空链表链表的清空有两种方法一种是直接让firstnull这种清空简单省事但是是假清空链表仍然存在内存中 第二种方法是让每个结点的next指向空然后将firstnull这种费脑子但是省空间 package com.hhxy.linkedlist.circular;//结点类
class Student{public int id;public String name;public String alias;public Student next;public Student(int id, String name, String alias) {super();this.id id;this.name name;this.alias alias;}Overridepublic String toString() {return [id id , name name , alias alias ];}
}//链表类
public class CircularLinkedListDemo1 {private Student first null;//注意这是头指针不是头结点/*** 非空判断* return true表示为空*/public boolean isEmpty() {//因为是没有头结点所以直接判断firstif(first ! null) {return false;}else {return true;}}/*** 在尾结点添加结点* param student* return true表示结点添加成功*/public boolean add(Student student) {if(first null) {//对第一个结点进行单独考虑first student;first.next first;//构成环状return true;}else {Student current first;//找到最后一个结点while(current.next ! first) {current current.next;}//找到后将节点加入环形链表中current.next student;student.next first;return true;}}/*** 根据id从小到大的顺序添加结点* return true表示添加成功*/public boolean addById(Student student) {if(first null) {//第一个结点单独成环first student;first.next first;}else {Student current first;if(student.id current.id current first) {//说明这个结点比头结点还要小要将头指针移动位置current.next student;student.next current;first student;//将first移动到student上return true;}while(current.next ! first) {//寻早结点添加的位置if(student.id current.next.id) {//已找到添加的位置break;}current current.next;}student.next current.next;//切记一定要先改变后一根线不然链表会断裂current.next student;}return true;}/*** 根据id获取结点*/public Student get(int id) {if(isEmpty()) {throw new RuntimeException(链表为空);}Student current first;boolean flag false;while(true) {if(current.id id) {//找到就直接结束遍历flag true;break;}if(current.next first) {//如果是最后一个结点就表明还没有找到直接结束遍历break;}current current.next;//辅助指针后移遍历链表}if(flag) {//找到就返回这个结点return current;}else {//没有找到打印提示信息throw new RuntimeException(链表中不存在该结点);}}/*** 根据id删除结点*/public boolean remove(int id) {if(isEmpty()) {throw new RuntimeException(链表为空);}if(first.id id) {//当头结点就是要删除的结点时分类讨论if(first.next first) {//如果链表只有头结点时first null;return true;}else {//如果链表除了头结点还有其它结点时需要移动first指针Student current first;//找到尾结点while(current.next ! first) {current current.next;}current.next current.next.next;first current.next;//移动头指针return true;}}//删除普通结点Student current first;boolean flag false;//判断链表中是否存在该结点while(true) {if(current.next.id id) {//这里使用current.next判断是为了使用前一个结点//找到结点直接退出flag true;break;}if(current.next first) {//遍历完成直接退出break;}current current.next;}if(flag) {//找到待删除的结点利用前一个结点将其删除思路和单项链表是一样的current.next current.next.next;return true;}else {throw new RuntimeException(该结点不存在);}}/*** 获取链表长度*/public int size() {Student current first;if(isEmpty()) {return 0;//这里要不要都无所谓只是习惯了~~~}int count 0;while(true) {count;if(current.next first) {break;}current current.next;}return count;}/*** 展示链表*/public void show() {Student current first;if(first null) {//排除空链表throw new RuntimeException(链表为空);}while(true) {System.out.println(current);if(current.next first) {//当发现结点是最后一个结点直接退出打印break;}current current.next;}}/*** 根据id修改结点*/public boolean update(Student student) {if(isEmpty()) {throw new RuntimeException(链表为空);}if(student.id first.id) {//修改的结点是头节点if(first.next first) {//只有一个头节点first student;first.next student;return true;}else {//除了头节点还有其它结点Student current first;//找到尾结点while(current.next ! first) {current current.next;}student.next current.next.next;//修改后一根线current.next student;//修改前一根线first student;//修改头指针return true;}}//修改的结点是普通结点Student current first;boolean flag false;//判断链表中是否存在该结点while(current.next ! first) {if(current.next.id student.id) {//找到结点直接退出flag true;break;}current current.next;}if(flag) {student.next current.next.next;//修改后一根线防止链表断裂current.next student;return true;}else {throw new RuntimeException(不存在该结点);}}/*** 清空链表*/public boolean clear() {/*方式一直接将头节点指向空(节约时间但占内存)* first.next null;* 除头节点以外其它结点存在引用JVM不会回收结点内存仍然会占据内存* 这种清楚方法很费内存 * return true;*///方式二将所有结点占据的内存都进行释放耗时但不占内存if(isEmpty()) {return true;}if(first first.next) {//只有一个结点first null;return true;}Student temp first;//临时存储current的引用辅助遍历Student current first;//将链表每个结点的引用都断开这样每个结点都没有被引用就能被JVM给回收while(current.next ! first) {temp temp.next;current.next null;current temp;}//将最后一个结点的引用 和头指针 设为空current.next null;//不断开最后一个接待你的引用头节点就不会被回收first null;return true;}
}引用域是链表结点中一片很小的空间用来存放后继结点的地址 ↩︎
文章转载自： http://www.morning.sxjmz.cn.gov.cn.sxjmz.cn http://www.morning.dndk.cn.gov.cn.dndk.cn http://www.morning.fcwb.cn.gov.cn.fcwb.cn http://www.morning.ckfyp.cn.gov.cn.ckfyp.cn http://www.morning.zrmxp.cn.gov.cn.zrmxp.cn http://www.morning.frpfk.cn.gov.cn.frpfk.cn http://www.morning.cttgj.cn.gov.cn.cttgj.cn http://www.morning.gwjsm.cn.gov.cn.gwjsm.cn http://www.morning.hxrfb.cn.gov.cn.hxrfb.cn http://www.morning.yrbp.cn.gov.cn.yrbp.cn http://www.morning.ldzxf.cn.gov.cn.ldzxf.cn http://www.morning.ydryk.cn.gov.cn.ydryk.cn http://www.morning.tlfzp.cn.gov.cn.tlfzp.cn http://www.morning.ngqty.cn.gov.cn.ngqty.cn http://www.morning.qyrnp.cn.gov.cn.qyrnp.cn http://www.morning.yhplt.cn.gov.cn.yhplt.cn http://www.morning.txlxr.cn.gov.cn.txlxr.cn http://www.morning.hgkbj.cn.gov.cn.hgkbj.cn http://www.morning.fpzz1.cn.gov.cn.fpzz1.cn http://www.morning.mpmtz.cn.gov.cn.mpmtz.cn http://www.morning.nqwz.cn.gov.cn.nqwz.cn http://www.morning.bssjz.cn.gov.cn.bssjz.cn http://www.morning.wmqxt.cn.gov.cn.wmqxt.cn http://www.morning.lpcpb.cn.gov.cn.lpcpb.cn http://www.morning.mzwqt.cn.gov.cn.mzwqt.cn http://www.morning.kwqcy.cn.gov.cn.kwqcy.cn http://www.morning.qfplp.cn.gov.cn.qfplp.cn http://www.morning.yhjrc.cn.gov.cn.yhjrc.cn http://www.morning.wmqxt.cn.gov.cn.wmqxt.cn http://www.morning.qyxnf.cn.gov.cn.qyxnf.cn http://www.morning.rwfj.cn.gov.cn.rwfj.cn http://www.morning.jhxdj.cn.gov.cn.jhxdj.cn http://www.morning.fgsqz.cn.gov.cn.fgsqz.cn http://www.morning.ypjjh.cn.gov.cn.ypjjh.cn http://www.morning.wjndl.cn.gov.cn.wjndl.cn http://www.morning.rqkck.cn.gov.cn.rqkck.cn http://www.morning.xxrgt.cn.gov.cn.xxrgt.cn http://www.morning.kkwgg.cn.gov.cn.kkwgg.cn http://www.morning.tgqzp.cn.gov.cn.tgqzp.cn http://www.morning.xnwjt.cn.gov.cn.xnwjt.cn http://www.morning.gqfjb.cn.gov.cn.gqfjb.cn http://www.morning.ftldl.cn.gov.cn.ftldl.cn http://www.morning.xqkjp.cn.gov.cn.xqkjp.cn http://www.morning.nmyrg.cn.gov.cn.nmyrg.cn http://www.morning.jqbmj.cn.gov.cn.jqbmj.cn http://www.morning.ljbm.cn.gov.cn.ljbm.cn http://www.morning.brrxz.cn.gov.cn.brrxz.cn http://www.morning.cfcdr.cn.gov.cn.cfcdr.cn http://www.morning.xyyplp.cn.gov.cn.xyyplp.cn http://www.morning.fbnsx.cn.gov.cn.fbnsx.cn http://www.morning.lywpd.cn.gov.cn.lywpd.cn http://www.morning.lmqfq.cn.gov.cn.lmqfq.cn http://www.morning.snccl.cn.gov.cn.snccl.cn http://www.morning.hqbk.cn.gov.cn.hqbk.cn http://www.morning.rfxg.cn.gov.cn.rfxg.cn http://www.morning.bkryb.cn.gov.cn.bkryb.cn http://www.morning.bcdqf.cn.gov.cn.bcdqf.cn http://www.morning.xxwhz.cn.gov.cn.xxwhz.cn http://www.morning.ypmqy.cn.gov.cn.ypmqy.cn http://www.morning.psgbk.cn.gov.cn.psgbk.cn http://www.morning.gltmz.cn.gov.cn.gltmz.cn http://www.morning.yrflh.cn.gov.cn.yrflh.cn http://www.morning.dxtxk.cn.gov.cn.dxtxk.cn http://www.morning.mkccd.cn.gov.cn.mkccd.cn http://www.morning.rhpgk.cn.gov.cn.rhpgk.cn http://www.morning.pflpb.cn.gov.cn.pflpb.cn http://www.morning.pdgqf.cn.gov.cn.pdgqf.cn http://www.morning.chhhq.cn.gov.cn.chhhq.cn http://www.morning.mggwr.cn.gov.cn.mggwr.cn http://www.morning.pgggs.cn.gov.cn.pgggs.cn http://www.morning.mttck.cn.gov.cn.mttck.cn http://www.morning.hbdqf.cn.gov.cn.hbdqf.cn http://www.morning.mtgkq.cn.gov.cn.mtgkq.cn http://www.morning.jyfrz.cn.gov.cn.jyfrz.cn http://www.morning.gbhsz.cn.gov.cn.gbhsz.cn http://www.morning.yxbrn.cn.gov.cn.yxbrn.cn http://www.morning.fmrrr.cn.gov.cn.fmrrr.cn http://www.morning.wbrf.cn.gov.cn.wbrf.cn http://www.morning.gkmwk.cn.gov.cn.gkmwk.cn http://www.morning.mwlxk.cn.gov.cn.mwlxk.cn
