链表详解(一)

顺序表的问题及思考

中间/头部的插入删除，时间复杂度为O(N),效率低,但是尾部插入效率可以

增容需要申请新空间，拷贝数据，释放旧空间,且增容一般是呈2倍的增长，会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

链表

链表的概念及结构

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

由于链表不像顺序表一样要求连续，所以我们需要一种方式来管理这些数据(因为空间不一定是连续,如果不管理的话可能就找不到数据)

这种方式就是我们需要找到最开始的一块空间,然后那块空间会告诉你下一块空间的地址在哪,只有这样你才能够找到链表中的所有数据

而满足这种方式只有是通过结构体实现，结构中包含了我们想要的数据，以及下一块空间的地址

当我们所有的数据都查找完后，我们需要有人提醒我们已经找到尽头了，所以在查找完最后一块空间时，那块空间记录的下一块空间地址为空指针，也就是告诉你不需要再往后查找

链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
单向或者双向
带头或者不带头
循环或者非循环

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了

单链表的实现

typedef int SLNDataType;
typedef struct SListNode
{SLNDataType val;struct SListNode *next;
}SLNode;

这段代码是一个结构体里装这一个数据val和一个结构体指针next(next就是为了告诉你下一块空间的地址而存在的)

很多人可能有疑惑，认为结构体还没有实现完，为什么里面就可以包含一个结构体的指针

其实结构体的指针也是指针，结构体只要定义了，知道结构体的名称就可以实现内部包含一个结构体指针

如果我们把struct SListNode* next的*去掉，就会报错

此外这里有一个问题,如何计算上面链表中一个节点所占用内存的空间,这就涉及到结构占用内存的计算,在我之前的文章中有讲过

链表功能实现

遍历链表void SLTprint(SLNode* phead)

phead为第一块空间的地址，cur是为了避免在使用链表时phead会被使用者改变,导致我们找不到第一块空间地址的指针

代码

void SLTprint(SLNode* phead)
{SLNode* cur = phead;while (cur != NULL){printf("%d-> ", cur->val);cur = cur->next;}printf("NULL\n");
}

cur=cur->next是让cur去遍历链表,也就是cur指向cur的下一块节点的地址

当cur指向空时就意味着cur已经遍历完整个链表,所以直接跳出循环

创造新节点SLNode* CreateNode(SLNDataType x)

因为对于链表创建节点是非常常见的一种操作,所以我们单独拿出来写成一个函数

代码

SLNode* CreateNode(SLNDataType x)
{SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->val = x;newnode->next = NULL;return newnode;
}