【数据结构】单链表

线性表顺序存储结构的优缺点

顺序表优点

无须为了表示中间的元素之间的逻辑关系而增加额外的存储空间；
因为以数组形式存储，可以快速地存取表中任一位置的元素。

顺序表缺点

插入和删除操作需要移动大量元素，时间复杂度为O(N)；
当线性表长度变化较大时，难以确定存储空间的容量；
造成存储空间的“碎片”。

顺序存储结构不足的解决办法

其实顺序表最大的缺点就是插入和删除时需要移动大量元素，这显然就需要耗费极大时间，因为相邻两元素的存储位置也具有邻居关系。它们编号是1,2,3,...,n，它们在内存中的位置也是挨着的，中间没有空隙，当然就无法快速介入，而删除后，当中就会留出空隙，自然需要弥补。

那这样的话，我们反正都要让相邻的元素都留有足够余地，那么干脆所有的元素都不考虑相邻位置了，哪里有空位就到哪里，而只是让每个元素知道他下一个元素的位置在哪里，这样我们就可以在第一个元素时，就知道第二个元素的位置（内存地址），而找到它；在第二个元素时，就知道第三个元素的位置（内存地址），而找到它。这样所有的元素我们就都可以通过遍历而找到了。

其实这个思路也就是链表存储思路，而本篇文章着重讲述链表中的单链表。

线性表链式存储结构定义

在链式结构中，除了要存储数据元素信息外，还要存储它的后继元素的存储地址。

数据域：存储数据元素信息的域称为数据域；

指针域：存储直接后继位置的域称为指针域。

在指针域中存储的信息称为指针或链。数据域与指针域信息组成数据元素的存储映像，称为结点。

单链表：n个结点链结成的链表，此链表中的每个结点中只包含一个指针域。

单链表的代码实现以及分析

单链表的结构代码

单链表中的结点，是由存放数据元素的数据域和存放后继结点地址的指针域组成的。所以，假设这个数据为val，存放后继结点地址的指针为next。

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

单链表中的每一个节点都是一个结构体成员，也就是多个结构体构成了一条链表。这与顺序表不同，顺序表由于数组存储，所以就是一个结构体的数组中存储了多个节点。

单链表的遍历打印

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

单链表建立新的头结点

在创建新的头结点时，需要用到malloc函数，关于malloc的使用方法，这里不做过多阐述，大家有什么不懂的，可以点击链接（单击即可查看）详细学习malloc的使用方法哦。

C库函数中 void *malloc(size_t size) 分配所需的内存空间，并返回一个指向它的指针。

malloc是分配内存空间的函数。

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

单链表的尾插

那如果这是一个空表的话，那么就直接让这个单链表为指针，指向新创建的节点。

void SLTPushBack(SLNode** pphead, SLNDataType x)
{assert(pphead);SLNode* Newnode = SLTCreateNode(x);if (*pphead == NULL){*pphead = Newnode;}else{SLNode* tail = pphead;while (tail->next != NULL){tail = tail->next;}tail->next = Newnode;}
}

单链表的头插

void SLTPushFront(SLNode** pphead, SLNDataType x)
{assert(pphead);SLNode* Newnode = SLTCreateNode(x);Newnode->next = *pphead;*pphead = Newnode;
}

单链表的尾删

void SLTPopBack(SLNode** pphead)
{assert(pphead);assert(*pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLNode* tail = *pphead;while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;}
}

单链表的头删

void SLTPopFront(SLNode** pphead)
{assert(pphead);assert(*pphead);SLNode* cur = (*pphead)->next;//注意在单链表头删的时候，如果只有一个节点，那也是可以的，就让那个临时的为空free(*pphead);*pphead = cur;
}

单链表的查找x数据

SLNode* SLTFind(SLNode* phead, SLNDataType x)
{SLNode* cur = phead;while (cur){if (cur->val == x){return cur;}else{cur = cur->next;}}return NULL;
}

单链表在pos位置插入x的数

SLNode* SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{assert(*pphead);assert(pphead);assert(pos);if (*pphead==pos){SLTPushFront(pphead,x);}else{SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLNode* Newnode = SLTCreateNode(x);prev->next = Newnode;Newnode->next = pos;}
}

单链表删除pos位置上的值

void SLTErase(SLNode** pphead, SLNode* pos)
{assert(*pphead);assert(pphead);assert(pos);if (pos == *pphead){SLTPopFront(pphead);}else{SLNode* prev = *pphead;while (prev->next!=pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}

单链表的销毁

void SLTDestroy(SLNode** pphead)
{assert(pphead);SLNode* cur = *pphead;while (cur){SLNode* tmp = cur->next;free(cur);cur = tmp;}*pphead = NULL;
}