单向非循环链表

1、顺序表遗留问题

1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，使用malloc、realloc等函数拷贝数据，释放旧空间。会有不小的消耗。
3. 当我们以2倍速度增容时，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，若下次只是插入5个数据，就会浪费95个数据大小的空间。
为了改进、弥补顺序表的缺点，我们发明了链表。

2、什么是链表

概念：物理顺序：链表是一种物理存储结构上非连续、非顺序的存储结构。

           逻辑顺序：是通过链表中的指针链接次序实现的。

 

 3、接口函数以及结点的定义
typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct
SListNode* next; }SListNode; //单链表打印 void SLTPrint(SListNode* phead); //尾插 void
SLTPushBack(SListNode** pphead,SLTDataType x); //创建一个新结点的函数，并将新结点的数据初始化为x
SListNode* BuySLTNode(SLTDataType x); //尾删 void SLTPopBack(SListNode** pphead);
//头插 void SLTPushFront(SListNode** pphead, SLTDataType x); //头删 void
SLTPopFront(SListNode** pphead); // 单链表查找 SListNode* SListFind(SListNode*
plist, SLTDataType x); // 单链表在pos位置之后插入x void SListInsertAfter(SListNode* pos,
SLTDataType x); // 单链表删除pos位置之后的值 void SListEraseAfter(SListNode* pos);
//单链表在pos前面插入 void SListInsertBefore(SListNode** pphead, SListNode* pos,
SLTDataType x); //单链表在删除在pos位置的值 void SListErasepos(SListNode** pphead,
SListNode* pos); // 单链表的销毁 void SListDestroy(SListNode* plist);
 为了方便，我们将链表的数据类型定义为int，同时定义一个struct ListNode*类型的指针next，用来指向下一个结点。

由于链表不需要事前申请一块连续的空间，因此不需要初始化，只需定义一个SlistNode*类型的指针phead，作为链表的头指针，指向这个链表。

4、链表的打印
//单链表打印 void SLTPrint(SListNode* phead) { SListNode* cur = phead; while (cur)
{ printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }

创建一个cur指针变量指向头结点，然后用cur=cur->next来遍历，打印完data后再到下一个，直到打印完最后一个data，cur指向最后结点的next（指向NULL）。为了便于前期理解，最后打印一个NULL。下文插入操作后，演示打印效果。

5、创建（Buy）一个新结点
//创建一个新结点的函数，并将新结点的数据初始化为x SListNode* BuySLTNode(SLTDataType x) {
//建立一个新的结点,并将data初始化，next置为NULL SListNode* newnode =
(SListNode*)malloc(sizeof(SListNode)); if (NULL == newnode) { perror("malloc
fail"); return NULL; } newnode->data = x; newnode->next = NULL; return newnode;
}

先用malloc申请一个结点大小的空间，并将其交给一个newnode指针，确认申请成功后，对newnodd进行初始化，data=x，next置为NULL，（因为不知道要指向哪里，只是申请一个新结点，next指向的问题交给调用此函数的人来完成）。

然后将newnode返回，使用的人用某个结点的next指向它，就可以链接一个新结点。

6、尾插
//尾插 void SLTPushBack(SListNode** pphead,SLTDataType x) { SListNode* tmp =
BuySLTNode(x); if (NULL == tmp) { return; } SListNode* newnode = tmp;
//分情况，原来是否为空链表 if (*pphead == NULL)//为空链表 { *pphead = newnode;//建立phead与新结点的联系
} else { //先找到原来的尾结点，然后建立其与新结点的联系 SListNode* tail = *pphead; while (tail->next
!= NULL) { tail = tail->next; } //找到原来的尾结点后 tail->next = newnode; } }
链表是为了改进顺序表中头插和中间插入效率而产生的，与顺序表是互补关系，顺序表尾插时直接插入即可，消耗很小。但链表尾插时，需要先进行找尾操作，然后再尾插新数据。

