链表是一种在物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。实际中链表的结构很多样化，本次实现的是无头单向非循环链表。
不足：链表以节点为单位存储，不支持随机访问。 优势：任意位置插入删除时间复杂度为O(1) ，没有增容问题，插入一个开辟一个空间。
代码如下： common.h
#include <stdio.h> #include <stdlib.h> #include <assert.h>SList.h（函数声明文件）
#include "common.h" #pragma once typedef int SLTDataType; //两个结构体，一个定义结点，一个定义指向链表 typedef struct SListNode { SLTDataType _data; struct SListNode* _next; }SListNode; typedef struct SList { SListNode* _head; }SList; void SListInit(SList* plist); void SListDestory(SList* plist); void SListPrint(SList* plist); //申请一个新结点 SListNode* BuySListNode(SLTDataType x); void SListPushBack(SList* plist, SLTDataType x); void SListPopBack(SList* plist); void SListPushFront(SList* plist, SLTDataType x); void SListPopFront(SList* plist); SListNode* SListFind(SList* plist, SLTDataType x); //在pos的后面插入节点 void SListInsertAfter(SListNode* pos, SLTDataType x); //删除pos后面的节点 void SListEraseAfter(SListNode* pos); void SListRemove(SList* plist, SLTDataType x); void SListTest1();SList.c（函数实现文件）
#include "SList.h" void SListInit(SList* plist) { assert(plist); plist->_head = NULL; } void SListDestory(SList* plist) { assert(plist); SListNode* cur = plist->_head; while (cur != NULL) { SListNode* next = cur->_next; free(cur); cur = next; } plist->_head = NULL; } void SListPrint(SList* plist) { assert(plist); SListNode* cur = plist->_head; while (cur != NULL) { printf("%d->", cur->_data); cur = cur->_next; } printf("NULL\n"); } SListNode* BuySListNode(SLTDataType x) { SListNode* pnode = (SListNode*)malloc(sizeof(SListNode)); pnode->_data = x; pnode->_next = NULL; return pnode; } void SListPushBack(SList* plist, SLTDataType x) { assert(plist); if (plist->_head == NULL) { plist->_head = BuySListNode(x); } else { SListNode* tail = plist->_head; while (tail->_next != NULL) { tail = tail->_next; } SListNode* newtail = BuySListNode(x); tail->_next = newtail; } } void SListPopBack(SList* plist) { assert(plist); //只有一个节点 if (plist->_head->_next == NULL) { free(plist->_head); plist->_head = NULL; } //有多个节点 else { SListNode* tail = plist->_head; SListNode* prev = NULL; while (tail->_next != NULL) { prev = tail; tail = tail->_next; } free(tail); prev->_next = NULL; } } void SListPushFront(SList* plist, SLTDataType x) { assert(plist); SListNode* newhead = BuySListNode(x); newhead->_next = plist->_head; plist->_head = newhead; } void SListPopFront(SList* plist) { assert(plist); SListNode* next = plist->_head->_next; free(plist->_head); plist->_head = next; } SListNode* SListFind(SList* plist, SLTDataType x) { assert(plist); SListNode* cur = plist->_head; while (cur != NULL) { if (cur->_data == x) { return cur; } cur = cur->_next; } return cur; } void SListInsertAfter(SListNode* pos, SLTDataType x) { assert(pos); SListNode* next = pos->_next; SListNode* newnode = BuySListNode(x); newnode->_next = next; pos->_next = newnode; } void SListEraseAfter(SListNode* pos) { assert(pos); pos->_next = pos->_next->_next; } void SListRemove(SList* plist, SLTDataType x) { assert(plist); } void SListTest1() { SList list; SListInit(&list); SListPushFront(&list, 1); SListPushFront(&list, 2); SListPushFront(&list, 3); SListPushBack(&list, 0); SListPrint(&list); SListPopFront(&list); SListPopBack(&list); SListPrint(&list); SListNode* pos = SListFind(&list, 2); SListInsertAfter(pos, 30); SListPrint(&list); SListDestory(&list); }Test.c（测试文件）
#include "Slist.h" int main() { SListTest1(); system("pause"); return 0; }