创建头节点,首先要创建一个没有存储值的头节点,我们本身定义了 NODE 结构体,可以根据NODE类型动态分配一块内存空间
// 创建一个值域为空的头结点,给头指针分配内存 PNODE pHead = (PNODE)malloc(sizeof(PNODE)); // 头指针创建新节点,需要根据定义的长度循环,这里的难点就是如何把新节点挂到链表尾部【这里还是要明确指针和指针变量的概念,这样会更好理解一些】
为了能让新创建的节点挂到尾部,我们直接使用pHead->pNext = pNew;
是不行的,这样只能最后添加一个,并且其他的都会被泄漏。这里我们使用一个站位尾节点来表示尾节点
为了便于理解,请先弄清楚,指针和指针变量区别,下图逐步讲解

2 遍历链表
遍历链表思路:
遍历链表只能通过头结点的 pNext 指针找到下一个节点,并循环到 pNext == NULL 为止,分别打印 值域的值即可。
3 判断是否为空链表
判断是够为空链表,直接拿头结点的 pNext 指针取值判断是否为 NULL 即可
bool isEmpty_list(PNODE pHead) { if ((*pHead).pNext == NULL) { return false; }else{ return true; } }4 求链表长度
求链表长度类似于遍历链表,这里主要是计算有效节点的个数,这个个数就是长度
int length_list(PNODE pHead) { PNODE p = pHead->pNext; int len = 0; while (p->pNext == NULL) { len++; p = p->pNext; } return len; }5 插入节点

其实思路很简单,主要是吧 p指向节点的的pNext 指向 q, 然后q所指向的下个节点直接指向原来p所指向的节点。 伪代码如下: temp = p->pNext; p->pNext -> q; q->pNext = temp; 或者直接 q->pNext = P->pNext; P->pNext = q;
本方法代码实现
bool insert_list(PNODE pHead , int pos , int val){ // 判断位置是否合法 PNODE q = pHead; // 要插入的位置,如果是 <= 0,则直接插到最前面,如果是 pos = 1 就插入第一个后面,pos = n,就插到第 n 个后面 int i = 0; while (i < pos) { if (q->pNext == NULL) { printf("要插入的位置不合法;大于链表长度\n"); break; }else{ q = q->pNext; //要被插入的节点 i++; } } // 插入操作 PNODE p = (PNODE)malloc(sizeof(NODE)); if (p == NULL) { printf("动态分配内存失败\n"); exit(0); } p->data = val; // 前一个节点为q, 直接添加到 q 后面。 p->pNext = q->pNext; q->pNext = p; return true; }6 删除节点

// 思路: // 想要删除后面的节点,直接让 p 的指针域指向下下个节点就完成了 // 这里的删除其实很方便,但是有个容易造成内存泄漏的误区 // 因为直接删除之后,我们就无法在拿到 p 后面的节点的地址,然后无法释放,最终内存泄漏 // 最终实现: temp = p->pNext; // 临时变量保存要删除节点地址 p->pNext = p->pNext-pNext; // p 的指针域指向下下个节点 free(temp); // 释放被删除节点内存代码实现
bool delete_list(PNODE pHead , int pos , int * val){ // 找到要被删除的元素保存起来 PNODE p = pHead; int i = 0; while (i < pos - 1) { // 找到被删除节点的前一个节点 if (p->pNext == NULL) { break; } p = p->pNext; i++; } if (i < pos && p->pNext == NULL) { printf("你要删除的位置非法,此位置不在链表长度范围之内\n"); return false; } // 找到了要被删除的那个节点 PNODE t = p->pNext;; *val = t->data; // 把被删除节点的值传给外面 p->pNext = t->pNext; // 直接指向后面一个节点 free(t); // 释放被删除节点内存,防止内存泄漏 return true; }7 链表排序
链表排序同数组不同,但很相似,都是把所有元素遍历然后找到相邻或者相反的值互换位置。