转载自https://github.com/Snailclimb/JavaGuide(添加小部分笔记)感谢作者!
数组#
- 数组(Array)是一种常见数据结构,由相同类型的元素(element)组成,并且是使用一块连续的内存来存储
- 直接可以利用元素的**索引(index)**可以计算出该元素对应的存储地址
- 数组的特点是:提供随机访问并且容量有限
假设数组长度为n:
访问:O(1) //访问特定位置的元素插入:O(n) //最坏的情况插入在数组的首部并需要移动所有元素时
删除:O(n) //最坏的情况发生在删除数组的开头并需要移动第一元素后面所有的元素时

链表#
链表简介#
链表(LinkedList)虽然是一种线性表,但是并不会按线性的顺序存储数据,使用的不是连续的内存空间来存储数据
链表的插入和删除操作的复杂度为O(1),只需要直到目标位置元素的上一个元素即可。但是,在查找一个节点或者访问特定位置的节点的时候复杂度为O(n)
使用链表结构可以克服数组需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理
但链表不会节省空间,相比于数组会占用更多空间,因为链表中每个节点存放的还有指向其他节点的指针。除此之外,链表不具有数组随机读取的优点
链表分类#
单链表、双向链表、循环链表、双向循环链表
假设链表中有n个元素
访问:O(n) //访问特地给位置的元素插入删除:O(1) //必须要知道插入元素的位置
单链表#
- 单链表只有一个方向,结点只有一个后继指针next指向后面的节点。因此,链表这种数据结构通常在物理内存上是不连续的
- 我们习惯性地把第一个结点叫做头结点,链表通常有一个不保存任何值的head节点(头结点),通过头结点我们可以遍历整个链表,尾结点通常指向null
- 如下图

循环链表#
- 循环链表是一种特殊的单链表,和单链表不同的是循环链表的尾结点不是指向null,而是指向链表的头结点
- 如图

双向链表#
- 双向链表包含两个指针,一个prev指向前一个节点,另一个next指向
- 如图

双向循环链表#
双向循环链表的最后一个节点的next指向head,而head的prev指向最后一个节点,构成一个环

应用场景#
- 如果需要支持随机访问的话,链表无法做到
- 如果需要存储的数据元素个数不确定,并且需要经常添加和删除数据的话,使用链表比较合适
- 如果需要存储的数据元素的个数确定,并且不需要经常添加和删除数据的话,使用数组比较合适
数组 vs 链表#
- 数组支持随机访问,链表不支持
- 数组使用的是连续内存空间 对CPU缓存机制友好,链表则相反
- 数组的大小固定,而链表则天然支持动态扩容。如果生命的数组过小,需要另外申请一个更大的内存空间存放数组元素,然后将原数组拷贝进去,这个操作比较耗时
栈#
栈简介#
- 栈(stack)只允许在有序的线性数据集合的一端(称为栈顶top)进行加入数据(push)和移除数据(pop)。因而按照**后进先出(LIFO,Last In First Out)**的原理运作。
- 栈中,push和pop的操作都发生在栈顶
- 栈常用一维数组或链表来实现,用数组实现的叫顺序栈,用链表实现的叫做链式栈
假设堆栈中有n个元素。 访问:O(n)//最坏情况 插入删除:O(1)//顶端插入和删除元素









如上,Eden区内存几乎被分配完全(即使程序什么都不做,新生代也会使用2000多K)
在给allocation2分配内存之前,Eden区内存几乎已经被分配完。所以当Eden区没有足够空间进行分配时,虚拟机将发起一次MinorGC。GC期间虚拟机又发现allocation1无法存入空间,所以只好通过分配担保机制,把新生代的对象,提前转移到老年代去,老年代的空间足够存放allocation1,所以不会出现Full GC(这里可能是之前的说法,可能只是要表达老年代的GC,而不是Full GC(整堆GC) ) 



1.8之后整个永久代改名叫"元空间",且移到了本地内存中

