链表有哪些用途？
链表有任何实际用途吗？许多计算机科学书籍将它们与数组进行比较，并表示主要优点是它们是可变的。但是，大多数语言都提供数组的可变版本。那么链表在现实世界中是否有任何实际用途，或者它们只是计算机科学理论的一部分？
Do linked lists have any practical uses at all. Many computer science books compare them to arrays and say the main advantage is that they are mutable. However, most languages provide mutable versions of arrays. So do linked lists have any actual uses in the real world, or are they just part of computer science theory?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（10）
它们绝对是珍贵的（在流行的双链接版本和不太流行但适用时更简单、更快的单链接版本中）。例如，在“数组的可变版本”（例如 C++ 中的
std::vector）中的指定“随机”位置插入（或删除）新项目是O( N)，其中N是数组中的项目数，因为后面的所有项目（平均一半）都必须转移，这是一个O(N)操作；在列表中，如果您已经拥有指向“前一个”项目的指针，则它的时间复杂度为O(1)，即常数时间。像这样的 Big-O 差异绝对是巨大——现实世界中可用且可扩展的程序与玩具、“家庭作业”级别的程序之间的差异！-)They're absolutely precious (in both the popular doubly-linked version and the less-popular, but simpler and faster when applicable!, single-linked version). For example, inserting (or removing) a new item in a specified "random" spot in a "mutable version of an array" (e.g. a
std::vectorin C++) isO(N)whereNis the number of items in the array, because all that follow (on average half of them) must be shifted over, and that's anO(N)operation; in a list, it'sO(1), i.e., constant-time, if you already have e.g. the pointer to the "previous" item. Big-O differences like this are absolutely huge -- the difference between a real-world usable and scalable program, and a toy, "homework"-level one!-)链接列表有很多用途。例如，实现在最终用户看来是可变数组的数据结构。
如果您使用的编程语言提供了各种集合的实现，那么许多集合将使用链表来实现。当使用这些语言进行编程时，您通常不会自己实现链接列表，但了解它们可能是明智之举，这样您就可以了解您使用的库正在做出哪些权衡。换句话说，“只是计算机科学理论的一部分”集合包含了如果您要编写可以运行的程序则只需要知道的元素。
Linked lists have many uses. For example, implementing data structures that appear to the end user to be mutable arrays.
If you are using a programming language that provides implementations of various collections, many of those collections will be implemented using linked lists. When programming in those languages, you won't often be implementing a linked list yourself but it might be wise to understand them so you can understand what tradeoffs the libraries you use are making. In other words, the set "just part of computer science theory" contains elements that you just need to know if you are going to write programs that just work.
链表在现实世界中是否有任何实际用途，
链表的使用/示例（双向）可以在建筑物中升降。
- 一个人必须穿过所有楼层才能到达顶部（链表的尾部）。
- 一个人永远不能直接去某个随机楼层（必须经过中间楼层/节点）。
- 一个人永远不能超越顶层（旁边的尾节点被分配为空）。
- 一个人永远不能超出底层/最后一层（在链表中头节点之前被分配为空）。
So do linked lists have any actual uses in the real world,
A Use/Example of Linked List (Doubly) can be Lift in the Building.
- A person have to go through all the floor to reach top (tail in terms of linked list).
- A person can never go to some random floor directly (have to go through intermediate floors/Nodes).
- A person can never go beyond the top floor (next to the tail node is assigned null).
- A person can never go beyond the ground/last floor (previous to the head node is assigned null in linked list).
链表的主要应用是
它意味着两个多项式的加法/减法/乘法。
例如：p1=2x^2+3x+7 和 p2=3x^3+5x+2
p1+p2=3x^3+2x^2+8x+9
在运行时分配和释放内存。
*在符号表中
在平衡括号中
参考：-
http://www.cs.ucf.edu/courses/cop3502h.02 /linklist3.pdf
The main Applications of Linked Lists are
It means in addition/subtraction /multipication.. of two polynomials.
Eg:p1=2x^2+3x+7 and p2=3x^3+5x+2
p1+p2=3x^3+2x^2+8x+9
In allocation and releasing memory at runtime.
*In Symbol Tables
in Balancing paranthesis
Ref:-
http://www.cs.ucf.edu/courses/cop3502h.02/linklist3.pdf
是的，当然它很有用，原因有很多。
例如，任何时候您想要从列表中高效插入和删除。要找到插入位置，您需要进行 O(N) 搜索，但如果您已经有了正确的位置，则执行插入操作的时间复杂度为 O(1)。
此外，您从使用链接列表中学到的概念可以帮助您学习如何创建基于树的数据结构和许多其他数据结构。
Yes of course it's useful for many reasons.
Anytime for example that you want efficient insertion and deletion from the list. To find a place of insertion you have an O(N) search, but to do an insertion if you already have the correct position it is O(1).
Also the concepts you learn from working with linked lists help you learn how to make tree based data structures and many other data structures.
与向量相比，链表的主要优点是随机插入时间就像解耦一对指针并将它们重新耦合到新对象一样简单（当然，对于双向链表来说，这需要更多的工作） 。另一方面，向量通常会在插入时重新组织内存空间，导致速度明显变慢。然而，在执行诸如在容器末尾添加等操作时，列表的效率不高，因为需要一路遍历列表。
A primary advantage to a linked list as opposed to a vector is that random-insertion time is as simple as decoupling a pair of pointers and recoupling them to the new object (this is of course, slightly more work for a doubly-linked list). A vector, on the other hand generally reorganizes memory space on insertions, causing it to be significantly slower. A list is not as efficient, however, at doing things like adding on the end of the container, due to the necessity to progress all the way through the list.
不可变链表是持久数据结构最简单的示例，这就是为什么它是许多函数语言中的标准（有时甚至是唯一）数据结构。 Lisp、Scheme、ML、Haskell、Scala，应有尽有。
An Immutable Linked List is the most trivial example of a Persistent Data Structure, which is why it is the standard (and sometimes even only) data structure in many functional languages. Lisp, Scheme, ML, Haskell, Scala, you name it.
链表在动态内存分配中非常有用。这些列表用于操作系统。链表中的插入和删除非常有用。复杂的数据结构（例如树和图）是使用链表实现的。
Linked Lists are very useful in dynamic memory allocation. These lists are used in operating systems. insertion and deletion in linked lists are very useful. Complex data structures like tree and graphs are implemented using linked lists.
由于计算机内存的工作方式，根据需要增长的数组始终只是一种幻想。在底层，它只是一个连续的内存块，当添加足够的新元素时必须重新分配。同样，如果从数组中删除元素，则必须分配一个新的内存块，复制数组并释放前一个块以回收未使用的内存。链接列表允许您增大和缩小元素列表，而无需重新分配列表的其余部分。
Arrays that grow as needed are always just an illusion, because of the way computer memory works. Under the hood, it's just a continous block of memory that has to be reallocated when enough new elements have been added. Likewise if you remove elements from the array, you'll have to allocate a new block of memory, copy the array and release the previous block to reclaim the unused memory. A linked list allows you to grow and shrink a list of elements without having to reallocate the rest of the list.
链接列表很有用，因为元素可以在中间有效地拼接和删除，正如其他人指出的那样。然而，链表的缺点是引用位置较差。由于这个原因，我不喜欢使用列表，除非我明确需要这些功能。
Linked lists are useful because elements can be efficiently spliced and removed in the middle as others noted. However a downside to linked lists are poor locality of reference. I prefer not using lists for this reason unless I have an explicit need for the capabilities.