单链表节点的添加和删除

  1. 单链表的节点定义
struct ListNode
{
  	int       m_nValue;
  	ListNode* m_pNext;
};
  1. 在单链表的末尾添加结点
void AddToTail(LIstNode** pHead,int value)
{
	ListNode* pNew = new ListNode();
	pNew->m_nValue = value;
	pNew->m_pNext = NULL;

	if(*pHead == NULL)
		*pHead = pNew;
	else
	{
		ListNode* pNode = *pHead;
		while(pNode->m_pNext != NULL)
		pNode=pNode->m_pNext;
		pNode->m_pNext = pNew;
	}
}
  1. 在单链表中找到第一个含有某个值的结点并删除
void RemoveNode(ListNode** pHead,int value)
{
	if(pHead == NULL || *pHead == NULL)
		return;
	//定义一个ListNode指针,用于释放要删除的结点
	ListNode* pToBeDeleted = NULL;
	if((*pHead)->m_nValue == value)
	{
		pToBeDeleted = *pHead;
		*pHead = *pHead->m_pNext;
	}
	else
	{
	// 定义一个临时的指针,用于遍历链表以找到要删除的结点(如果存在的话)的前一个结点
		ListNode* pNode = *pHead;
		while(pNode->m_pNext != NULL && pNode->m_pNext->m_nValue != value)
			pNode = pNode->m_pNext;
		if(pNode->m_pNext != NULL && pNode->m_pNext->m_nValue == value)
		{
			pToBeDeleted = pNode->m_pNext;
			pNode->m_pNext = pNode->m_pNext->m_pNext;
		}
		if(pToBeDeleted != NULL)
		{
			delete pToBeDeleted;
			pToBeDeleted = NULL;
		}
	}
}

重点问题:

  • 为什么在添加和删除函数参数中要用二级指针?

     首先要说的是,函数的参数在传递的过程中,传递的是实参的一个拷贝。在搜索别人的解释的过程中,也有人反复强调的另一点是:指针也是有地址的。ok,那么如果函数的参数是一级指针ListNode* pHead,那么函数中使用的pHead是什么?答案是,指向头结点的指针的副本,也就是另一个指向头结点的指针。

     

     好了,也就是说接下来在函数中所有的操作都是从这个临时的pHead开始的。从我们的函数名来看,AddToTail也就是从尾部插入,那这么看来,我只是从尾部插入新的结点,看起来并不影响头指针。

     那么问题来了,函数中的第七行的判断,如果头指针为空,也就是链表为空的时候,如果要新插入结点,那么从函数看来我们会改变头指针pHead另其指向新结点。但是! 前边我们说了,这个pHead只是函数中的一个 临时变量,这个指针本身的地址不同于函数外实参指针的地址,而它虽然指向了新结点,但函数外本身传入的头指针仍然为 NULL!

     同理,在删除结点的时候,如果要删除的结点即第一个结点,使用一级指针也会出错,此时会导致原头指针指向的链表为空。

时间: 04-21

单链表节点的添加和删除的相关文章

C语言实现单链表节点的删除(带头结点)

我在之前一篇博客<C语言实现单链表节点的删除(不带头结点)>中具体实现了怎样在一个不带头结点的单链表的删除一个节点,在这一篇博客中我改成了带头结点的单链表.代码演示样例上传至 https://github.com/chenyufeng1991/DeleteLinkedList_HeadNode.删除类型有两种: (1)删除某个位置pos的节点: (2)推断x值是否在链表中,若存在则删除该节点: 核心代码例如以下: //删除某个位置pos的节点 Node *DeletePosNode(Node

父兄子节点的获取及子节点的添加、删除、克隆操作

第一.父兄子节点的获取 1.父节点的获取 某节点的parentNode属性值即为该节点的父节点.示例: <!DOCTYPE html> <html> <head lang="en"> <meta charset="UTF-8"> <body> <div id="father"> <div id="son1"></div> </

删除单链表节点,时间复杂度为O(1)

一个编程练习,删除单链表一个节点,且时间复杂度控制在O(1)内. 1.核心操作代码如下: struct ListNode { int m_data; ListNode *m_pNext; }; void DeleteNode(ListNode **pListHead, ListNode *pToBeDeleted) { if(pListHead == NULL || pToBeDeleted == NULL) return; //=================================

单链表的逆向打印、删除无头的非尾节点、无头链表插入节点、约瑟环

//1.逆向打印链表(递归) void PrintTailToHead(ListNode *pHead) {                 ListNode *cur = pHead;                  if(cur != NULL)                 {                                 PrintTailToHead(cur->_next);                                 printf( "

c 单链表反转(不添加新结点空间)

最近复习考研,加上一直都将"算法"放在很高的位置,所以,蛮重视算法的.不多说了,其实这个问题,不难理解的. 主要代码: 1 //反转单链表. 2 void 3 reverse(linklist lList) { 4 Linknode *pre = NULL; //注意该结点不能再指向别的非空结点. 5 Linknode *cur = lList->next; 6 Linknode *next; 7 while(cur) { 8 next = cur->next; 9 cur

单链表 初始化 创建 头插法 尾插法 插入 删除 查找 合并 长度

#include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR -1 #define TRUE 1 #define FALSE -1 #define NULL 0 #define OVERFLOW -2 #define ElemType int #define Status int typedef int ElemType typedef int Status #define LEN sizeof(LNode) #

带头节点控制单链表之C语言实现

//  1.头.尾节点位置 //  2.链表 //  元素数量 #include <stdio.h> #include <stdlib.h> #include <strings.h> #include <string.h> //链表节点信息: // //   1.数据域 //   2.指针域 #define TRUE     (1) #define FALSE    (0) #define ZERO     (0) #define ONLY_ONE (1)

数据结构基础(8) --单链表的设计与实现(1)之基本操作

链表简介 数组的缺点: 1.元素插入:除了在数组的末尾插入元素之外,在数组的其他任何位置插入元素都需要进行数组元素的频繁移动(插入位置之后的元素都需往后移动), 时间复杂度约为O(N); 2.数组的删除:除了在数组的末尾删除元素之外,在数组的其他任何位置删除元素都需要进行数组元素的频繁移动(删除位置之后的元素都需往前移动), 时间复杂度也为O(N); 链表的特点: 由于在链表中插入/删除元素都不需要进行数据的移位, 只需要O(1)时间完成, 因此链表适用于频繁插入与删除的情况; 但是链表也有缺点

7. C#数据结构与算法 -- 存储结构(单链表)

C#定义并实现单链表 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Linked {     //单链表结点类,采用泛型       public class Node<T> {         private T data; //数据域,当前结点的数据           private