数据结构与算法——单链表01

链表的解释

链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

“车头” ：plist是个变量，存储的是个地址，说明他是个指针
“车厢” ： 相当于一个结点，不同于顺序表的是，它不仅存储数据，还存储了一个地址（或是个指针，因为指针存储地址）。

这是两个不同类型的数据，只有结构体才能保存不同类型的数据 ————>由图知，每个结点由需要存储的数据和保存下一个结点的地址的指针组成

struct SListNode //S->Single   SListNode 由结点组成的单链表
{int data;//存储的数据struct SListNode* next;//指向下一个结点的指针
}

每个结点都是个独立的空间                  

单链表的打印

//手动构造链表
void test01()
{//创建结点SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));//malloc申请空间不用去增容，此处是申请一个结点大小的空间SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));node1->data = 1;node2->data = 2;node3->data = 3;node4->data = 4;node1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;SLTNode* list = node1;SLTPrint(list);//实参  //形参的改变需要影响实参的时候才需要传地址，这里不需要改变第一个结点所以不用传址调用
}

创建一个打印函数

void SLTPrint(SLTNode* phead) //形参
{SLTNode* pcur = phead;while (pcur != NULL){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("NULL\n");
}

phead指向头结点，但是为什么又要用pcur去遍历？
因为我们需要一个值一直指向头结点，如果用phead遍历后，没有指向头结点的指针
且要插入一个结点需要从头结点遍历，所以我们需要创建一个pcur

单链表的数据插入

尾插

把数据存在链表里面，必须给这个数据申请一个结点，然后往链表里面去插入
如图：为数据8创建一个结点，然后往链表里面插，这样4的next指针不指向NULL而是指向保存8这个结点的地址，就是指向newnode，所以首先要找到4这个结点，利用ptail遍历找尾

循环条件：（ptail—>next ！= NULL ）

链表为空：plist = NULL
newnode 就是 头结点，不用找尾

//创建结点
SLTNode* SLTbuyNode(SLTDataType x)
{//根据x创建新结点SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)  //pphead为&plist ，*pphead则是plist，**pphead则是*plist，就是结点
{assert(pphead);SLTNode* newnode = SLTbuyNode(x);//链表为空if (*pphead == NULL) //plist等于空的时候{*pphead = newnode;}else{//找尾结点SLTNode* ptail = *pphead;  while (ptail->next != NULL){ptail = ptail->next;}//找到了尾结点 ptail newnodeptail->next = newnode;}
}

void test02()
{//创建空链表SLTNode* plist = NULL; SLTPrint(plist);SLTPushBack(&plist, 1); //plist是指向结点地址的指针，&plist则是指向结点地址指针的地址SLTPrint(plist);
}int main()
{// test01();test02();return 0;
}

时间复杂度：O(n)

头插

newnode——>next 需要指向第一个结点，头插操作完成了，但是对链表来说还需要从头结点来遍历，还需要将phead移到新结点下面

void test02()
{//创建空链表SLTNode* plist = NULL; SLTPrint(plist);//SLTPushBack(&plist, 1); //plist是指向结点地址的指针，&plist则是指向结点地址指针的地址SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPrint(plist);
}int main()
{// test01();test02();return 0;
}

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTbuyNode(x);//链表为空和不为空一样newnode->next = *pphead;*pphead = newnode;
}

时间复杂度：O(1)

尾删

不仅要找到尾结点删掉，还要找到前一个结点把他的存储下一个结点地址的指针给为NULL
先让prev的指针指向NULL，然后删掉尾结点 prev一定是ptail的前一个结点
注意：只有一个结点和多个结点的操作是不同的 一个结点只需要直接释放掉然后赋NULL

//尾删
void SLTPPopBack(SLTNode** pphead)
{assert(pphead && *pphead);//只有一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* prev = NULL;SLTNode* ptail = *pphead;//指向第一个结点while (ptail->next != NULL){prev = ptail;ptail = ptail->next;}//prev和ptail都找到prev->next = NULL;free(ptail);//释放掉ptail = NULL;}
}

时间复杂度：O(n)

头删

phead指向第一个结点，第二个结点变成新的结点，所以在删除之前，将头结点的下一个结点存下来，然后将头结点删掉，让phead走到next
只有一个结点的情况：和多结点一样

//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* next = (*pphead)->next; //头结点的下一个结点存下来，然后将头结点删掉free(*pphead);*pphead = next;
}

时间复杂度：O(1)