【科创世界】学习Python数据结构

在学习数据结构的数组和链表过程中，你需要掌握一些基础且重要的知识点。

数组和链表都是一种线性结构，数组其将相同类型元素存储在连续的内存空间中。我们将元素在数组中的位置称为该元素的索引index。链表中每个元素都是一个节点对象，各个节点通过“引用”相连接。引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。链表的设计使得各个节点可以被分散存储在内存各处，它们的内存地址是无须连续的。

01

数组的查删改

今天我们分别从访问元素、插入元素、删除元素三个方面来看看数组和链表之间的差异。由于数组元素被存储在连续的内存空间中，这意味着计算数组元素的内存地址非常容易。给定数组某个元素的索引便可以直接访问到该元素。需要注意的一点数组首个元素的索引为0，这似乎有些反直觉，因为从1开始计数会更自然。但从地址计算公式的角度看，索引的含义本质上是内存地址的偏移量。首个元素的地址偏移量是，因此它的索引为0也是合理的。

所以在数组中访问元素是非常高效的。由于数组元素在内存中是“紧挨着的”，它们之间没有空间再存放任何数据。如果想要在数组中间插入一个元素，则需要将该元素之后的所有元素都向后移动一位，之后再把元素赋值给该索引。值得注意的是，由于数组的长度是固定的，因此插入一个元素必定会导致数组尾部元素的“丢失”。为了解决这个问题，在插入元素的同时我们需要对原数组进行扩容的操作。

若想要删除索引index处的元素，则需要把索引index之后的元素都向前移动一位。但是需要注意删除元素完成后，原先末尾的元素变得“无意义”了，我们可以不修改忽略，或者修改原数组的长度，将长度减1即可。

02

链表的查删改

链表的组成单位是节点 node对象。每个节点都包含两项数据：节点的“值”和指向下一节点的“引用”。链表的首个节点被称为“头节点”，最后一个节点被称为“尾节点”；尾节点指向的是“空”，它在 Java、C++ 和 Python 中分别被记为Null。建立链表分为两步，第一步是初始化各个节点对象，第二步是构建引用指向关系。初始化完成后，我们就可以从链表的头节点出发，通过引用指向 next 依次访问所有节点。

数组整体是一个变量，比如数组 arrs包含元素 arrs[0] 和 arrs[1] 等，而链表是由多个独立的节点对象组成的。我们通常将头节点当作链表的代称，比如以上代码中的链表可被记作链表 n0。在链表中插入节点非常容易。假设我们想在相邻的两个节点n0和n1之间插入一个新节点P，则只需要改变两个节点引用（指针）即可。在链表中删除节点也非常方便，只需改变一个节点的引用（指针）即可。

尽管在删除操作完成后节点P仍然指向n1但实际上遍历此链表已经无法访问到P，这意味着P已经不再属于该链表了。链表不像数组直接可以通过索引查找到元素。链表需要从头节点出发，逐个向后遍历，直至找到目标节点。

03

优缺点对比

数组的优点：随机访问元素非常快。在内存中连续存储，易于分配和管理。可以直接通过下标操作数组元素，使用方便。数组的缺点：插入和删除元素时需要移动大量元素。数组的大小固定，需要预先分配足够的内存空间，不够灵活。 

链表的优点：插入和删除元素时只需要调整指针。链表的大小不固定，可以动态地增加或减少元素。链表的缺点：随机访问元素的时候需要从头开始遍历。在内存中不连续存储，需要更多的内存空间和管理成本。不支持直接通过下标操作元素。

编辑｜张毅

审核｜吴新