数据结构与算法 链表

链表：零散的内存空间

数组：连续的内存空间

链表类型：单链表、双向链表、循环链表

链表和数组的比较：

数组：

    查询：按索引访问元素，时间复杂度为O(1)

    插入/删除：可能会涉及大量数据移动，时间复杂度为O(n)

链表：

    查询：需要从头依次遍历，时间复杂度为O(n)

    插入/删除：改变节点指针即可，时间复杂度为O(1)

单链表、双向链表的比较：

    共同点

随机访问数据的时间复杂度为O(n)。

在给定结点之后或列表开头添加一个新结点的时间复杂度为O(1)。

删除第一个结点的时间复杂度为O(1)。

    差异点

在单链表中，无法获取给定结点的前一个结点，需要先查找前一结点，时间复杂度为O(n)，然后删除。

在双链表中，直接使用“prev”引用字段获取前一个结点。删除给定结点时间复杂度为O(1)。

对比总结

如果高频添加或删除结点，选择链表。

如果高频按索引访问元素，选择数组。