iOS算法之链表

链表是一种数据结构，和数组同级。比如，Java中我们使用的ArrayList，其实现原理是数组。而LinkedList的实现原理就是链表了。链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

链表在进行循环遍历时效率不高，但是插入和删除时优势明显。与之相对应的概念是线性表和顺序表，线性表是n个数据元素的有限序列，数据之间存在顺序关系，一般同一个线性表属于同一类数据对象（例如A~Z的字母表）。线性表存在唯一一个首位元素和末位元素，除了第一个元素和最后一个元素，每个元素存在着一个前驱和一个后继（A的后继是B，B的前驱是A）。线性表主要有顺序表和链表两种存储形式，线性表是一种逻辑结构，顺序表和链表是物理存储结构。

线性表是逻辑概念，只要所有的数据在逻辑上是一维的都可以认为是线性表。线性表包括顺序表（栈，队列等），链表（栈，队列等）。跟线性表相对的概念应该是树或者堆。顺序表是空间概念，指的是所有的数据在存储空间上顺序排列，而跟具体的操作方式无关。顺序表是线性表的顺序表示，用一组地址连续的存储单元依次存储线性表的数据元素，数组即是最简单的顺序表。与顺序表相对的概念只有链表。

相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度是O(1)。

详细代码请参考Algorithm。参考代码比文字好理解。

使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。

总结来说，相比较普通的线性结构，链表结构的优势是单个节点创建非常方便，普通的线性内存通常在创建的时候就需要设定数据的大小；节点的删除非常方便，不需要像线性结构那样移动剩下的数据；节点的访问方便，可以通过循环或者递归的方法访问到任意数据，但是平均的访问效率低于顺序表。

单向链表(Singly linked lis)

单向链表是最简单的链表形式。我们将链表中最基本的数据称为节点(node)，每一个节点包含了数据块和指向下一个节点的指针。

单向链表

单向链表有时候也分为有头结点和无头结点。有头结点的链表实现比较方便(每次插入新元素的时候，不需要每次判断第一个节点是否为空)，并且可以直接在头结点的数据块部分存储链表的长度，而不用每次都遍历整个链表。

在单向链表中插入一个新的元素有两种方式：后插和前插。后插就是每次在链表的末尾插入新元素，前插就是在链表的头插入新元素。后插法比较符合平常的思维方式，并且保证插入数据的先后顺序。但是由于只保存了头结点，所以每次插入新元素必须重新遍历到链表末尾。为了解决这个问题，考虑增加一个尾指针，指向链表的最后一个节点。由于单向链表只存储了头指针，所以删除单向链表中的元素时，需要找到目标节点的前驱节点。链表里面的内存是手动分配的，当不再使用这些内存时需要手动删除。

双向链表(Doubly linked list)

双向链表就是有两个方向的链表。同单向链表不同，在双向链表中每一个节点不仅存储指向下一个节点的指针，而且存储指向前一个节点的指针。通过这种方式，能够通过在O(1)时间内通过目的节点直接找到前驱节点，但是同时会增加大量的指针存储空间。

双向链表

在双向链表中插入新元素的操作跟在单向链表中插入新元素的操作类似。由于双向链表中每个节点记录了它的前驱结点，所以不需要像单向链表中一样索引目标节点的前驱节点，而是可以通过目标节点直接获得。在双向链表中，第一个节点的前驱节点不是头结点，而是指向一个空指针。同样的，最后一个节点的后驱指向了一个空指针。

循环链表(Circular Linked list)

循环链表与双向链表相似，不同的地方在于：在链表的尾部增加一个指向头结点的指针，头结点也增加一个指向尾节点的指针，以及第一个节点指向头节点的指针，从而更方便索引链表元素。

循环链表

线索二叉树

存储结构

二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构，使每个结点都有了唯一前驱和后继（第一个结点无前驱，最后一个结点无后继）。对于二叉树的一个结点，查找其左右子女是方便的，其前驱后继只有在遍历中得到。为了容易找到前驱和后继，有两种方法。一是在结点结构中增加向前和向后的指针fwd和bkd，这种方法增加了存储开销，不可取；二是利用二叉树的空链指针。

线索二叉树是对二叉链表中空指针的充分利用，线索二叉树是一种物理结构。以这种结点结构构成的二叉线索链表，链表作为二叉树的存储结构，其中指向结点前驱和后继的指针叫做线索，加上线索的二叉树称为线索二叉树。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）。使得原本是空指针的转化成在某种遍历的顺序下，指向该结点的前驱和后继。

在二叉链表中，每个结点都带有leftChild和rightChild两个指针，线索二叉树在二叉链表的基础上增加了两个成员数据：leftTag、rightTag，用来标记当前结点的leftChild，rightChild指针指向的是孩子，还是线索。leftTag=rightTag=1,表示线索，leftTag=rightTag=0;表示孩子。

对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。若对二叉树进行中序遍历，则所得的线索二叉树称为中序线索二叉树，线索链表称为中序线索链表。

线索二叉树

建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前的左，右指针域是否为空，将它们改为指向前驱结点或后续结点的线索。在对一颗二叉树加线索时，必须首先申请一个头结点，建立头结点与二叉树的根结点的指向关系，对二叉树线索化后，还需建立最后一个结点与头结点之间的线索。

在中序线索树找结点后继的规律是：若其右标志为1，则右链为线索，指示其后继，否则遍历其右子树时访问的第一个结点（右子树最左下的结点）为其后继；找结点前驱的规律是：若其左标志为1，则左链为线索，指示其前驱，否则遍历左子树时最后访问的一个结点（左子树中最右下的结点）为其前驱。

在后序线索树中找到结点的后继分三种情况：
若结点是二叉树的根，则其后继为空；若结点是其双亲的右孩子，或是其双亲的左孩子且其双亲没有右子树，则其后继即为双亲结点；若结点是其双亲的左孩子，且其双亲有右子树，则其后继为双亲右子树上按后序遍历列出的第一个结点。

详细代码请参考Algorithm。参考代码比文字好理解。