链表有单向链表、双向链表和循环链表,此篇文章只讲解单向链表,另外两种会在下一篇文章中补充,要真正理解和使用链表的话,建议三种链表结构都了解一下。
平时我们使用最多的数据结构应该是数组,很多东西都可以用数组来轻松实现,但在某些编程语言中,数组的长度是预先设定好的,想要额外添加元素或者删除元素是一件比较困难的事。那么使用链表的话恰恰就解决了这些问题,对于链表来说删除或添加一个元素是非常方便的,除了数据的随机访问(可以实现但是比较麻烦,比如可以通过添加和操作索引值来实现),它几乎可以用在任何可以使用一维数组的情况中。
链表的定义
链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。指向另一
个节点的引用叫做链。
一般的链表都会额外添加一个头节点(作为辅助)和尾节点,例如下面这种样子
数组元素靠它们的位置进行引用,链表元素则是靠相互之间的关系进行引用。在上图中,我们说 bread 跟在 milk 后面,而不说 bread 是链表中的第二个元素。遍历链表,就是跟着链接,从链表的首元素一直走到尾元(但这不包含链表的头节点,头节点常常用来作为链表的接入点)。上图中另外一个值得注意的地方是,链表的尾元素指向一个 null 节点。
插入新元素:
向单向链表中插入一个节点,只需要修改它前面的节点(前驱),使其指向新加入的节点,而新加入的节点则指向原来前驱指向的节点。上图演示了如何在 eggs 后加入 cookies。
删除链表中已有元素:
从链表中删除一个元素也很简单。只需要将待删除元素的前驱节点指向待删除元素的后继节点。上图展示了从单向链表中删除Bacon。
除了插入和删除,链表还有其他一些操作,后面将给出讲解。
设计一个基于对象的链表
我们需要设计两个类,Node 类用来表示节点, LinkedList 类提供插入节点、删除节点、显示列表元素的方法,以及其他一些辅助方法。
Node类:
function Node(element) { this.element = element;//当前节点的数据 this.next = null;//下一个节点数据 }
LinkedList 类:
function LList() { this.head = new Node("head");//头节点 } LList.prototype={ //查找某一节点 find:function (item) { var currNode = this.head; while (currNode.element != item) { currNode = currNode.next; } return currNode; }, //向某一元素后面插入新节点 insert:function(newElement,item){ var newNode = new Node(newElement); var current = this.find(item); newNode.next = current.next; current.next = newNode; }, //查找某一节点的前一个节点(前驱) findPrevious:function(item){ var currNode = this.head; while (!(currNode.next == null) &&(currNode.next.element != item)) { currNode = currNode.next; } return currNode; }, //删除某一个节点 remove:function(item){ var prevNode = this.findPrevious(item); if (!(prevNode.next == null)) { prevNode.next = prevNode.next.next; } }, //修改某一节点的数据 edit:function(item,newItem){ var element=this.find(item); element.element=newItem; }, //在控制台打印出所有节点(为了方便预览) display:function(){ var currNode = this.head; while (!(currNode.next == null)) { console.log(currNode.next.element); currNode = currNode.next; } } }
测试:
var names = new LList(); names.insert("likek", "head");//往头节点后插入节点likek names.insert("zhangsan", "likek");//往likek后插入节点zhangsan names.insert("lisi", "zhangsan");//往zhangsan后插入节点lisi names.insert("wangwu", "lisi");//往lisi后插入节点wangwu names.display(); /*likek zhangsan lisi wangwu*/ names.remove("zhangsan");//删除zhangsan节点 names.display(); /*likek lisi wangwu*/ names.edit("lisi","wangnima");//将lisi节点改为wangnima names.display(); /*likek wangnima wangwu*/
相关推荐
数据结构与算法--链表 很好的哦 欢迎下载
算法-数据结构和算法-8-双向链表.rar
【数据结构与算法 - 链表】 C语言实现 实现模块化
算法-数据结构和算法-6-链表和单链表的实现过程.rar
数据结构-基本算法-静态链表(学生时代源码,调试可运行)
严蔚敏-数据结构--链表实现c++实现 还不错哦!``
数据结构与算法-链表(线性表的链表表示和实现) 定义线性表节点的结构.pdf
数据结构实验--链表进行多项式求和与求积 数据结构实验--链表进行多项式求和与求积 数据结构实验--链表进行多项式求和与求积 数据结构实验--链表进行多项式求和与求积 数据结构实验--链表进行多项式求和与求积
《数据结构与算法》-李春葆 实验报告-基于二叉链存储的树形结构算法实践---二叉链表
数据结构与算法----线性表及Java实现顺序表、链表、栈、队列 定义线性表节点的结构.pdf
实现双向链表的定义,冒泡排序,插入,删除,输出,反向。
《数据结构与算法》-李春葆 实验报告-基于邻接链表存储的无向图形算法实践-邻接链表
数据结构与算法 c语言 线性表-静态链表 静态链表源码
数据结构实验报告-利用链表实现简易学生信息管理系统,内容包含实验目的,实验环境,实验源代码,实验运行截图,实验小结等。 说明:如有bug,还请反馈!
数据结构与算法(Python) 一、引入概念 1-01算法引入 1-02 时间复杂度与大O表示法 1-03-最坏时间复杂度与计算规则 1-04-常见时间复杂度与大小关系 1-05-代码执行时间测量模块 1-06-Python列表类型不同操作的...
c语言链表的排序算法-排序链表最快的算法是什么?.pdf
博文C++数据结构X篇_04_单向链表框架搭建、实现和测试(链表的定义,常用操作的实现等)的配套资源
链表实战题目4 - 链表入环的第一个节点给定一个链表,返回链表开始入环的第一个节点。如果链表无环,则返回 null。为了表示给定链表中的环,我们使用整数 pos
数据结构-基本算法-孩子兄弟链表(学生时代源码,调试可运行)