欢迎使用6miu-markdown编辑器

单链表结构

每个节点依靠储存的下一个节点的内存地址，从而使得一个一个相连接在一起，而不需要考虑位置在哪

插入删除操作空间复杂度为O(1)读取某位置节点的空间复杂度O(n)不需要提前分配空间若线性表需要频繁的插入删除操作则应该选择链式结点个数未知的时候采用链式更好指针的应用

---

链表创建

创建带头结点的指针` 按照结构体开辟一块内存` 头结点指向NULL`其他的初始化置0`

ps：代码来自网络但没毛病，实现方法很多不是唯一·····

typedef struct _tag_LinkList { LinkListNode header; int Length; }TLinkList; LinkList *LinkList_Create() { TLinkList *tmp = NULL; tmp = (TLinkList *)malloc(sizeof(TLinkList)); if (tmp == NULL) { printf("func LinkList_Create()err \n"); return NULL; } memset(tmp, 0, sizeof(TLinkList)); tmp->Length = 0; tmp->header.next = NULL; return tmp; }

销毁

当链表执行完毕后要进行销毁····

直接free掉链表，不要忘记判断是否为空····

void LinkList_Destroy(LinkList *list) { if (list == NULL) { return; } free(list); return ; }

清空链表

链表的清空和销毁是不一样的，销毁的话释放了整个内存空间，狗带了就 然而清空的话，保留了内存空间，只是把里面东西弄没了，回到刚刚创建好头指针指向NULL的一个状态

就是相当于，俩人分手了销毁的是自杀，清空是回到单身狗状态

判断链表是否已经空了链表长度置为零清空头结点 void LinkList_Clear(LinkList *list) { TLinkList *tList = NULL; tList = (TLinkList *)list; if (tList == NULL) { return; } tList->Length = 0; tList->header.next = NULL; return ; }

获取链表长度

判断链表是否为空直接返回长度即可 int LinkList_Length(LinkList *list) { TLinkList *tList = NULL; tList = (TLinkList *)list; if (tList == NULL) { return -1; } return tList->Length; }

链表的插入

就 相当于一堆人手拉手好好的走，突然隔壁老王来了要站在张翠花和赵桂花中间，张翠花和赵桂花拉着的手就得松开，俩人都拉着老王

需要辅助指针用来从头部开始蹦跶走走走走到指向要插入的地方需要辅助指针变量接过来之前搞好的list需要知道插入位置错误判断：list为空，插入位置<0,要来插队的结点为空，三选一就没法玩儿了

链表长度再+1！！！

int LinkList_Insert(LinkList *list, LinkListNode *node, int pos) { int i = 0; LinkListNode *current = NULL; TLinkList *tList = NULL; tList = (TLinkList *)list; if (list == NULL || node == NULL || pos < 0) { return -1; } current = &(tList->header); for (i = 0; i < pos; i++) { current = current->next; } node->next = current->next; current->next = node; tList->Length++; return 0; }

获取某个位置上的结点

链表不为空位置不小于0辅助指针变量从头节点处跳到位置处函数返回值为位置处的next中 LinkListNode *LinkList_Get(LinkList *list, int pos) { int i = 0; LinkListNode *current = NULL; TLinkList *tList = NULL; tList = (TLinkList *)list; if (list == NULL || pos < 0) { return NULL; } current = &(tList->header); for (i = 0; i < pos; i++) { current = current->next; } return current->next; }

删除某位置处的结点

插入的反向操作···· 从头结点蹦到位置处的指针缓存要删除的结点的指针

接传入list的指针

list不为空，删除位置>=0，函数操作的基本

头指针蹦到删除位置处辅助缓存指针缓存下即将删除的结点p->next=p->next->next 核心操作原来的链表长度要减少 LinkListNode *LinkList_Delete(LinkList *list, int pos) { int i = 0; LinkListNode *current = NULL; LinkListNode *ret = NULL; TLinkList *tList = NULL; tList = (TLinkList *)list; if (list == NULL || pos < 0) { return; } current = &(tList->header); for (i = 0; i < pos; i++) { current = current->next; } ret = current->next; current->next = ret->next; tList->Length--; return ret; }