第五章 链表
ps:整个文章所涉及的源代码我都发布在我的Github主页上,大家可以自行下载,如果对您有一丢丢的帮助的话,记得在我的github项目上点上【star】哟,当然不要忘了在本篇文章下方【点赞】哦~,你们的支持将是我最大的动力!
(利他之心是每个优秀开发者的传统美德!——@惜墨的少年)
定义链表
链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。指向另一个节点的引用叫做链。数组元素靠它们的位置进行引用,链表元素则是靠相互之间的关系进行引用。
上图中,我们说chaoge跟在draven后面,而不说chaoge是链表中的第二个元素。遍历链表 ,就是跟着链表,从链表的首元素一直走到尾元素(但这不包含链表的头节点,头节点常常用来作为链表的接入点),链表的尾元素指向一个null节点。许多链表的实现都在链表最前面有一个特殊节点,叫做头节点。
链表中插入节点效率很高。向链表中插入节点,需要修改前面的节点(前驱),使其指向新加入的节点,而新加入的节点则指向原来前驱指向的节点。
从链表中删除一个元素也很容易。将待删除元素的前驱节点指向待删除元素的后继节点,同时将待删除元素指向null。
设计一个基于对象的链表
Node类用来表示节点,LinkedList类提供插入节点、删除节点、显示列表元素的方法。
Node类
LinkedList类
遍历链表,查找给定数据
从链表中删除一个节点
从链表中删除节点时,需要先找到待删除节点前面的节点,修改它的next属性,使其不再指向待删除节点,而是指向待删除节点的下一个节点。