关键词：
【中文标题】从内存分配的角度来看 ArrayList 与 LinkedList【英文标题】：ArrayList vs LinkedList from memory allocation perspective 【发布时间】：2012-07-18 20:16:43 【问题描述】：我需要存储大量信息，例如 java 列表中的“名称”。项目的数量可以改变（或者简而言之我无法预定义大小）。我认为，从内存分配的角度来看，LinkedList 将是比 ArrayList 更好的选择，因为对于 ArrayList，一旦达到最大大小，内存分配会自动加倍，因此总是有可能分配比 ArrayList 更多的内存需要什么。
我从这里的其他帖子中了解到，存储在 LinkedList 中的单个元素比 ArrayList 占用更多空间，因为 LinkedList 还需要存储节点信息，但我仍然猜测我定义的场景 LinkedList 可能是更好的选择。另外，我不想涉及性能方面（获取、删除等），因为已经讨论了很多。
【问题讨论】：
看来您已经有了答案。链接列表会更好，因为当达到最大值时它的大小不会翻倍。假设您有 251 个名称，然后当您达到 250 时，该数组加倍至 500。然后您在内存中分配了 249 个额外的点，而这一切都没有。基本上我想说的是从长远来看 Link-List > ArrayList 就内存而言。 @Eric Robinson：以下来自其他用户的cmets证明我的理解不正确。您可能也想注意这一点。谢谢.. 查看此答案以了解两者的内存占用情况：***.com/questions/322715/… 【参考方案1】：LinkedList 可能会分配更少的条目，但这些条目比 ArrayList 更昂贵——就内存而言，即使是最坏的情况 ArrayList 也更便宜。
（仅供参考，我认为你搞错了；ArrayList 满时会增长 1.5 倍，而不是 2 倍。）
参见例如https://github.com/DimitrisAndreou/memory-measurer/blob/master/ElementCostInDataStructures.txt : LinkedList 每个元素消耗 24 个字节，而 ArrayList 在最好的情况下每个元素消耗 4 个字节，在最坏的情况下每个元素消耗 6 个字节。 （结果可能因 32 位与 64 位 JVM 和压缩对象指针选项而异，但在这些比较中，LinkedList 至少需要 36 个字节/元素，ArrayList 最多为 8，最坏为 12。）
更新：
我从这里的其他帖子中了解到，存储在 LinkedList 中的单个元素比 ArrayList 占用更多空间，因为 LinkedList 还需要存储节点信息，但我仍然猜测我定义的场景 LinkedList 可能是更好的选择。另外，我不想涉及性能方面（获取、删除等），因为已经讨论了很多。
需要明确的是，即使在最坏的情况，ArrayList 也比具有相同元素的LinkedList 小 4 倍。使LinkedList 获胜的唯一可能方法是通过使用故意夸大的值调用ensureCapacity 来故意修复比较，或者在添加后从ArrayList 中删除大量值。
简而言之，让LinkedList 赢得内存比较基本上是不可能的，如果你关心空间，那么在ArrayList 上调用trimToSize() 将立即让ArrayList 再次以巨大的优势获胜。严重地。 ArrayList 获胜。
【讨论】：
FWIW，Joshua Bloch 公开表示，他认为编写 LinkedList 是一个错误，他应该坚持使用 ArrayList。 （不幸的是，我不记得我在哪里看到这个声明了）。 如果你有内存限制，还有一件事要考虑 - 当增长 ArrayList 时，你需要在复制时将原始数组和新数组放在内存中，在最坏的情况下消耗比需要多 2.5 倍案子。即便如此，ArrayList 还是胜过 LinkedList。【参考方案2】：...但我仍在猜测我定义的场景 LinkedList 可能是一个更好的选择
你的猜测不正确。
一旦您超过了数组列表的初始容量，支持的大小将在 1 到 2 个引用乘以条目数之间。这是由于用于增长后备阵列的策略。
对于链表，每个节点占用的条目数至少是条目数的 3 倍，因为每个节点都有一个 next 和 prev 引用以及条目引用。 （而且实际上是 3 倍以上，因为节点的对象头和填充使用的空间。根据 JVM 和指针大小，可能高达 6 倍。）
链表使用的空间比数组列表少的唯一情况是您严重高估了数组列表的初始容量。 （对于非常小的列表......）
细想一下，链表相对于数组列表的唯一真正优势是在插入和删除元素时。即便如此，这也取决于你如何做到这一点。
【讨论】：
【参考方案3】：ArrayList 对每个对象使用一个引用（或者当它的大小是所需大小的两倍时使用两个）这通常是 4 个字节。
LinkedList 只使用它需要的节点，但每个节点可以是 24 字节。
所以即使在最坏的情况下，ArrayList 也会比 LinkedList 小 3 倍。
对于获取 AArrayList 支持随机访问 O(1) 但 LinkedList 是 O(n)。从末尾删除都是O(1)，从ArrayList中间某处删除是O(n)
除非您有 数百万 个条目，否则集合的大小可能并不重要。首先重要的是条目的大小，无论使用何种集合，条目的大小都是相同的。
【讨论】：
【参考方案4】：信封最坏情况：
大小为 1,000,000 的数组中有 500,000 个名称 = 已使用 500,000 个，已分配数组的未使用部分中有 500,000 个空指针。
链表中的 500,000 个条目 = 每个条目 3 个指针（Node 对象保存 current、prev 和 next）= 内存中的 1,5000,000 个指针。 （然后你必须添加节点本身的大小）
【讨论】：
@Affe..yup..简而言之，即使在这种情况下（有点最坏的情况）ArrayList 消耗的内存也比 Linked List 少..【参考方案5】：ArrayList.trimToSize() 可能会让你满意。
将此 ArrayList 实例的容量调整为列表的当前容量 尺寸。应用程序可以使用此操作来最小化存储 一个 ArrayList 实例。
顺便说一下，在 ArrayList Java6 中，它不是双倍容量，它大约是达到最大大小的 1.5 倍。
【讨论】：
什么是更有效的堆栈内存或堆？ [复制]
】什么是更有效的堆栈内存或堆？[复制]【英文标题】：Whatismoreefficientstackmemoryorheap?[duplicate]【发布时间】：2011-06-2520:49:15【问题描述】：可能重复：C++Whichisfaster:StackallocationorHeapallocation从内存分配的角度来看，堆栈内存或堆内... 查看详情
从性能角度来看 MongoDB 嵌入式与参考
】从性能角度来看MongoDB嵌入式与参考【英文标题】：MongoDBembeddedvs.referencefromperformanceperspective【发布时间】：2011-09-1418:32:32【问题描述】：我读到从性能的角度来看嵌入更好：“如果性能是一个问题，嵌入。”(http://www.mongodb.org/... 查看详情
细节拉满，80张图带你一步一步推演slab内存池的设计与实现(代码片段)
从0到1带你一步一步推演slab内存池的设计与实现1.前文回顾在之前的几篇内存管理系列文章中，笔者带大家从宏观角度完整地梳理了一遍Linux内存分配的整个链路，本文的主题依然是内存分配，这一次我们会从微观的角度来探秘... 查看详情
Iphone：在哪里为数据源分配内存？
】Iphone：在哪里为数据源分配内存？【英文标题】：Iphone:WhereallocatememoryfordataSource?【发布时间】：2011-06-0705:43:30【问题描述】：我有一个用于填充UITableView的数组。问题是我应该在哪里为它分配内存。我在viewDidLoad或viewWillAppear... 查看详情
Netezza - 从 SQL 的角度来看，啥是托管？
】Netezza-从SQL的角度来看，啥是托管？【英文标题】：Netezza-WhatiscolocationintheperspectiveofSQL?Netezza-从SQL的角度来看，什么是托管？【发布时间】：2015-04-1022:33:51【问题描述】：我知道托管对于Netezza中的分布式连接很重要。在高层次... 查看详情
数组与数组列表的显着差异？ [复制]
...显着差异？[复制]【英文标题】：SignificantdifferencesinArrayvsArrayList?[duplicate]【发布时间】：2012-05-3114:54:26【问题描述】：可能重复：WhentouseArrayListoverarray[]inc#?从内存或处理器成本的角度来看，数组和arrayList对象之间是否存在显着... 查看详情
openssl之内存用法
参考技术A用户在使用内存时，容易犯的错误就是内存泄露。当用户调用内存分配和释放函数时，查找内存泄露比较麻烦。OpenSSL提供了内置的内存分配/释放函数。如果用户完全调用OpenSSL的内存分配和释放函数，可以方便的找到... 查看详情
c程序内存分配
...下进程。进程是占有资源的最小单位，这个资源当然包括内存。在现代操作系统中，每个进程所能访问的内存是互相独立的（一些交换区除外）。而进程中的线程所以共享进程所分配的内存空间。 在操作系统的角度... 查看详情
内存分配（malloc）的过程
参考技术A[TOC]malloc和mmap等内存分配函数只是建立进程的虚拟地址空间，并没有分配实际的物理内存。当进程访问没有建立映射关系的虚拟内存时会自动的触发一个缺页中断。请求分页的系统当中，可以查询页表当前的状态位来... 查看详情
LINQ 和内存分配
】LINQ和内存分配【英文标题】：LINQandmemoryallocation【发布时间】：2018-07-1212:51:16【问题描述】：在LINQ一词下的这个问题中，我的意思是LINQtoobjects。哪些LINQ方法分配新内存，哪些不分配？例如，Select(x=>x)是否分配新内存？如果... 查看详情
优化条件/if 块，从性能的角度来看，啥是可取的？
】优化条件/if块，从性能的角度来看，啥是可取的？【英文标题】：Optimizingconditionals/ifblocks,whatispreferablefromaperformancepointofview?优化条件/if块，从性能的角度来看，什么是可取的？【发布时间】：2015-12-1310:41:24【问题描述】：我... 查看详情
优化条件/if 块，从性能的角度来看，啥是可取的？
】优化条件/if块，从性能的角度来看，啥是可取的？【英文标题】：Optimizingconditionals/ifblocks,whatispreferablefromaperformancepointofview?优化条件/if块，从性能的角度来看，什么是可取的？【发布时间】：2015-12-1310:41:24【问题描述】：我... 查看详情
从编码人员的角度来看文件权限
】从编码人员的角度来看文件权限【英文标题】：Filepermissionsfromacodersperspective【发布时间】：2016-02-1000:04:23【问题描述】：文件权限是仅存储在HDD（或其他存储介质）上并受到操作系统尊重的东西。或者硬盘驱动器是否以某种... 查看详情
.NET 字符串与流 - 内存配置文件和特征
】.NET字符串与流-内存配置文件和特征【英文标题】：.NETStringsvs.Streams-MemoryProfileandCharacteristics【发布时间】：2010-09-2816:13:18【问题描述】：我需要从数据库(nvarchar)中提取大型Unicode文本字符串（例如200Mb）并存储在内存中以进行... 查看详情
c++内存分配方法new与placementnew使用方法详解
tags:C++写在前面总结一下C++内存分配中的new/delete方法,以及一个很有意思的工具:placementnew.参考:cppprimer5ed,pp409,pp726(19.1).侯捷C++videonew的基本使用编译器角度在使用new分配内存的时候,例如下... 查看详情
从任何角度来看 ++i 和 i+=1 有啥区别
】从任何角度来看++i和i+=1有啥区别【英文标题】：whatisdifferencebetween++iandi+=1fromanypointofview从任何角度来看++i和i+=1有什么区别【发布时间】：2013-08-2713:07:31【问题描述】：这是来自knking的c编程的一个问题：一种现代方法。看不懂... 查看详情
从配置管理的角度来看，在自动化构建中要做的最好的事情是啥？
】从配置管理的角度来看，在自动化构建中要做的最好的事情是啥？【英文标题】：Bestthings,fromaConfigurationManagementperspective,todoinanautomatedbuild?从配置管理的角度来看，在自动化构建中要做的最好的事情是什么？【发布时间】：2010... 查看详情
iOS 5 推送通知 - 从开发的角度来看
】iOS5推送通知-从开发的角度来看【英文标题】：iOS5PushNotification-FromDevelopingperspective【发布时间】：2011-11-0105:08:25【问题描述】：我在观看iOS5推送通知的视频时发现，除了徽章、警报和声音之外，通知用户存在一些差异。请通... 查看详情