注意：第一个参数是SListNode**
pphead，用来接收头指针的地址，这是一次传址调用，可以改变phead本身的内容，由于phead是头指针，改变的就是头指针指向的内容。

第一次尾插时，phead指向NULL，利用*pphead使其指向新的第一个结点。

如果用一个SListNode*
plist来接收，只是phead的形参，即一份临时拷贝，用plist接收newnode，只是在尾插函数内部起作用，而对外部的phead无影响，结果变成尾插一大顿，phead仍然指向NULL。

若phead不为NULL，则创建一个tail指针进行找尾操作。找尾过程中，tail->next为NULL，则此时tail指向尾结点，将newnode赋给tail->next即完成尾插。

 上图为尾插1234后的结果。

还有一点要注意：assert的使用，不能见到指针就用assert，有时传入的数据就是一个NULL，比如插入第一个元素时phead就是NULL，如果使用assert(phead)，就会报错导致无法插入。

而对于pphead即phead的地址，是一定不为NULL，就可以进行assert(pphead)的操作。

注意*pphead与pphead的区别

7、尾删
//尾删 void SLTPopBack(SListNode** pphead) {
assert（pphead）;//先检查pphead，再检查*pphead，若pphead为NULL，*pphead就会产生错误
assert(*pphead);//若原来为空链表，则无法删除 SListNode* cur = *pphead; //分情况，原来链表中有一个 还是
多个元素 if (NULL == cur->next) { free(cur); cur = NULL; *pphead = NULL; } else//
多个元素先找到倒数第二个 { SListNode* pretail = *pphead; while (pretail->next->next !=
NULL) { pretail = pretail->next; } free(pretail->next); pretail->next = NULL; }
}
先用assert确保phead不为NULL，即确保删除的不是空链表。

如果链表只有一个元素，free后，将phead置为NULL，使其成为空链表

当链表中有多个元素时，需要先找到尾结点的前一个元素pretail，方法是遍历，直到pretail->next->next为NULL，这里通过两个next，可以找到尾结点的那个next中的NULL，因此多个元素时使用这种方法，若只有一个元素则next的next会对NULL->,产生对于野指针解引用的错误。

总结：链表进行尾插尾删操作时，要先进行找尾，此过程需要遍历，效率较低，因此进行尾部操作时不如顺序表。

删除空链表时会报错。 

8、头插
//头插 void SLTPushFront(SListNode** pphead, SLTDataType x) { //先创造一个新结点
SListNode* tmp = BuySLTNode(x); if (NULL == tmp) { return; } SListNode* newnode
= tmp; //分情况讨论，原来链表是否为空 //if (NULL == *pphead) //{ // //如果为空，直接将phead与新结点连接即可
// *pphead = newnode; //} //else //{ // //不为空，建立新结点与原来头结点的联系 //
//将phead与原来头结点的联系变为与新结点的联系 // //原来A->B,现在A->C->B，先建立C->B,再建立A->C //
newnode->next = *pphead; // *pphead = newnode; //}
//是否为空都按不为空处理，next要么存原来头结点地址，要么为 NULL newnode->next = *pphead; *pphead =
newnode; }
链表的头插很简单，先buy一个新结点，然后将newnode->next指向原来的头结点，无论原来是否为NULL，再用phead指向这个新结点。

9、头删
//头删 void SLTPopFront(SListNode** pphead) { assert(*pphead); SListNode* first
= *pphead; *pphead = (*pphead)->next; free(first); first = NULL; }
创建first指针指向头结点，然后将phead指向下一个结点，不论是否为NULL，然后free掉first。

10、查找 
// 单链表查找 SListNode* SListFind(SListNode* phead, SLTDataType x) { SListNode*
cur = phead; while (NULL != cur) { if (cur->data == x) { return cur; } cur =
cur->next; } return NULL; }
利用cur遍历链表，如果找到x就返回cur，即存有x的结点的地址，没找到就继续遍历，cur==NULL时仍然未找到，则返回NULL。

 11、指定位置pos后方插入数据
