文章目录【面试分享】嵌入式面试题常考难点之关于单链表的增删改查一、单链表结点定义二、增Create——插入结点1. 于链表头部插入结点头插法2. 于链表尾部插入结点尾插法3. 于链表中间插入结点3-1. 在指定结点前插入结点前插法3-2.在指定结点后插入结点后插法三、删Delete——删除结点1. 根据结点内容删除结点2. 根据位置删除结点3. 删除指针指向的结点经典面试题四、改Update和查Read————修改结点与查找结点【面试分享】嵌入式面试题常考难点之关于单链表的增删改查在众多经典数据结构中单链表以其简单灵活的特性成为嵌入式面试题库中的常客尤其是在考察增删改查CRUD操作时。本文旨在深入剖析单链表在面试场景中常考的难点通过解析这些基本操作的实现细节与优化策略帮助读者掌握应对相关面试题的技巧同时提升对链表这一基础数据结构的深刻理解。单链表作为一种线性数据结构其特点在于每个结点包含两部分存储数据的元素和指向下一个结点的指针。这一结构特性使得单链表在插入、删除等操作上相比数组展现出更高的效率但也给查找等操作带来了一定挑战。正因如此面试官倾向于通过单链表的增删改查来评估候选人对指针操作的熟练度、逻辑思维能力以及对时间与空间复杂度的敏感度。接下来我们将依次探讨单链表增Create、删Delete、改Update和查Read操作的核心逻辑、常见陷阱及优化思路力求为即将步入面试场的开发者们提供一份详实的备考指南。无论是追求极致性能的算法爱好者还是希望在面试中脱颖而出的求职者都能从本文中获得宝贵的知识与启发。关于链表反转的方法我在另一篇博客《嵌入式面试热点链表反转——四种单链表反转方法C语言》中做了详细的讨论欢迎有需要的小伙伴查阅。一、单链表结点定义为了方便介绍本文将使用以下结构体创建链表的结点typedefstructnode{intnodeId;charnodeData[20];structnode*next;}NODE;externNODE*head;并用如下链表初始化函数创建一条初始链表NODE*initList(NODE*pHead){NODE*tempNULL;for(intiMAX_NODE_NUM;i0;i--){temp(NODE*)malloc(sizeof(NODE));if(tempNULL){printf(Memory allocation failed!\n);exit(0);}else{temp-nodeIdi;temp-nextpHead;pHeadtemp;sprintf(temp-nodeData,Node_%d,temp-nodeId);}}returnpHead;}[!NOTE]上述代码中的MAX_NODE_NUM宏定义为 4也就是初始链表的长度为 4 个结点。打印链表 ID 的函数voidprintList(NODE*pHead){while(pHead!NULL){printf(%d - ,pHead-nodeId);pHeadpHead-next;}printf(NULL\n);}打印链表 ID 及信息的函数voidprintListData(NODE*pHead){while(pHead!NULL){printf( %d: %s\n |\n,pHead-nodeId,pHead-nodeData);pHeadpHead-next;}printf( NULL\n);}在main函数简单测试一下intmain(){headinitList(head);printList(head);putchar(\n);printListData(head);return0;}执行结果如下1 - 2 - 3 - 4 - NULL 1: Node_1 | 2: Node_2 | 3: Node_3 | 4: Node_4 | NULL后续创建链表的新结点使用以下函数NODE*createNewNode(){NODE*temp(NODE*)malloc(sizeof(NODE));if(tempNULL){printf(Memory allocation failed!\n);exit(0);}else{printf(Enter the Node Id: );scanf(%d,temp-nodeId);temp-nextNULL;sprintf(temp-nodeData,New_Node_%d,temp-nodeId);}returntemp;}[!NOTE]结点 ID 需要用户手动输入。二、增Create——插入结点1. 于链表头部插入结点头插法链表的头插法写法也是多种多样以下是两种常见写法在执行头插法时创建新结点后插入新结点并返回新的链表头指针NODE*insertAtHead(NODE*head){NODE*newNodecreateNewNode();newNode-nexthead;headnewNode;returnhead;}已经创建了新结点执行头插法时添加进链表并返回新的链表头指针NODE*insertAtHead(NODE*pHead,NODE*newNode){newNode-nexthead;pHeadnewNode;returnpHead;}其实不管怎么变化核心只有最后几句代码首先是newNode-next head让新结点的next指向链表的头部接入链表然后是pHead newNode让链表头指针指向新结点最后返回头指针。2. 于链表尾部插入结点尾插法链表的为插法跟头插法一样也是有两种常见写法在执行尾插法时创建新结点后先判断链表是否存在如果存在就添加进链表否则以该结点为链表头部创建链表并返回链表头指针NODE*insertAtTail(NODE*pHead){NODE*newNodecreateNewNode();NODE*temppHead;if(tempNULL){pHeadnewNode;newNode-nextNULL;}else{while(temp-next!NULL)temptemp-next;temp-nextnewNode;newNode-nextNULL;}returnpHead;}已经创建了新结点执行尾插法时先判断链表是否存在如果存在就添加进链表否则以该结点为链表头部创建链表并返回链表头指针NODE*insertAtTail(NODE*pHead,NODE*newNode){NODE*temppHead;if(tempNULL){pHeadnewNode;newNode-nextNULL;}else{while(temp-next!NULL)temptemp-next;temp-nextnewNode;newNode-nextNULL;}returnpHead;}两中尾插法的方式是一样的当链表存在时尾插法的插入过程就是通过while (temp-next ! NULL) temp temp-next;遍历链表判断当前结点是否为链表最后一个结点。一旦找到链表的最后一个结点就让该结点的next指针指向插入链表的新结点。[!NOTE]为什么头插法不需要判断链表是否存在而尾插法需要头插法和尾插法在插入结点时的处理方式不同在头插法中始终是在链表的头部插入一个新结点。这种方法不需要考虑链表是否为空因为新的头结点将始终指向当前的头结点即使链表为空head为NULL这也是有效的。在尾插法中需要遍历链表找到最后一个结点然后在其后插入一个新结点。如果链表为空就需要特别处理因为此时链表没有结点或者说链表不存在不存在所谓的尾结点。遍历一个不存在的链表是一种指针的非法访问会导致段错误。3. 于链表中间插入结点3-1. 在指定结点前插入结点前插法所谓前插法就是在链表中找到指定结点并在该结点前插入新结点。例如当前链表为0 - 1 - 2 - 3 - 4 - NULL现在有个新结点100要求插入并指定在结点3前插入插入后链表为0 - 1 - 2 - 100 - 3 - 4 - NULL。前插法在编码时需要考虑到一些特殊情况链表没有结点链表不存在这时有两种处理方式由开发者决定使用哪一种。一是直接返回错误代码告知功能使用者链表为空无法插入新结点。二是以当前新结点为链表头创建链表写法参考头插法。指定结点为链表头结点跟第一种情况第二点一样的处理处理方式差不多也是头插法的处理方式。链表存在但结点不存在如果遍历完这个链表都没找到指定的结点就可能是参数传递错误也可能是其他原因总之这种情况无法插入结点。可以通过输出 Log 的方式提示功能使用者并作出相应的处理动作。单链表不可反向回退单链表结点的特性就决定了链表只能单个方向遍历所以在遍历结点的时候应该通过临时指针temp指向的结点的next去找目标结点。如若不然只是用临时指针temp搜索目标结点就会出现找到目标结点也无法插入的情况如下图所示结合以上四种情况前插法的代码如下所示参数列表中不含新结点由前插法函数申请新结点NODE*insertBefore(NODE*pHead,intnodeId){NODE*newNodecreateNewNode();NODE*temppHead;if(tempNULL){pHeadnewNode;newNode-nextNULL;}elseif(temp-nodeIdnodeId){newNode-nextpHead;pHeadnewNode;}else{while(temp-next!NULLtemp-next-nodeId!nodeId)temptemp-next;if(temp-nextNULL){printf(Node not found!\n);free(newNode);}else{newNode-nexttemp-next;temp-nextnewNode;}}returnpHead;}参数列表中含新结点指针常用NODE*insertBefore(NODE*pHead,NODE*newNode,intnodeId){NODE*temppHead;if(tempNULL){pHeadnewNode;newNode-nextNULL;}elseif(temp-nodeIdnodeId){newNode-nextpHead;pHeadnewNode;}else{while(temp-next!NULLtemp-next-nodeId!nodeId)temptemp-next;if(temp-nextNULL){printf(Node not found!\n);}else{newNode-nexttemp-next;temp-nextnewNode;}}returnpHead;}两个代码核心部分是一样的代码解析如下通过if (temp NULL)判断链表是否存在如果不存在新结点newNode则作为链表头如果链表已经存在则通过else if (temp-nodeId nodeId)判断第一个节点是不是目标节点如果是则以头插法的方式把新结点插在目标结点前新结点成为新的链表头如果以上两个判断都不是则通过while (temp-next ! NULL temp-next-nodeId ! nodeId)遍历链表直到找到目标结点或者链表遍历结束如果目标结点未找到则输出 Log。在此处两个代码有一点区别如果新结点是由前插法内部生成的要注意把无法插入的新结点释放掉执行free(newNode);如果是传参传进来的新结点则不需要释放如果找到目标结点则通过newNode-next temp-next;把新结点挂在链表上。再通过temp-next newNode;把当前结点的next指针指向新结点完成新结点的插入。以下是前插法执行的动画过程3-2.在指定结点后插入结点后插法后插法相对于前插法要简单一些只需要找到目标结点并在其后面插入新结点即可其处理过程有点类似于尾插法。例如当前链表为0 - 1 - 2 - 3 - 4 - NULL现在有个新结点100要求插入并指定在结点2前插入插入后链表为0 - 1 - 2 - 100 - 3 - 4 - NULL。后插法在编码时也由一些需要注意的情况不过与前面提到的前插法差不多这里就不赘述了。后插法的代码如下所示参数列表中不含新结点由后插法函数申请新结点NODE*insertAfter(NODE*pHead,intnodeId){NODE*newNodecreateNewNode();NODE*temppHead;if(tempNULL){pHeadnewNode;newNode-nextNULL;}else{while(temp-next!NULLtemp-nodeId!nodeId)temptemp-next;if(temp-nodeId!nodeId){printf(Node not found!\n);free(newNode);}else{newNode-nexttemp-next;temp-nextnewNode;}}returnpHead;}参数列表中含新结点指针常用NODE*insertAfter(NODE*pHead,NODE*newNode,intnodeId){NODE*temppHead;if(tempNULL){pHeadnewNode;newNode-nextNULL;}else{while(temp-next!NULLtemp-nodeId!nodeId)temptemp-next;if(temp-nodeId!nodeId){printf(Node not found!\n);}else{newNode-nexttemp-next;temp-nextnewNode;}}returnpHead;}两个代码核心部分是一样的代码解析如下与前插法相同通过if (temp NULL)判断链表是否存在如果不存在新结点newNode则作为链表头如果链表存在则通过while (temp-next ! NULL temp-nodeId ! nodeId)遍历链表直到找到目标结点或者链表遍历结束通过if (temp-nodeId ! nodeId)判断while循环退出的具体原因如果遍历完链表目标结点未找到则输出 Log。在此处两个代码也是有区别原理跟前插法一样不赘述。如果是找到目标结点提前结束了while循环则通过newNode-next temp-next;把新结点挂在链表上。再通过temp-next newNode;把当前结点的next指针指向新结点完成新结点的插入。以下是后插法执行的动画过程三、删Delete——删除结点1. 根据结点内容删除结点一般链表的结点都有一个所谓的唯一标识符例如本文使用的结点中的nodeId这样可以通过这个唯一标识符找到对应的结点类似 Python 中的键值对nodeId的效果相当于键值对中的key。前面使用前插法和后插法都是使用了这个nodeId索引到对应的目标结点的。那么根据结点内容来删除结点也成了最常见的删除结点的办法通常这里的结点内容指的就是唯一标识符。在完成这个编码的时候也是需要注意以下两点判断链表是否存在如果不存在有可能是链表已经被删完了或者传参时没传入正确的参数此时应该立即返回并提示用户临时指针指向被删结点的上一个结点即将被删除的结点在被剔除链表之前它的上一个结点的next要先指向被删除的结点的下一个结点因为单链表不可逆因此在临时指针应当指在被删结点的上一个结点上这样才有利于删除的操作。结合以上两点根据nodeId删除结点的方法如下NODE*deleteNodeByNodeId(NODE*pHead,intnodeId){NODE*temppHead;if(tempNULL){printf(List is empty!\n);}elseif(temp-nodeIdnodeId){pHeadtemp-next;free(temp);}else{while(temp-next!NULLtemp-next-nodeId!nodeId)temptemp-next;if(temp-nextNULL){printf(Node not found!\n);}else{NODE*delNodetemp-next;temp-nextdelNode-next;free(delNode);}}returnpHead;}代码解析如下首先用临时指针temp代替链表头指针通过if (temp NULL)判断链表是否存在如果链表存在结合结点 ID通过else if (temp-nodeId nodeId)判断需要删除的结点是否是链表的头结点。如果是则将头指针后移到下个结点再将头节点释放如果以上两个情况都不符合则开始遍历链表直到找到目标结点或者链表遍历结束退出遍历之后如果没有找到目标结点则返回如果找到了目标结点则新建一个指针指向被删除结点先改变临时结点的next指向再释放目标结点完成删除。以下是该函数执行的动画过程2. 根据位置删除结点这种删除结点的方式不常见假设链表有 m 个结点要求删除第 n 个结点m ≥ n则在链表中找到第 n 个结点并删除。具体代码如下NODE*deleteNodeByPosition(NODE*pHead,unsignedintposition){NODE*temppHead;if(tempNULL){printf(List is empty!\n);}elseif(position0){pHeadtemp-next;free(temp);}else{for(unsignedinti0;iposition-1;i){if(temp-nextNULL){printf(Invalid position!\n);returnpHead;}temptemp-next;}NODE*delNodetemp-next;temp-nextdelNode-next;free(delNode);}returnpHead;}代码前半部分与前面大部分代码相似就不过多解释只从for循环开始解析如下因为 0 号结点算链表的第一个结点所以在for循环中的第二个表达式位置数要减一如果位置大于链表长度也就是已经遍历完链表了但还到达指定位置直接返回如果找到了目标结点删除结点的方法与上一个代码的方式一样此处省略。3. 删除指针指向的结点经典面试题这是一道 C 语言的经典面试题原题目不太记得大概就是在单链表中未给出头指针只有一个指针指向链表的某个结点现在要求删除这个结点。从前面提到两种删除结点的方式来看我们要删除单链表上的某一个结点N的话都是在N结点的上一个结点进行操作的我们用M结点来代替N结点的上一个结点。删除的过程就是让M结点的next指向N结点的下一个结点然后再释放N结点。但现在指针指在要求被删的结点上倒退回上一个结点是不可能的事所以这里就需要换一种思路来完成那就是“移花接木”。我们都知道链表主要的作用就是方便管理数据而数据是可以被复制、转移和修改的所谓删除结点可以理解为把这个结点的数据从链表上去除那么只要这个链表上没有这个结点的数据不就等同于把这个结点在链表上删除了吗因此本题的解法就是既然我们无法直接删除这个结点那就把下一个结点的数据复制到当下指针所指的结点上此时链表上就会有两个数据一样的结点包括next也复制然后再把当下指针所指的结点的下一个结点释放掉完成结点的删除。以下是删除给定指针指向的节点的函数实现intdeleteNode(NODE*node){if(nodeNULL||node-nextNULL){printf(Cannot delete the given node.\n);return-1;}NODE*tempnode-next;memcpy(node,temp,sizeof(NODE));free(temp);return0;}代码解析如下先判断node指针是否为空和node下一个结点是否存在满足任意条件直接返回-1用临时指针指向下一个结点把下一个结点的数据全部复制到本结点上然后是否下一个结点。[!NOTE]为什么node-next也不能为NULL如果node-next为NULL就说明node指针指向的是链表的最后一个结点没办法改变上一个结点的next指针指向NULL。如果把node指针所指的结点直接释放掉并不能使上一个结点的next指针指向NULL它依然是指向原本node所指的地址而此时该地址已经被释放后续所有的访问操作都是非法访问。四、改Update和查Read————修改结点与查找结点改和查我们放在一起来讲解因为修改结点数据其中就包含了查找结点。其实不单单是修改节点数据时有查找结点的操作前面提到的前插法和后插法还有删除结点的两个方法都包含了查找结点的操作。在单链表中查找某个结点通常有两个目的一个是读取里面的数据二是修改。我们先从比较简单的查找结点说起在前面删除结点的章节就提过链表的结点都有一个所谓的唯一标识符一般查找结点也是通过这个唯一标识符查找的所以查找结点的方法能很快的就写出来如下NODE*searchNode(NODE*pHead,intnodeId){NODE*temppHead;while(temp!NULL){if(temp-nodeIdnodeId)returntemp;temptemp-next;}returnNULL;}其实就是通过遍历的方式找到对应的结点。接下来是改数据一般来说改数据都是根据具体需求来决定例如我要别某个结点的nodeData内容改成其它内容我的代码可以这样写intupdateNode(NODE*pHead,intnodeId,char*newData){NODE*tempsearchNode(pHead,nodeId);if(temp!NULL){strcpy(temp-nodeData,newData);return0;}else{return-1;}}