详细介绍关于链表【数据结构】

链表

顺序表缺点：

• 空间不够了 需要扩容，但是扩容是有消耗的
• 头部或中间位置需要插入或删除，需要挪动 ，但是挪动是有消耗的
• 避免频繁扩容 ，一次一般都是去按倍数去扩2倍，可能存在一定的空间浪费
  我们采用链表解决问题

顺序表优点：

• 支持随机访问

链表优点：

• 按照需求申请空间，不用了就释放空间，更加合理的运用空间
• 头部中间插入或删除数据 ，不需要挪动数据，不存在空间浪费

缺点：

• 每插入一个数据，都需要存一个指针去链接后面的数据节点 ，
• 不支持随机访问，用下标直接访问第i个（ arr[ i ] )

单链表

typedef struct  SListNode  // 单链表
{SLDataType data;struct  SListNode* next;
}SLTNode; //单链表类型
void SListPrint(SLTNode* phead)
{SLTNode* cur= phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}
}

尾插

尾插的本质是原来的尾节点需要存储新的尾节点地址

void SListPushBack(SLTNode** pphead  , SLDataType x) // 尾插
{                                                                                              //插入SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));newnode->data = x;newnode->next = NULL;if (*pphead == NULL) //链表中一个节点都没有，就不用去找尾{*pphead = newnode;}else{//找到尾节点SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}}

头插

 SLTNode *  BuySingListNode(SLDataType x)//创建节点
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));newnode->data = x;newnode->next = NULL;return newnode; 
}
void SListPushFront(SLTNode** pphead, SLDataType x) // 头插
{//创建节点SLTNode* newnode =BuySingListNode(x);newnode->next = *pphead;*pphead = newnode;
}

尾删

第一种方式删除

void SListPopBack(SLTNode** pphead)  // 尾删
{assert(*pphead != NULL);  //头指针是否为空//只有一个节点if ( (*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//两个或两个以上的节点else{SLTNode* p = NULL;//找尾节点SLTNode* tail = *pphead;while (tail->next != NULL){p = tail;//p指针记录倒数第二个节点 ，并且将节点置空tail = tail->next;}free(tail);//删除tail = NULL;p->next = NULL;}}

第二种

void SListPopBack(SLTNode** pphead)  // 尾删
{assert(*pphead != NULL);  //头指针是否为空//只有一个节点if ( (*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else  //不创建临时变量p的方式去尾删{//找尾节点SLTNode* tail = *pphead;while (tail->next->next){tail = tail->next;}//删除free(tail->next);tail->next = NULL;}}

头删

void SingleListPopFront(SLTNode** pphead)
{assert(*pphead);SLTNode* first = *pphead;*pphead = first->next;free(first);first = NULL;}

查找

int  SingleListFind(SLTNode* phead, SingleListDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;}

pos之前插入

void SingleListInsert(SLTNode** pphead, SLTNode* pos, SingleListDataType x)
{assert(pos);assert(pphead);//只有一个节点相当于头插if (*pphead ==pos){SingleListPushFront(pphead ,x);}else//多个节点{//找到pos的前一个位置SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLTNode* newnode = BuySingListNode(x);prev->next = newnode;newnode->next = pos;}
}

pos位置删除

void SingleListErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);//只有一个节点相当于头删if (*pphead==pos){SingleListPopFront(pphead);}// 多个节点else{//找到pos的前一个位置SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}}

pos后面插入

void SingleListInsertAfter(SLTNode* pos, SingleListDataType x)  //pos后面插入
{assert(pos);SLTNode* newnode = BuySingListNode(x);newnode->next = pos->next;pos->next = newnode;
}

pos位置后面删除

void SingleListEraseAfter(SLTNode* pos)   // 从pos后面删除
{assert(pos);assert(pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}

如果你觉得这篇文章对你有帮助，不妨动动手指给点赞收藏加转发，给鄃鳕一个大大的关注
你们的每一次支持都将转化为我前进的动力！！！