2023网站分享,商洛网站建设公司电话,wordpress全站转移,缪斯设计网站一、前言
链表的历史
于1955-1956年#xff0c;由兰德公司的Allen Newell、Cliff Shaw和Herbert A. Simon开发了链表#xff0c;作为他们的信息处理语言的主要数据结构。链表的另一个早期出现是由 Hans Peter Luhn 在 1953 年 1 月编写的IBM内部备忘录建议在链式哈希表中使…一、前言
链表的历史
于1955-1956年由兰德公司的Allen Newell、Cliff Shaw和Herbert A. Simon开发了链表作为他们的信息处理语言的主要数据结构。链表的另一个早期出现是由 Hans Peter Luhn 在 1953 年 1 月编写的IBM内部备忘录建议在链式哈希表中使用链表。
到 1960 年代初链表和使用这些结构作为主要数据表示的语言的实用性已经很好地建立起来。MIT 林肯实验室的 Bert Green于 1961 年 3 月在 IRE Transactions on Human Factors in Electronics 上发表了一篇题为“用于符号操作的计算机语言”的评论文章总结了链表方法的优点。1964 年 4 月Bobrow 和 Raphael 的一篇评论文章“列表处理计算机语言的比较”发表在 ACM 通讯中。
二、链表数据结构
在计算机科学中链表是数据元素的线性集合元素的线性顺序不是由它们在内存中的物理地址给出的。它是由一组节点组成的数据结构每个元素指向下一个元素这些节点一起表示线性序列。 在最简单的链表结构下每个节点由数据和指针存放指向下一个节点的指针两部分组成这种数据结构允许在迭代时有效地从序列中的任何位置插入或删除元素。
链表的数据结构通过链的连接方式提供了可以不需要扩容空间就更高效的插入和删除元素的操作在适合的场景下它是一种非常方便的数据结构。但在一些需要遍历、指定位置操作、或者访问任意元素下是需要循环遍历的这将导致时间复杂度的提升。
三、链表分类类型
链表的主要表现形式分为单向链表、双向链表、循环链表接下来我们分别介绍下。
1. 单向链表
单链表包含具有数据字段的节点以及指向节点行中的下一个节点的“下一个”字段。可以对单链表执行的操作包括插入、删除和遍历。 2. 双向链表
在“双向链表”中除了下一个节点链接之外每个节点还包含指向序列中“前一个”节点的第二个链接字段。这两个链接可以称为forwards和backwards或next和prevprevious。 3. 循环链表
在列表的最后一个节点中链接字段通常包含一个空引用一个特殊的值用于指示缺少进一步的节点。一个不太常见的约定是让它指向列表的第一个节点。在这种情况下列表被称为“循环”或“循环链接”否则它被称为“开放”或“线性”。它是一个列表其中最后一个指针指向第一个节点。 常见面试问题
描述一下链表的数据结构Java 中 LinkedList 使用的是单向链表、双向链表还是循环链表链表中数据的插入、删除、获取元素时间复杂度是多少什么场景下使用链表更合适
