链表

链表

MessageQueue采用单链表的数据结构存储数据；对链表不了解小伙伴可以先看一下这篇文章有助于后面分析MessageQueue(简单介绍链表，不会做过多分析)。

链表

以单链表为例，链表由一系列链结点按照一定关系组成；链表包含一个指向第一个链结点的引用(first)；链结点由某个类的对象和下一个链结点的引用组成(next)。
需要注意链表的最后一个链结点next指向Null(可以作为链表尾端的标识)
Java代码

public class ChainNode {

    private double chainNodeData;
    private ChainNode next;

}
public class Chain {

    private ChainNode first;

}

链表的优缺点(相对于数组):
优点:
插入和删除方面效率较高；数组在内存中开辟一块连续的存储空间，每次插入和删除都需要对数组下标进行重新分配。而链表无需这样操作。
缺点:
1）不支持随机访问
2）链结点需要额外的引用地址

单链表

以下是我学习链表时思考的问题
1.为什么MessageQueue会被叫做单链表结构,是因为它持有了Message对象的引用吗?
MessageQueue相当于上面Chain类,Message对象充当了一个链结点的角色。

Message mMessages;//相当于Chain中first

2.Link中持有一个包含其自身相同类型的字段，怎样避免混淆?
持有的是对象的引用，而非对象本身。
3.为什么Link的搜索和插入效率高?
插入和删除不需要对链表进行重新分配.(链表没有数组下标这个概念，链表插入和删除只需要对next和first进行相关操作即可)
4.链表的插入是从头开始查询的吗?
无论是链表的插入还是删除都是从第一个链结点开始。
5.链结点如何插入到任意位置?
通过循环。

需要注意对新加入链结点的判空。

删除链接点后要记得断开链结点与下一个链接点之间的引用,避免脏数据的生成。

链表无论执行删除插入还是其他操作都会从表头开始遍历，找到对应元素。
后面提到的双端链表,有序链表和双向链表原理都跟单链表差不多,就不再累述了。

双端链表

方便查询链表最后一个链结点,除此之外跟单链表没有什么区别。

有序链表

数据按照关键值排序。（获取最大or最小值挺方便）

双向链表

允许前后遍历