前面我们学习了顺序表,但顺序表其实存在一些问题
1. 中间/头部的插入删除,时间复杂度为O(N)
2. 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗(尤其是异地扩容)。3. 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到 200,我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间。
优点:
1.尾插尾删足够快
2.下标的随机访问和修改
如何改善顺序表的这些问题呢?那么看看远处的链表吧
3.1 链表的概念及结构
概念:链表是一种 物理存储结构上非连续 、非顺序的存储结构,数据元素的 逻辑顺序 是通过链表中的 指针链接 次序实现的 。
链表在内存中是什么样的呢?
以往在数组中内存空间是连续的,通过一个指针和 size 就能够找到并管理所有值;
在链表中的空间是多段不连续的,空间之间也没有大小关系,链表也定义一个头指针指向第一个空间,第一个空间中存放一个指针指向第二个空间,每个空间都有一个指针指向下一个空间,而最后一个空间的指针指向NULL(空)。
形如:
物理形态:(箭头是臆想的)
节点的空间是从堆上随机申请的,两次申请的空间可能连续,可能不连续。
3.2 链表的初步实现
初级单向链表举例:
//single link table
typedef int SLTDateType;
typedef struct SListNode //(链表节点)
{//数据SLTDateType data;//结构体类型的指针,能够找到下一个结构(节点)SLTDateType* next;
}SLTNode;//将结构体简写,等同于下一行
//typedef struct SListNode SLTNode;//打印链表
void PrintSList(SLTNode* phead)
{//拷贝头指针SLTNode* cur = phead;while (cur!=NULL){printf("%d ", cur->data);//指针指向节点中的下一个节点的地址cur = cur->next;}printf("NULL\n");
}
int main()
{//插入节点SLTNode* p1 = (SLTNode*)malloc(sizeof(SLTNode));p1->data = 10;SLTNode* p2 = (SLTNode*)malloc(sizeof(SLTNode));p2->data = 20;SLTNode* p3 = (SLTNode*)malloc(sizeof(SLTNode));p3->data =30;//让上一个节点指向下一个节点p1->next = p2;p2->next = p3;p3->next = NULL;PrintSList(p1);return 0;
}