据结构与算法

在上一章节中我们讲解了数据结构中的顺序表知道了顺序表的空间是连续存储的这与数组非常类似为我们随机访问数据提供了便利的条件。

但是同时当插入数据时可能存在移动数据与扩容的情况这大大增加我们的时间与空间成本。

为了解决这个问题就要学习我们今天要讲解的链表。

链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的

2.1

本专栏将选择其中两种常见链表进行讲解那就是无头单向非循环链表与与带头双向循环链表这两种优点主要有

无头单向非循环链表结构简单一般不会单独用来存数据。

实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。

另外这种结构在笔试面试中出现很多。

带头双向循环链表结构最复杂一般用在单独存储数据。

实际中使用的链表数据结构都是带头双向循环链表。

另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势实现反而简单了后面我们代码实现了就知道了。

打印单链表中的数据。

对单链表进行头插(开头插入数据)。

对单链表进行头删(开头删除数据)。

对单链表进行尾插(末尾插入数据)。

对单链表进行尾删(末尾删除数据)。

对单链表进行查找数据。

对单链表数据进行修改。

任意位置的删除和插入数据。

销毁单链表。

单链表的结点定义方式与我们以往定义的方式都不同它是一个结构体中包含两个成员。

一个是存储数值一个存放下一个结点的地址。

typedef

打印链表需要对函数传参指向链表的指针首先为了保证链表不为空(NULL)需要对其进行断言。

(1)

时间复杂度因为需要遍历整个链表显然时间复杂度为O(N)。

空间复杂度打印链表不需要格外的空间所以空间复杂度为O(1).

5.2

单链表每次插入都需要插入一个节点所以我们最好写一个创建节点的函数方便后续调用。

SListNode*

(SListNode*)malloc(sizeof(SListNode));if

(newnode

单链表的头插与顺序表头插最大的不同就是单链表传参需要二级指针。

因为头插数据需要改变一级指针plist的指向而形参的改变无法影响实参所以需要二级指针才能改变一级指针plist的指向。

void

时间复杂度不需要额外时间的消耗时间复杂度为O(1)。

空间复杂度固定创造一个节点空间复杂度为O(1)。

5.3

头删与头插类似都可能需要改变plist的指向所以也需要二级指针。

并且也需要防止链表为空的情况发生。

(1)

{assert(plist);assert(*plist);SListNode*

cur

(*plist)-next;free(*plist);*plist

cur;

时间复杂度不需要额外时间的消耗时间复杂度为O(1)。

空间复杂度不需要格外的空间消耗空间复杂度为O(1)。

5.4

当链表为空时单链表尾插就会变成单链表头插也需要改变plist的指向。

其余情况即可通过循环寻找尾节点。

(1)

SListCreatNode(x);}else{SListNode*

ptail

时间复杂度需要遍历整个链表时间复杂度为O(N)。

空间复杂度固定创造一个节点空间复杂度为O(1)。

5.5

与单链表尾插类似当链表只有一个头结点时需要将plist置为空所以也需要二级指针。

并且也需要防止链表为空的情况发生。

(1)

{assert(plist);assert(*plist);//防止链表为空if

((*plist)-next

ptail-next;}free(ptail-next);ptail-next

NULL;}

时间复杂度需要遍历整个链表时间复杂度为O(N)。

空间复杂度不需要格外的空间消耗空间复杂度为O(1)。

5.6

时间复杂度可能需要遍历整个链表时间复杂度为O(N)。

空间复杂度不需要格外的空间消耗空间复杂度为O(1)。

5.6

{assert(plist);assert(pos);SListNode*

cur

时间复杂度可能需要遍历整个链表时间复杂度为O(N)。

空间复杂度不需要格外的空间消耗空间复杂度为O(1)。

5.7

NULL||pos-nextNULL){SListPushBack(plist,

tmp

时间复杂度无论向前插入还是向后插入都可能需要遍历整个链表所以时间复杂度为O(N)。

空间复杂度固定创造一个节点空间复杂度为O(1)。

5.8

{assert(plist);assert(*plist);assert(pos);if

(*plist

pos){SListPopFront(plist);//头删}SListNode*

prev

时间复杂度可能需要遍历整个链表所以时间复杂度为O(N)。

空间复杂度固定创造一个节点空间复杂度为O(1)。

5.9

{assert(plist);assert(*plist);SListNode*

cur

时间复杂度需要遍历整个链表所以时间复杂度为O(N)。

空间复杂度不需要格外的空间消耗空间复杂度为O(1)。