高端的网站,办公软件开发公司,打开百度网页,钓鱼网站图片点击上方蓝字#xff0c;关注公众号链表概念的讲解链表是什么链表是一种线性数据结构#xff0c;每个节点都存有数据#xff0c;通过指针将各个节点链接在一起。链表的性质一致性: 每个节点有相同的数据结构#xff0c;相同的数据大小#xff0c;内存中占据相同的大小关注公众号链表概念的讲解链表是什么链表是一种线性数据结构每个节点都存有数据通过指针将各个节点链接在一起。链表的性质一致性: 每个节点有相同的数据结构相同的数据大小内存中占据相同的大小存储相同的数据类型。有序性: 节点之间的相对顺序固定排在某节点前面的节点就是它的前驱后面的节点就是它的后继所以定义里面有线性。链表的分类链接方式分类单向链表双向链表。ps: 代码展示只用单链表举例。单链表结构单链表中的每个结点包含数据指向后继节点的指针通过这种方式单链表将所有结点按顺序组织起来。节点定义class Node(object):单链表结构的Node节点 def __init__(self, data, next_nodeNone):Node节点的初始化方法。 data:存储的数据 next:下一个Node节点的引用地址 self.data data self.next next_node双链表结构双链表中的每个节点包含数据指向前驱和后继的指针。链表的基本操作链表基本操作: 插入搜索删除。以下分别讲每个操作是如何操作的时间复杂度多少为什么是那么多根据时间复杂度判断链表的适合场景。查找按照索引/值查找: 遍历找到对应的位置/值然后返回该节点。# 按照值查找node head_nodewhile node.data ! value: node node.next_node# 按照索引查找pos 0while pos ! index: node node.next_node pos 1时间复杂度是线性遍历的所以时间复杂度是O(n)。因为时间复杂度相对较高所以在大量数据需要经常用检索的时候就不要用链表了。插入按照index插入1.先创建新节点new_node2.找到要插入的位置的前驱节点pre3.新节点new_node指向pre的后继节点4.pre指向新节点new_node.next pred.nextpred.next new_node时间复杂度由于第2步要线性遍历去找index位置所以时间复杂度是O(n)。如果插入在头部就不需要找位置时间复杂度是O(1)。删除如何做删除的 1.找到待删节点的前驱pred2.把它的前驱节点的后继指向待删节点后继的后继pred.next pred.next.next时间复杂度因为要去找前驱所以线性遍历时间复杂度是O(n)。如果删除头部就不需要找位置时间复杂度是O(1)。链表常见的考点: 哑节点(边界条件)- 用于简化边界情况链表为空或链表的头结点和尾节点。解决办法自己创建一个哑节点然后把它的后继连接原节点。链表的实际应用通常用于顺序记录的存储无需提前分配空间仅适用小规模数据存储。对于适用的操作属性来说链表适合查找少无需排序的使用场景原因:是链表的查找效率不高通过调整指针可以快速调节节点的相对位置。业界应用: 小规模日志记录(通话记录或通讯录)读到内存中后可以以链表的方式进行存储操作系统中内存快的缓存也可以用链表来实现LRU缓存(利用了链表快速调整相对位置优势)。模式识别以下这些适用解决链表相关问题。runner and chaser类型题目中有关键词: 要寻找每个特定位置/相对位置。就用后移速度不同的快慢指针来解决使以下文章用到这个方法:【LeetCode-19-Remove Nth Node From End of List】删除链表的倒数第N个节点【LeetCode-141-Linked List Cycle】环形链表【LeetCode-876-Middle of the Linked List】链表的中间节点遍历并处理节点: 处理包括交换改数值改指针删除等等这类问题的处理方式是每次操作都是当前节点或某类节点每次处理单个或一对节点处理的时候先改变前驱指针再改变当前节点指针否则当前节点的next信息改变完之后就不对了通过先改变前驱的指针到达一个保存状态的目的。要动一个元素的后继之前先保存它的后继。【LeetCode24. Swap Nodes in Pairs】两两交换链表中的元素【LeetCode-25-Reverse Nodes in k-Group】K 个一组翻转链表【LeetCode-143-Reorder List】重排链表次头条。处理两个或多个链表处理方式是用while循环进行常规处理循环条件是list1非空并且list2非空当循环跳出后处理剩下的非空列表。循环至空再处理剩余。【LeetCode-21. Merge Two Sorted Lists】合并两个有序链表 应用递归处理(涉及链表倒序处理问题)解决当前问题依赖于存在的相似结构的子问题利用调用函数本身先解决子问题再利用子问题的结果解决当前的问题递归的出口通常是问题的初始条件n1的情况。链表问题一旦需要倒序处理或与树之间的数据结构进行相互转换往往会用到递归或者用栈来解决。LeetCode369,426因为这两道题要会员才能做我不能做所以没有写题解。自己实现一个单链表类实现插入查找删除的功能。class ListNode(object): def __init__(self, value): value: 节点的数据值 next: 节点的后继 self.value value self.next Noneclass MyLinkedList(object): def __init__(self): Initialize your data structure here. self.head ListNode(0) # 用哑结点来当头节点方便处理插入和删除的边界情况。 self.size 0 def get(self, index):按照索引查找 Get the value of the index-th node in the linked list. If the index is invalid, return -1. :type index: int :rtype: int # 异常情况: 如果索引无效 | 索引超出范围if index self.size:return -1 node self.headfor _ in range(index 1): # 记得链表的头结点是哑结点所以range后界要1 node node.nextreturn node.value # 是返回节点值 def addAtHead(self, val):添加到头节点 Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. :type val: int :rtype: None self.addAtIndex(0, val) def addAtTail(self, val):添加到尾节点 Append a node of value val to the last element of the linked list. :type val: int :rtype: None self.addAtIndex(self.size, val) def addAtIndex(self, index, val):按照索引添加node :type index: int :type val: int :rtype: None # 异常情况: 如果索引无效 | 索引超出范围if index self.size 1:return # 什么都不做# 找到要加入节点的前驱节点 node self.headfor _ in range(index): node node.next# 加入新节点 new_node ListNode(val) # 创建新节点 new_node.next node.next node.next new_node# 链表的总数加1 self.size 1 def deleteAtIndex(self, index):删除节点 因为删除操作的流程是待删节点node的前驱pre改变pre后继节点到node的后继节点所以找的节点应该是pre :type index: int :rtype: None # 异常情况: 如果索引无效 | 索引超出范围if index self.size:return # 什么都不做# 找到要删除的节点 node self.headfor _ in range(index): # 找到待删节点的前驱节点因为我们已经在头部加了哑结点所以真正的头部节点是不用单独处理的按照常规删节点的方式处理 node node.next# 删除待删节点 node.next node.next.next# 链表的总数减1 self.size - 1参考资料:- 力扣原创文章欢迎转载转载请在公众号菜单栏查看【联系我】。 喜欢本文的小伙伴点【在看】分享给你的朋友?↓↓↓
