blocks|key|4689964|text|没有一种数据结构比另一种数据结构更普遍。有好处也有缺点，更好的取决于哪些优点和缺点对您的用例更重要。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4689965|4689966|插入和删除的复杂性是相同的|blockquote|4689967|4689968|4689969|首先，根本不可能插入或删除数组的元素。它们的大小保持不变。但我假设您的意思是“动态数组”数据结构，即std::vector和java.util.ArrayList+(不要与动态分配的数组混淆，后者也称为“动态数组”)。|offset|length|style|CODE|4689970|链接列表和动态数组之间的插入和删除复杂性并不相同。|4689971|4689972|，但在后面插入是O(n)。|4689973|4689974|4689975|给定链接链接列表的迭代器，可以在固定时间内在指向元素之后插入。因此，如果您将迭代器维护到列表的末尾，则可以在固定时间内插入其中。|4689976|除了复杂性外，链表相对于动态数组的一个重要优点是元素在内存中保持稳定。在向量中，如果添加一个元素超过了容量，那么所有迭代器和对现有元素的引用都将失效。迭代器以及对链接列表元素的引用仍然有效，直到元素被擦除。如果需要此属性，则使用动态数组不是选项。|4689977|entityMap^0|0|0|0|0|0|1E|B|1Q|J|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|10|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|11|8|@]|9|@]|A|$]]|$1|C|3|D|5|E|7|12|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|13|8|@]|9|@]|A|$]]|$1|G|3|-4|5|6|7|14|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|15|8|@$J|16|K|17|L|M]|$J|18|K|19|L|M]]|9|@]|A|$]]|$1|N|3|O|5|6|7|1A|8|@]|9|@]|A|$]]|$1|P|3|-4|5|6|7|1B|8|@]|9|@]|A|$]]|$1|Q|3|R|5|E|7|1C|8|@]|9|@]|A|$]]|$1|S|3|-4|5|6|7|1D|8|@]|9|@]|A|$]]|$1|T|3|-4|5|6|7|1E|8|@]|9|@]|A|$]]|$1|U|3|V|5|6|7|1F|8|@]|9|@]|A|$]]|$1|W|3|X|5|6|7|1G|8|@]|9|@]|A|$]]|$1|Y|3|-4|5|6|7|1H|8|@]|9|@]|A|$]]]|Z|$]]

No data structure is universally better than another data structure. There are benefits and drawbacks and which is better depends on what benefits and drawbacks are more important for your use case.
<blockquote>
the insertion and deletion complexities are same
</blockquote>
Firstly, it isn't possible to insert or delete elements of arrays at all. Their size remains constant. But I'll assume that you meant &quot;dynamic array&quot; data structure i.e. <code>std::vector</code> and <code>java.util.ArrayList</code> (not to be confused with dynamically allocated array which is also called &quot;dynamic array&quot;).
The insertion and deletion complexities between linked lists and dynamic array are not the same.
<blockquote>
but for the later it is O(n) to insert at the rear end.
</blockquote>
Given a an iterator to a linked linked list, you can insert after the pointed element in constant time. Hence, if you maintain an iterator to the end of the list, you can insert there in constant time.
An important advantage of linked list over the dynamic array, besides the complexity, is that the elements remain stable in memory. In vector, if adding an element exceeds the capacity, then all iterators and references to existing elements are invalidated. Iterators as well as references to linked list elements remain valid until the element is erased. If you need this property, then using a dynamic array is not an option.

blocks|key|4255457|text|链接列表作为独立的数据结构很少使用。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4255458|但是，通常情况下，通过将next和prev指针直接链接到对象本身，将对象链接到列表中。作为一种数据结构，这通常被称为“侵入性”链接列表。|offset|length|style|CODE|4255459|有时，这被用来向现有的数据结构添加特性。在Java中，您可以在LinkedHashMap中看到这一点，它将映射条目链接到一个列表中，保留它们的插入或访问顺序，并允许您将其用作LRU缓存。类似地，B%2Btree中的叶节点通常链接到列表中以简化遍历。有很多例子。|4255460|entityMap^0|0|C|4|H|4|0|V|D|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|M|8|@$D|N|E|O|F|G]|$D|P|E|Q|F|G]]|9|@]|A|$]]|$1|H|3|I|5|6|7|R|8|@$D|S|E|T|F|G]]|9|@]|A|$]]|$1|J|3|-4|5|6|7|U|8|@]|9|@]|A|$]]]|K|$]]

Linked lists, as independent data structures, are rarely used.
Quite often, however, objects are linked into a list by incorporating <code>next</code> and maybe <code>prev</code> pointers directly into the objects themselves. As a data structure, that is often referred to as an &quot;intrusive&quot; linked list.
Sometimes this is used to add features to existing data structures. In Java you can see this in <code>LinkedHashMap</code>, which links the map entries together into a list, preserving their insertion or access order and allowing you to use it as an LRU cache. Similarly, leaf nodes in a B+tree are often linked onto a list to simplify traversal. There are many examples.

I really don't see how linked lists are better than array , the insertion and deletion complexities are same , eg. , In array the insertion at rear is O(1) while for linked lists the insertion at head is O(1) , and simillarly insertion in arrays at front is O(n) but for the later it is O(n) to insert at the rear end.
<hr />
Apart from the only fact that linked lists are dynamic in nature ,I dont see any benefits of linked lists over arrays. Moreover , I can use a dynamic array to counter that problem.
<hr />
Again Array also have better results when we want to access an element.
<hr />
So can anybody please tell me why are linked lists better than array? And if they are not better , then why do we use it?

Benefits of linked list over array

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我真的不认为链表比数组更好，插入和删除的复杂性是一样的。，在数组中，后方插入为O(1)，而对于链接列表，头插入为O(1)，前面数组中的插入为O(n)，而后面插入则是O(n)。除了链接列表在本质上是动态的这一事实之外，我没有看到链接列表对数组的任何好处。此外，我可以使用动态数组来解决这个问题。同样，如果我们想要访问一个元...

问链表对数组的好处
EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问链表对数组的好处EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问链表对数组的好处
EN