说到链式存储结构，数组是两种非常基本的数据结构，每次提到链式存储结构，通常都要与数组一起进行比较。
对于数组和链表，从结构上看，数组需要连续的内存空间来存储数据，对内存的要求非常高。 例如，即使申请100M大小的数组，即使有100M以上的内存可用空间，如果没有连续的100M可用空间，即使内存空间足够，申请空间时申请也会失败。
对于链表，他对内存空间的要求不是很高。 不需要连续的内存空间。 如果内存空间足够，则即使内存空间中存在碎片，只要碎片大小足以存储链表节点中的数据，也可能会分配该碎片空间。 链表连接使用通过指针或引用碎片化的一组空间。 因此，即使链表需要100M的空间，尽管内存空间足够，但连续的空间必须在100M以上，才不会影响链表的空间分配。
关于链存储结构，一般最多、最常用的有三种类型：单向链路、双向链路和循环链路。
链表是通过指针或引用链接分散的内存块的产物，连接到链表的每个内存块称为链表的节点。
单向链表位于链表结构中，每个节点只存储自身需要存储的数据和下一个节点地址，这种链表结构称为单向链表结构。 其形象如下。
如图所示，单链表中的每个节点除了数据区域外，还包含当前节点的下一个节点的地址。 记录下一个节点地址的指针或引用称为后续指针或引用Next。
在我们的单链接列表结构中，两个节点是特殊的：第一个节点和最后一个节点。 在链式存储结构中，第一个节点称为首节点，最后一个节点称为尾节点。 头节点记录链表的起始地址。 有了这个地址，就可以遍历整个链表。 对尾部节点的后续指针或引用指向空地址NULL，而不是特定节点。 这表示该节点是链表的末尾节点。
与数组一样，链表也支持数据的插入、搜索和删除。
但是，众所周知，数组在进行数据的插入、删除操作时，为了确保存储器数据的连续性需要进行大量的数据移动工作，因此时间复杂度为o(n )。 在链表中插入或删除数据时，链表结构中的节点不需要连续的存储空间，因此在链表中插入和删除数据时不需要移动节点。 关于链表的删除和插入操作，由于只需调整相邻节点的后续指针即可，对应的时间复杂度为o(1)。
与数组相比，链表在需要访问第k个元素时，不像数组那么简单。 数组的内存数据是连续的，因此如果需要访问第k个元素，则可以根据基地址(base_address )和数据类型大小随机访问数据所在的存储器地址。
array [ k ] _ address=base _ addressk * data _ type _ size； 但是，在链表的情况下，链表的各节点的数据分布在存储器内，不像数组那样是连续的存储空间，所以要访问链表的第k个要素，从最初的节点开始依次基于节点间的后续指针或参照
循环链表结束后，我们来看看循环链表。 循环链表是一种特殊的单链表，其特殊之处在于，在单链表中，尾部节点的后续指针或引用指向空地址NULL，而不是特定节点，表示它是最后一个节点。 另一方面，如果将单链表的尾部节点调整为从空地址的NULL到起始节点的Head，则形成循环链表。
与单连锁表相比，循环连锁表的优点是从连锁的末尾到连锁的开头比较方便。 如果要处理的数据具有环型结构的特点，则采用循环链表尤为合适。 例如，著名的约瑟夫问题也可以在单链表中实现，但在循环链表中实现的话代码会变得简洁。
双向链表中的单向链表是单向的，后续指针或引用Next指向后续节点。 双向链表是指支持两个方向的链表结构。 每个节点不仅后续指针或引用Next指向上一个节点，而且前体指针或引用Prev也指向上一个节点。
从图中可以看出，双向链表需要额外的空间来存储后续节点和前驱节点的地址。 因此，如果存储同样多的数据，双向链表比单向链表需要更多的存储空间。 两个指针或引用会占用存储空间，但可以支持双向遍历，从而提供了双向链表操作的灵活性。
从双向链表的结构来看，双向链表可以在o(1)的时间复杂度下找到前驱节点。 基于这一特性，在某些特殊场景中，双向链表比单向链表更高效进行节点删除和插入操作。
首先，让我们看一下删除指定指针或引用节点的操作。
要删除指定的指针或引用的节点，必须首先检查整个链表以找到指定的节点x。 找到节点x后，需要找到其前驱节点。 由于单向链表不支持他直接获取前驱节点，因此必须再次遍历整个链表才能执行删除操作。 这在双向链表的情况下很有利。 找到指定的节点x后，不需要再次遍历链表以查找前驱节点。 因为双向链表中的节点已经包含指向前驱节点的指针或引用。 因此，如果找到指定节点x并删除节点，则删除单向链表的操作需要o(n )的时间复杂度，而双向链表只需要o ) 1的时间复杂度。 如果要在链表的特定节点x之前插入节点，则双向链表比单向链表更好
大的优势。双向链表可以在O(1)的时间复杂度内完成，而单向链表需要O(n)的时间复杂度才能完成。具体原因和我们上述的删除类似。基于双向链表在特定情况下相对于单向链表的优势，所以在我们实际的开发过程中，尽管双向链表相对耗内存，但是还是比单向链表应用广泛。比如在Java语言中LinkedHashMap 的实现原理也用到了双向链表。
双向循环链表上面我们说了单向链表、循环链表、双向链表，我们将循环链表和双向链表整合在一起，就形成了双向循环链表。
通过前面内容的探讨，我们应该已经知道，数组和链表是两种截然不同的内存组织方式。正是因为内存存储的区别，它们插入、删除、随机访问操作的时间复杂度正好相反。
不过，数组和链表的对比，并不能局限于时间复杂度。而且，在实际的软件开发中，不能仅仅利用复杂度分析就决定使用哪个数据结构来存储数据，一切都要根据具体情况具体分析，合适最好，共勉之。