链表(Linked List) 线性结构

链表与数组看起来非常像，但是内存分配方式、内部结构和插入删除操作方式都不一样。链表是一系列节点组成的链，每一个节点保存了数据以及指向下一个节点的指针。链表头指针指向第一个节点，如果链表为空，则头指针为空或者为 null。链表可以用来实现文件系统、哈希表和邻接表。

在 Java 中创建链表的过程和创建数组的过程不同，不会先划出一块连续的内存。因为链表中的数据并不是连续的，链表在存储数据的内存中有两块区域，一块区域用来存储数据，一块区域用来记录下一个数据保存在哪里(指向下一个数据的指针)。当有数据进入链表时候，会根据指针找到下一个存储数据的位置，然后把数据保存起来，然后再指向下一个存储数据的位置。这样链表就把一些碎片空间利用起来了，虽然链表是线性表，但是并不会按线性的顺序存储数据。

由于链表是以这种方式保存数据，所以链表在插入和删除时比较容易，读取数据时比较麻烦。举个例子：一个链表中0->1->2->3->4这五个内存地址中都存了数据，现在需要往2中插入一条数据，那么只需要更改1号和2号中记录下一个数据的位置就行了，对其他数据没有影响。删除一条数据与插入类似，很高效。但是如果是想要在链表其中取出一条数据，就需要从0号开始一个一个的找，直到找到想要的那条数据为止。