《Hello算法》增删改查——数组与链表

aramy

《Hello算法》增删改查——数组与链表 [复制链接]

 

对数据的基础处理方法有增、删、改、查。四种基本操作。链表和数组都能支持这些基本操作。

1、查与改

数组是一种线性数据结构，数组元素被存储在连续的内存空间中，那么对于数组而言，可以直接定位到数组中的任意一个元素，所以复杂度为O(1)。定位到具体元素后即可做修改操作。

链表也是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过“引用”相连接。引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。与数组不同，链表无法直接定位到任意一个元素，只能从头节点出发，逐个节点地遍历，直至找到目标节点。复杂度为O(n)。同样定位到具体元素，即可做修改操作。

2、增与删

数组应为元素是被存储在连续的内存空间里，并且内存空间在初始化时就被指定了。所以增加和删除元素变得很麻烦。增加元素时，需要重新申请一整块内存空间，新内存空间尺寸为当前内存空间加一；然后将当前内存空间中的元素与增加的元素，逐一地搬运到新的内存空间中去（这里存在申请新内存失败的风险）。删除元素时可以不用新申请内存空间，但是指定位置元素删除后，其后方所有的元素，都需要向前移动位置，形成新的数组。数组的增与删，内存操作都非常频繁，复杂度为O(n)。

 

 

 

链表在增与删上则方便很多，新增元素时：第一步将新增元素的下一节点指针指向需要插入位置的下一节点地址；第二步将需要插入位置的节点的下一元素指针，指向新增元素即可。

删除元素：第一步将指向待删除元素的指针，修该为待删除元素指向的下一节点地址；第二步释放待删除元素。链表的增和删，复杂度O(1)。

 

 

 

最后 关于数组与链表的总结，书上总结的非常到位：

数组和链表是两种基本的数据结构，分别代表数据在计算机内存中的两种存储方式：连续空间存储和分散空间存储。两者的特点呈现出互补的特性。
数组支持随机访问、占用内存较少；但插入和删除元素效率低，且初始化后长度不可变。
链表通过更改引用（指针）实现高效的节点插入与删除，且可以灵活调整长度；但节点访问效率低、占用内存较多。常见的链表类型包括单向链表、环形链表、双向链表。
列表是一种支持增删查改的元素有序集合，通常基于动态数组实现。它保留了数组的优势，同时可以灵活调整长度。
列表的出现大幅提高了数组的实用性，但可能导致部分内存空间浪费。
程序运行时，数据主要存储在内存中。数组可提供更高的内存空间效率，而链表则在内存使用上更加灵活。
缓存通过缓存行、预取机制以及空间局部性和时间局部性等数据加载机制，为 CPU 提供快速数据访问，显著提升程序的执行效率。
由于数组具有更高的缓存命中率，因此它通常比链表更高效。在选择数据结构时，应根据具体需求和场景做出恰当选择。

 

 

 

查看本帖全部内容，请登录或者注册

Jacktang

对增、删、改、查这四种基本操作总结的到位