网站规划具体内容,深圳市住房和建设局官网房源,新昌网站建设,wordpress维护模式链表(维基百科) 链表#xff08;Linked list#xff09;是一种常见的基础数据结构#xff0c;是一种线性表#xff0c;但是并不会按线性的顺序存储数据#xff0c;而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储#xff0c;链表在插入的时候可以…链表(维基百科) 链表Linked list是一种常见的基础数据结构是一种线性表但是并不会按线性的顺序存储数据而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储链表在插入的时候可以达到O(1)的复杂度比另一种线性表顺序表快得多但是查找一个节点或者访问特定编号的节点则需要O(n)的时间而顺序表相应的时间复杂度分别是O(logn)和O(1)。使用链表结构可以克服数组链表需要预先知道数据大小的缺点链表结构可以充分利用计算机内存空间实现灵活的内存动态管理。但是链表失去了数组随机读取的优点同时链表由于增加了结点的指针域空间开销比较大。在计算机科学中链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成每个节点包含任意的实例数据data fields和一或两个用来指向上一个/或下一个节点的位置的链接links。链表最明显的好处就是常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序数据的访问往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型因为它包含指向另一个相同类型的数据的指针链接。链表允许插入和移除表上任意位置上的节点但是不允许随机存取。链表有很多种不同的类型单向链表双向链表以及循环链表。单向链表又名单链表、线性链表是链表的一种其特点是链表的链接方向是单向的对链表的访问要通过从头部开始依序往下读取. 定义 我们来看一下单向链表的定义实现 class ListNode(object):def __init__(self, value):self.value valueself.next None一个节点有value的属性定义该节点的值还有一个next的指针指向下一个节点类似于124563这样。 操作 单向链表的操作主要有添加一个节点删除一个节点遍历一条链表具体的实现如下 def add(pre, new_node):pre节点后面插入一个新的节点:param pre: pre节点:param new_node: 新插入的节点:return:new_code.next pre.nextpre.next new_nodedef delete(pre):pre节点的后面删除一个节点:return:if pre.next:pre.next pre.next.nextdef traverse(head):while head:print(head.value)head head.next在pre节点后面插入一个节点只需要把新节点的指针指向pre节点指针指向的节点把pre节点的指针指向新节点。 在pre节点后面删除一个节点只需要把pre节点的指针指向pre节点的指针的指针节点(要注意pre节点的指针不为None) 题目 我们来看一个关于链表的一个算法题来自于leetcode: 删除链表中的元素 删除链表中等于给定值 val 的所有元素。 示例给定: 1 -- 2 -- 6 -- 3 -- 4 -- 5 -- 6, val 6返回: 1 -- 2 -- 3 -- 4 -- 5 分析一般来讲我们首先会考虑到遍历一下这个链表移除掉value值等于给定val的节点就好。但是这里要返回一个新的链表我们知道对于单向链表我们只能知道当前元素的后置节点而不知道当前元素的前置节点。所以我们要构建一个前置节点。 看代码 def removeElements(head, val)::param head: listNode:param val: int:return: listNodedump ListNode(-1)dump.next headcur headpre dumpwhile cur:if cur.value val:pre.next cur.nextelse:pre pre.nextcur cur.nextreturn dump.next我们构建一个dump节点作为第一个节点cur节点为当前循环的节点pre节点为cur节点的前置节点。 当前节点的value为给定val的时候把当前cur的前置节点pre指针指向cur的后置节点也就是cur.next。然后接着遍历这个链表。 由于第一个节点dump是我们自己构造的(我用的值是-1你可以用其他不为val的值一般使用-1)它的next是给出的head我们只是对head做了调整。所以最后新的列表就是dump.next,也就是调整后的head。 学习技术交流群226704167愿和各位一起进步 转载于:https://www.cnblogs.com/lip0121/p/8668023.html