几种链表及它们的优缺点

halo大家好~今天我们来学习静态链表、循环链表和双向链表。

一、静态链表

1、什么是静态链表？

静态链表其实是为了给没有指针的高级语言设计的一种能实现单链表能力的方法。

用数组描述的链表叫静态链表，首先我们让数组的元素都由两个数据域组成，data和cur。也就是说，数组的每个下标都对应一个data和一个cur。

数据域data用来存放数据元素，而游标cur相当于单链表中的next指针，存放该元素的后继在数组中的下标。

在这里我们不对静态链表做详细介绍。

2、静态链表的优缺点

二、循环链表

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

循环链表与单链表的区别主要在于循环条件的判断上，原来是判断p->next是否为空，现在则是判断p->next是否等于头结点，如果不等于，则循环没有结束。

在单链表中，我们有了头结点，用O(1)时间访问第一个结点，但到访问到最后一个结点，要遍历单链表，需要用O（n）时间。那有没有方法可以用O（1）时间由链表指针访问到最后一个结点呢？答案是可以的。

不过我们需要改造这个链表，用指向终端结点的尾指针来表示循环链表。终端结点用尾指针rear表示。如下图所示

用尾指针表示循环链表

有了尾指针，我们将两个循环链表合成一个表就十分方便嘞。

三、双向链表

双向链表是在单向链表的每个结点中再设置一个指向其前驱结点的指针域。即它有两个指针域，一个指向前驱，一个指向后继。

双向链表的循环带头结点的空链表

非空的循环的带头结点的双向链表

插入操作：

总结：

通常我们用数组实现顺序存储结构，数组一开始就开辟一段固定的内存空间，因此我们需要对数据的长度有一定的估算，并且数组的插入与删除操作不方便。

而链式存储结构--链表不受固定的存储空间限制，可以快速进行插入和删除操作。

但是它们同样优秀哦~

我们对线性表的学习到此结束啦~线性表对我们学习其他数据结构至关重要~大家好好消化这几个概念吧~结合图像建立起自己的空间结构~