首页 > 代码库 > 单链表节点的添加和删除

单链表节点的添加和删除


  1. 单链表的节点定义

    struct ListNode{
    	int m_nValue;
    	ListNode* m_pNext;
    };
    
  2. 在单链表的末尾添加结点

    void AddToTail(LIstNode** pHead,int value)
    {
    	ListNode* pNew = new ListNode();
    	pNew->m_nValue = http://www.mamicode.com/value;"hljs-keyword" style="color: #e3ceab">if(*pHead == NULL)
    		*pHead = pNew;
    	else
    	{
    		ListNode* pNode = *pHead;
    		while(pNode->m_pNext != NULL)
    		pNode=pNode->m_pNext;
    		pNode->m_pNext = pNew;
    	}
    }
    
  3. 在单链表中找到第一个含有某个值的结点并删除

    void RemoveNode(ListNode** pHead,int value)
    {
    	if(pHead == NULL || *pHead == NULL)
    		return;
    	//定义一个ListNode指针,用于释放要删除的结点
    	ListNode* pToBeDeleted = NULL;  
    	if((*pHead)->m_nValue =http://www.mamicode.com/= value)"hljs-keyword" style="color: #e3ceab">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 =http://www.mamicode.com/= value)"hljs-keyword" style="color: #e3ceab">if(pToBeDeleted != NULL)
    		{
    			delete pToBeDeleted;
    			pToBeDeleted = NULL;
    		}
    	}
    }
    

重点问题:

  • 为什么在添加和删除函数参数中要用二级指针?
     首先要说的是,函数的参数在传递的过程中,传递的是实参的一个拷贝。在搜索别人的解释的过程中,也有人反复强调的另一点是:指针也是有地址的。ok,那么如果函数的参数是一级指针ListNode* pHead,那么函数中使用的pHead是什么?答案是,指向头结点的指针的副本,也就是另一个指向头结点的指针。
     
     好了,也就是说接下来在函数中所有的操作都是从这个临时的pHead开始的。从我们的函数名来看,AddToTail也就是从尾部插入,那这么看来,我只是从尾部插入新的结点,看起来并不影响头指针。
     那么问题来了,函数中的第七行的判断,如果头指针为空,也就是链表为空的时候,如果要新插入结点,那么从函数看来我们会改变头指针pHead另其指向新结点。但是! 前边我们说了,这个pHead只是函数中的一个 临时变量,这个指针本身的地址不同于函数外实参指针的地址,而它虽然指向了新结点,但函数外本身传入的头指针仍然为 NULL!

     同理,在删除结点的时候,如果要删除的结点即第一个结点,使用一级指针也会出错,此时会导致原头指针指向的链表为空。最后是一个网上借来的图:出自使用双重指针实现链表结点的插入与删除

     

    技术分享

     

     

单链表节点的添加和删除