单链表学习总结
百度上定义:单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。
1、我的理解为:单链表,顾名思义,就是像一条链子一样的东西。比如一条自行车链子,由一个个的小节串在一起,链表也是由一个个称为节点的东西组成。
但他也被一个称之为“表”,所以也是像所有表格一样可以“填写”或“放置”一些数据的容器。
2、链表的节点,通常用 node 单词来表示。并且链表的第一个节点,我们称之为根节点,用root表示。
链表节点的大致结构也如下图所示
┌───┬───┐
| data next |
└───┴───┘
data域------用来存放各种数据的地方
next域------存放节点的直接后继的地址(位置)的指针域(链域),或者说就是像自行车链的一个小节要
和另一个节接上的扣一样,指向后面的那个小节。
3、链表和数组都可以存放数据,但是其显著不同在于
1:数组一旦定义了,长度就不可以改变,所能存储的东西也就有限。
而链表像自行车链子一样,可以拆,也可以加,无论是头尾还是中间,都可以对他进行更改。
2:访问数据时,数组相对快捷,但链表则比较复杂。
4、实现链表代码。简单的学生信息的存储。实现添加,索引删除,数据删除,修改,查找,插入,给学生分数排序等功能。
第一步:定义一个节点类;
/** * 节点类 * @author *节点node,节点内存储students对象 ,节点指向next */ public class Node { public Node(Students stu) {//声明一个节点,里面存储的是学生数据 this.stu = stu; } public Students stu;//数据 public Node next;//引用,指向下一个节点 }
第二步,定义一个学生对象,存储学生的姓名和分数信息;
/** * 定义Student学生类 * 学生的属性,构造方法,get,set方法 */ public class Students { private String name;//声明姓名属性 private int score;//声明学分属性 /** * 构造方法,用来创建对象的(类名 对象名 = new 构造方法(参数值,...);) */ public Students(String name,int score){ this.name = name; this.score = score; } /** * 给姓名属性设置值的方法 * @param name要赋给属性的参数 */ public void setName(String name){ this.name = name; } /** * 获取姓名属性值的方法 * @return name姓名属性的值 */ public String getName(){ return name; } public void setScore(int score){ this.score = score; } public int getScore(){ return score; } /** * 重写一个toString方法 */ public String toString(){ return "姓名:"+name+" 学分:"+score; } }
第三步,创建一个链表类;
/** * 链表类 * * @author 头节点,尾节点,节点总数 链表加减索引插入修改等方法 */ public class LinkedList { private Node root;// 头节点 private Node rear;// 尾节点 private int size;// 记录节点总数的计数器 /** * 添加节点到链表中的方法 * * @param node要被添加的新节点 * @param stu是链表内存储的数据 */ public void add(Students stu) { Node node = new Node(stu); if (root == null) {// 表示第一次添加节点 root = node; rear = node; } else { rear.next = node; rear = node;// 新的节点成为尾节点 } size++; } /** * * 索引指定位置的节点 * * @param index为索引的位置 * @return 返回节点内的数据 */ public Students get(int index) {// 索引 if (index < 0 || index >= size) { throw new RuntimeException("索引越界!"); } if (index == 0) { return root.stu; } Node node = root; for (int i = 0; i < index; i++) { node = node.next; } return node.stu; } /** * * 移除索引位置的节点 * * @param index索引位置 * @return 返回移除的节点数据 */ public Students remove(int index) {// 移除 if (index < 0 || index >= size) { throw new RuntimeException("索引越界!"); } if (index == 0) { Node node = root; Node temp = node.next; root = temp; size--; return node.stu; } else { Node node = root; for (int i = 0; i < index - 1; i++) { node = node.next; } Node temp = node.next; Node mode = temp.next; node.next = mode; size--; return temp.stu; } } /** * * 插入节点node * * @param stu需要插入的节点数据 * @param index需要插入的位置 */ public void Charu(Students stu, int index) {// 在索引位置插入节点 if (index < 0 || index > size) { throw new RuntimeException("索引越界!"); } Node node = new Node(stu); if (index == 0) { Node temp = root; root = node; node.next = temp; } else { Node node1 = root; for (int i = 0; i < index - 1; i++) { node1 = node1.next; } Node temp = node1.next; node1.next = node; node.next = temp; } size++; } /** * * 查找指定的数据所处的位置 * * @param stu为指定数据 * @return 返回数据所处的位置j */ public int get(Students stu) {// 查找相应的节点所在位置 int j = 0; Node node = root; for (int i = 1; i < size; i++) { node = node.next; if (stu.getName() == node.stu.getName() && stu.getScore() == node.stu.getScore()) { j = i; } } return j; } /** * 修改指定数据的方法 * * @param stu1指定的数据 * @param stu2用来替换的数据 */ public void Xiugai(Students stu1, Students stu2) {// 修改指定位置的节点 int j = get(stu1); remove(j); Charu(stu2, j); } /** * 交换两个节点所在的位置 * * @param stu1 * @param stu2 * */ public void Jiaohuan(Students stu1, Students stu2) { int i = get(stu1); int j = get(stu2); remove(i); Charu(stu2, i); remove(j); Charu(stu1, j); } /** * 获取链表中元素总数的方法 * * @return 返回size */ public int size() { return size; } }
第四步:创建一个链表测试类;
/** * 链表测试类 * * @author 输出检验前面的方法 */ public class ListTest { public static void main(String[] args) { // 创建链表对象 LinkedList list = new LinkedList(); list.add(new Students("张三", 70)); list.add(new Students("李四", 60)); list.add(new Students("王五", 77)); list.add(new Students("小雅", 68)); list.add(new Students("李明", 91)); // 检验添加方法 System.out.println(); System.out.println("增加后长度为" + list.size()); System.out.println("增加后为" ); for (int i = 0; i < list.size(); i++) { Students stu = list.get(i); System.out.println( stu.toString()); } // 检验交换方法 list.Jiaohuan(list.get(0), list.get(1)); System.out.println(); System.out.println("交换后" ); for (int i = 0; i < list.size(); i++) { Students stu = list.get(i); System.out.println( stu.toString()); } // sort排序 for (int i = 0; i < list.size(); i++) { for (int j = i; j < list.size(); j++) { if (list.get(i).getScore() < list.get(j).getScore()) { list.Jiaohuan(list.get(i), list.get(j)); } } } // 得出排序情况 System.out.println(); System.out.println("排序后" ); for (int i = 0; i < list.size(); i++) { System.out.println( list.get(i).toString()); } // 检验删除方法 list.remove(0); System.out.println(); System.out.println("删除后长度为" + list.size()); System.out.println("删除后为" ); for (int i = 0; i < list.size(); i++) { Students stu = list.get(i); System.out.println( stu.toString()); } // 检验插入方法 list.Charu(new Students("阿黄", 90), 0); System.out.println(); System.out.println("插入后长度为" + list.size()); System.out.println("插入后为" ); for (int i = 0; i < list.size(); i++) { Students stu = list.get(i); System.out.println( stu.toString()); } // 检验修改方法 list.Xiugai(new Students("阿黄", 90), new Students("小明", 90)); System.out.println(); System.out.println("修改后" ); for (int i = 0; i < list.size(); i++) { Students stu = list.get(i); System.out.println( stu.toString()); } } }
the end:
这段时间学习链表,自己似乎走了许多弯路。跌跌撞撞用了一个星期,才稍微摸清了苗头。
其实也知道并不是难,只是在第一次接触链表的那堂课,自己没有好好的接收一些知识,满心以为课后有了百度就完事大吉了。
结果在自己自以为完全搞明白了一些东西之后,却被指出根本思维是不正确的。
突然就想起了曾经一个学姐说过的一句话,没有很明显的联系,只是突然的想起吧。
Finally , learn to walk before you run.
相关推荐
关于双向链表的学习 有一些JAVA的内容 希望对大家有所帮助
C语言链表课件ppt,是你学习链表的好资料。
关于c语言的链表学习的课堂笔记,链表学习的详细知识点。
C语言链表学习教案.pptx
对新手来说很好 因为全面的学习链表的知识。
C# 链表学习例子 , 运行环境 .net 2003 。
uC/OS-II学习笔记—空闲链表和就绪链表
记录了C++实现的链表,包含常见的链表题目,用于后续补充
分享一下学习java链表的一些笔记新的!
链表这个很不错的,帮助我们很快拿下数据结构
链表指针 学习C++的经典例子0000
通过本程序可以进行链表的学习,对城市信息进行管理
该实例摘自范磊老师编写的《c++全方位学习》,该实例简明扼要,概括了链表的所有操作:插入节点、删除节点、及节点号排序、节点搜索等,特别适合于学习链表知识
链表的学习
c++结构体链表的简单排序,删除,添加等介绍和学习。。。
资源介绍:易语言链表学习源码,源码是链队列和链堆栈的应用。资源作者:
双向链表的API和C语言实现,程序说明在我的专栏《数据结构与算法学习笔记》中双向链表相关文章。包含了双向链表的结点结构体、表头结构体、创建双向链表、销毁双向链表、获取链表长度、清空双向链表、插入一个节点...
写更多的代码,用更多的指针, 用更多的指针,写更多的代码, C语言编程,我还是要用链表。
简单的链表实现大数阶乘的程序 是双向链表实现的 初学者可以看看
本程序针对链表进行一系列的操作,包括生成,插入,排序,创建已排链表等。对链表的学习以及后续程序的编写有一定帮助。