// 单链表在指定位置后方插入 不用遍历 void SListInsertAfter(SListNode* pos,SLTDataType x) {
assert(pos); SListNode* newnode = BuySLTNode(x); if (NULL == newnode) {
perror("ButSLTNode fail"); return; } newnode->next = pos->next; pos->next =
newnode; }

将newnode->next连接pos的next，不论正负，然后将newnode赋给pos的next，此过程中不需要遍历，解决了顺序表在中间位置插入效率低的问题。

12、删除指定位置pos后方的数据
// 删除后面的 不用遍历 void SListEraseAfter(SListNode* pos) { assert(pos);
assert(pos->next != NULL); SListNode* del = pos->next; pos->next = del->next;
free(del); del = NULL;//del为形参，是否置空影响不大，到函数外自动销毁，一般由使用者进行置空 }
必须保证pos->next不为NULL，因为是删除pos位置的下一个元素，则至少有2个元素，若只有一个，next为NULL，再解引用会变为野指针。

用del保存要删除的位置，将pos的next与要删除元素的下一个元素连接，不论是否为NULL，然后free掉del，完成删除，也不需要遍历。

总结：链表的优点在于头部以及中间位置的插入和删除不需要遍历，这里中间位置，实际是pos的下一个元素。

任意位置后方进行插入/删除，不涉及phead的改变，因此只需要传入phead即可。

 13、在指定位置pos的前方插入元素

在前方插入删除涉及phead，因此传入&phead
//单链表指定位置之前插入元素，需要找prev void SListInsertBefore(SListNode** pphead,SListNode*
pos,SLTDataType x) { assert(*pphead);//不能为空，否则Find找不到pos assert（pos）;
SListNode* newnode = BuySLTNode(x); SListNode* prev = *pphead; if (pos ==
*pphead) { newnode->next = pos; *pphead = newnode; } else//找到pos前一个位置 {
SListNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; }
newnode->next = pos; prev->next = newnode; } }
若链表中只有一个元素，则会改变phead的指向，这里调用头插SLTPushFront也可以。

>=2个元素时，先找到prev，然后插入。

需要进行遍历找到prev。 

如果要找的位置pos是NULL，直接报错即可，是使用该函数的人的问题，函数只要完成应该完成的任务即可。

注意：假设传入的是plist，而不是它的地址，仍然用pphead接收，后续*pphead就会发生错误。因此可assert(pphead)。pphead实际上一定不为空，因此只要传入plist地址就要assert

14、删除指定位置pos的数据
//在指定位置pos的删除 void SListErasepos(SListNode** pphead, SListNode* pos) {
assert(pphead); assert(*pphead); assert(pos); SListNode* cur = *pphead; if (cur
== pos) { *pphead = pos->next; free(cur); cur = NULL; } else { SListNode* prev
= *pphead; while (prev->next != pos) { prev = prev->next; } prev->next =
pos->next; free(pos); } }
 

 如果pos指向第一个结点，即为头删，也可以使用SLTPopFront头删函数

接收Find的ret在erase后可以置为NULL，在函数外部完成，内部为形参。在内部改变需要传pos的二级指针。

而对于pphead则只能传二级指针，在函数内部修改phead的指向。

销毁时，利用tmp指针变量销毁当前位置，然后next找到下一个位置，遍历销毁。

总结：尾插尾删头插头删都需要pphead，insertafter和eraseafter仅需要pos，查找和打印仅需要phead，insertbefore、erasepos需要pphead、pos。

pos  phead  pphead  *pphead 的assert问题。

链表的优点缺点，某些位置是否需要遍历。

面试题：不告知phead，只知道pos，怎么在pos指向的数据之前插入数据？

例如原来为  1   2，pos指向2，可以在2的位置后插入3，然后将2、3两个data交换，结果为132，当然，此时pos指向的是3。

如果是删除不给phead删除pos当前位置，则将pos位置的值改为下一个位置的值，然后删除掉下一个位置的数据。（不能删除尾结点）

• « 上一篇：python中input的使用与循环
• » 下一篇：iOS 实现渐变色