数据结构学习笔记——线性表（下）

了解过线性表的链式存储结构以后，有人就想出来用数组来代替指针，来描述单链表。看看他们是怎么做到的。

静态链表

让数组的元素都由两个数据域组成，data和cur。也就是说，数组的每个下标都有对应的一个data和cur。数据域data，用来存放数据元素，而cur相当于单链表中的next指针，存放该元素的后继在数组中的下标，我们把cur叫做游标。

这种用数组描述的链表叫做静态链表，我们把这种描述叫做游标实现法。

另外我们对数组第一个和最后一个元素作为特殊元素处理，不存数据。我们通常把未使用的数组元素称为备用链表。

数组第一个元素，即下标为0的元素的cur存放备用链表的第一个节点的下标；而数组最后一个元素的cur存放第一个有数值的元素的下标，相当于单链表中的头节点的作用。

如下图：

我们对静态链表的插入和删除操作简单了解以下：

静态链表中要解决的是：如何用静态模拟动态链表的存储空间的分配，需要时申请，无用时释放。

静态链表的插入

静态链表的删除

静态链表的优缺点

• 在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点。
• 没有解决连续内存分配带来的表长度难以确定的问题。
• 失去了顺序存储结构随机存取的特点。

循环链表

对于单链表，由于每个结点只存储了向后的指针，到了尾标就停止了向后链的操作，这样，当某一个结点就无法找到它的前驱结点了。

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。

显然解决了一个问题：当从一个结点出发，访问链表的所有结点。

双向链表

双向链表：是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。

双向链表的好处：某个结点对前后结点的操作更快；

双向链表的不足：一个结点，两个指针，耗内存更大。

既然单链表可以由循环链表，那么双向链表当然也可以是循环表，其结构如下：

双向链表的插入

双向链表的删除

关于线性表就整理到这里了，文中有不对或不足的地方，希望大家能够反馈给我，一起进步。