blocks|key|863008|text|如果存储链表的尾部，那么插入到链表中肯定比插入到二叉树中快。如果二叉树是不平衡的，那么插入到二叉树的最坏情况是O(N)+(最好的情况是O(Log))。如果它是平衡的，那么插入就是O(log+N)，但是需要内部管理来保持它的平衡。如果保持尾部不变，则插入链表的时间为O(1)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|863009|此外，与BillyONeal+mentioned一样，二叉树通常是关联结构，而链表不是。|offset|length|863010|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/questions/2036251/advantages-of-linked-lists-over-binary-trees/2036255#2036255^0|0|F|9|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@]|9|@$D|P|E|Q|1|R]]|A|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|A|$]]]|G|$H|$5|I|J|K|A|$L|M]]]]

If the tail of a linked list is stored, then insertion into a linked list is decidedly faster than insertion into a binary tree. Insertion into a binary tree is O(N) at worst case (O(log N) at best) if it's unbalanced. If it's balanced, then insertions are O(log N), but there is house keeping involved in keeping it balanced. Insertion into a linked list is O(1) if the tail is kept.

Also, as BillyONeal <a href="https://stackoverflow.com/questions/2036251/advantages-of-linked-lists-over-binary-trees/2036255#2036255">mentioned</a>, a binary tree is usually an associative structure, whereas linked lists are not.

blocks|key|2271362|text|与二叉树相比，从链表中删除项更容易/更快，因为二叉树只需要很少的操作就可以修复树。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2271363|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

It's easier/faster to delete items from a linked list compared to a binary tree which could require few operations to fix the tree.

blocks|key|2271332|text|链表通常不用作关联容器(READ:不用作字典)+--仅用作项的文字列表，如数组。当需要这样一种简单的数据结构时，二叉树的性能很差。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2271333|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

A linked list is not generally used as an associative container (READ: Not to be used as a dictionary) -- only as a literal list of items, like an array. Binary trees' performance when such a simple data structure is desired is poor.

blocks|key|863038|text|在链表中，对象是按容器本身排序的，因此您不需要为对象提供比较函数。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|863039|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

In linked list the objects are ordered by the container itself, so you don't need to have a comparison function for the objects.

blocks|key|863079|text|这是个合理的问题。我喜欢使用最“紧密”地满足我需求的容器。例如，当您所需要的只是一个没有实际结果的队列时，您可以使用列表……但是..。队列针对从前面弹出和在后面插入这一特定任务进行了高度优化，不需要额外的指针或其他任何东西。通过使用最合适的类，您可以确保不会得到任何额外的错误，即使它具有相同的Big-O。有时这些隐藏的常量确实很重要。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|863080|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

A fair question. I like to use the container that most "tightly" fits my needs. For example, you can use a list when all you need is a queue with no real consequence either... but... queues are highly optimized for this one specific task of popping off the front, and inserting at the back, with no extra pointers, or anything. By using the most appropriate class, you can be sure you're not getting any extra fluff, even if it has the same Big-O. Sometimes those hidden constants do matter.

blocks|key|863116|text|这主要取决于场景。如果保持链表的尾部，则在链表中插入较快。删除在链表中是相当快的，但在搜索的情况下，在树中更好(对于高度平衡树是o(log(n)+)，而在链表中是o(n)+)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|863117|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

It mostly depends on scenario. If tail of linked list is maintained then insertion is fast in linked list. Deletion is quite fast in linked list but in case of searching it is better in trees( o(log(n) for height balance tree ) while o(n) in linked list.

blocks|key|863165|text|我假设您谈论的是实际的二进制搜索树，其中节点是使用算法添加的，以最大限度地提高检索性能。而不是每个节点最多具有2个子节点的简单树。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|863166|链表通常是未排序的，因此添加新节点只是一个O(1)操作，通常是通过追加到链表的尾部来实现的。|863167|另一方面，二叉树必须以特定的排序机制存储节点(并可能强制平衡)，以提供更有效的搜索/检索操作。|863168|如果您的算法不需要非常高效地检索项，同时还提供高效的项排序，那么链表可能就是您需要的全部。|863169|队列和堆栈是可以使用链表愉快地实现的数据结构的示例。|863170|注意:插入到链表中的操作与基本的加法/追加操作不同(较慢)。插入通常需要沿着列表遍历，直到找到正确的位置，O(n)，其中n是列表长度。追加只是添加到列表的尾部(因此是O(1))|863171|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|P|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|Q|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|R|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|S|8|@]|9|@]|A|$]]|$1|L|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|M|$]]

I assume you're talking about actual binary search trees where the nodes are added using algorithms to maximize retrieval performance. As opposed to a simple tree where each node has a maximum of 2 child nodes.

A linked list is often unsorted and so addition of new nodes is simply an O(1) operation normally by appending to the tail of the list. 

On the other hand a binary tree must store nodes in a specific ordering mechanism (and possibly enforce balancing) to provide for a more efficient searching/retrieval operation.

If your algorithm does NOT need to retrieve items very efficiently while also provide efficient sorting of the items, a linked list is probably all you need. 

Queues and Stacks are examples of data structures that can be happily implemented using a linked list. 

Note: Insertion to a linked list is a different (slower) operation than basic addition/append. Insertion often requires traversal along the list until the correct position is found, O(n) where n is the list length. An append is simply adding to the tail of the list (hence O(1))

The title is mostly self-explanatory: what are the advantages of linked lists over binary trees? The only case I can think of in which a linked list is more efficient is for iterating over every element, in which case it's still pretty close. It looks like binary trees are faster at both accessing data and inserting new elements. So why use a linked list at all?

Advantages of linked lists over binary trees?

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

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

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

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

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

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

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

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

EdgeOne AI 安全实战专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

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

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

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

标题大多不言自明:链表相对于二叉树的优势是什么？我能想到的唯一更有效的情况是遍历每个元素，在这种情况下它仍然非常接近。看起来二叉树在访问数据和插入新元素方面都更快。那么为什么要使用链表呢？

问链表相对于二叉树的优势是什么？
EN

回答 7

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问链表相对于二叉树的优势是什么？EN

回答 7

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问链表相对于二叉树的优势是什么？
EN