初始链表

链表(linked list)

本文目标：了解链表结构，并回顾之前iOS内存管理中的自动释放池

自动释放池poolpage用的栈的数据结构实现对象操作的，但是poolPage是双向链表的形式连接。
引入了栈的数据结构，论思维导图的重要性，知识点都是相互连接的。

链表是在非连续的内存单元中保存数据，通过指针将内存单元连接在一起。基本结构有指针域和值域两部分

入门释放池熟悉链表

回顾之前的源码

//第一步有push压栈操作
void *objc_autoreleasePoolPush(void) {
    return AutoreleasePoolPage::push();
}

void objc_autoreleasePoolPop(void *ctxt) {
    AutoreleasePoolPage::pop(ctxt);
}

//重点来了
class AutoreleasePoolPage {
    magic_t const magic;
    id *next;
    pthread_t const thread;
    AutoreleasePoolPage * const parent;
    AutoreleasePoolPage *child;
    uint32_t const depth;
    uint32_t hiwat;
};

每一个自动释放池都是由一系列的 AutoreleasePoolPage 组成的，并且每一个 AutoreleasePoolPage 的大小都是 4096 字节（16 进制 0x1000）

双向链表的实现（之外还有单向链表，循环链表）
释放池的AutoReleasePoolPage之间的连接是双向链表的形式。其中parent child构造前后指针。

当Pool:push()也就是压栈操作时，会涉及到一个点hotpage。查看当前页是否满，满了就parent创建新的poolpage。要查到或创建的 新的poolpage作为hotpage,去添加对象。不存在hotpage的情况当然创建新的poolpage.

这句话就涉及到计算机语言(oc/swift/c++)的流程控制if、else

通知通信

除此之外，通知中心NSNotification的数据结构的里面实现也用的了这个结构，NSNotificationCenter维护的链表一对象key保存，多个观察者的情况。
这个具体的底层实现，还有待研究。

链表的优势和数组对比

1. 插入删除方便。不需要移动元素

不同：

1. 链式存储，数组的顺序存储
2. 链表通过指针连接元素，数组通过元素的依次存储（内存存储中的连续...）
3. 链表的查询元素比较困难，指针查找了解下，方便扩容，数组插入删除麻烦，但是查找快啊

两者都能实现数据顺序存储，构造的模型是线性的（一条线），逻辑关系

多刷LeetCode的链表题
扩充几个知识点（双指针，快慢指针、链表反转）都是可以去了解的几个点