双链表实现

以前写的不带头的单链表实现，当时也啥也没学，好多东西不知道，加上一心想压缩代码，减少情况，所以写得不太好。

请教了老师，首先是命名问题和代码紧凑性等的改进。还有可读性方面的改进，多写了一些注释。并且因为带头的比较好写，好操作，所以标准写法也不是很长，繁琐。

下面贴代码

  

   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     

      #include <stdlib.h>
     
    
   

    

     

    
    

     

      #include <string.h>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      typedef struct node{
     
    
   

    

     

    
    

     
 int key;//数据
     
    
   

    

     

    
    

     
 struct node * prev;//前驱
     
    
   

    

     

    
    

     
 struct node * next;//后继
     
    
   

    

     

    
    

     

      }Node;
     
    
  
 

初始化（带头） 

  

   

    

     

    
    

     

      Node * list;
     
    
   

    

     

    
    

     

      //初始化，这里·我们list不再是NULL，而是指向了一个节点
     
    
   

    

     

    
    

     

      //这个改进方便了很多操作，也不用借助二重指针把list和next统一表示了
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void init(Node * list)//初始化
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 list = (Node *)malloc(sizeof(Node));
     
    
   

    

     

    
    

     
 list->next = NULL;
     
    
   

    

     

    
    

     
 list->prev = NULL;
     
    
   

    

     

    
    

     

      }
     
    
  
 

查找（不用再判断一下空不空）

  

   

    

     

    
    

     

      Node * find(int key,Node * list)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       Node * head = list->next;//从头节点后面开始找
     
    
   

    

     

    
    

     
 while(head != NULL && head->key != key)//找到或空跳出
     
    
   

    

     

    
    

     

       head = head->next;
     
    
   

    

     

    
    

     
 return head;
     
    
   

    

     

    
    

     

      }
     
    
  
 

打印

  

   

    

     

    
    

     

      void printList(Node * list)//打印
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       Node * temp = list->next;头节点下一个开始
     
    
   

    

     

    
    

     
 while(temp != NULL)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 printf("%d ",temp->key);
     
    
   

    

     

    
    

     

       temp = temp->next;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 printf("\n");
     
    
   

    

     

    
    

     

      }
     
    
  
 

删除指定结点

  

   

    

     

    
    

     

      void delete(Node * list)//删除指定结点
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 list->prev->next = list->next;前面后面指针改了，再free自己即可
     
    
   

    

     

    
    

     
 list->next->prev = list->prev;
     
    
   

    

     

    
    

     
 free(list);
     
    
   

    

     

    
    

     

      }
     
    
  
 

配合一下删除：

  

   

    

     

    
    

     

      void deleteKey(int key,Node * list)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 delete(find(key,list));
     
    
   

    

     

    
    

     

      }
     
    
  
 

头插：

  

   

    

     

    
    

     

      void insertHead(int key,Node * list)//头插
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       Node * newNode = (Node *)malloc(sizeof(Node));//初始化
     
    
   

    

     

    
    

     

       newNode->key = key;
     
    
   

    

     

    
    

     

       newNode->next = list->next;//赋值后继
     
    
   

    

     

    
    

     
 if(list->next != NULL)//如果有后继，赋值后继的前指针为新结点
     
    
   

    

     

    
    

     
 list->next->prev = newNode;
     
    
   

    

     

    
    

     
 list->next = newNode;//改头
     
    
   

    

     

    
    

     

       newNode->prev = list;//赋值新结点前指针
     
    
   

    

     

    
    

     

      }
     
    
  
 

按下标插入

单链表都写了，我就不写长度函数和判断非法了，用的时候注意吧。

  

   

    

     

    
    

     

      void insert(int key,Node * list,int index)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       Node * head=list;//最后指到要插位置的前一个即可
     
    
   

    

     

    
    

     

       Node * newNode = (Node *)malloc(sizeof(Node));//初始化
     
    
   

    

     

    
    

     

       newNode->key = key;
     
    
   

    

     

    
    

     
 while(index--)
     
    
   

    

     

    
    

     

       head = head->next;
     
    
   

    

     

    
    

     

       newNode->next = head->next;//修改指针
     
    
   

    

     

    
    

     

       newNode->prev = head;
     
    
   

    

     

    
    

     

       head->next = newNode;
     
    
   

    

     

    
    

     

      }
     
    
  
 

指定某值后插入不写了，和这个修改指针逻辑一样，再传一个find配合一下就行了。

然后简单测试

  

   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       Node * list = NULL;
     
    
   

    

     

    
    

     

       init(list);
     
    
   

    

     

    
    

     

       insertHead(1,list);
     
    
   

    

     

    
    

     

       insertHead(2,list);
     
    
   

    

     

    
    

     

       insertHead(3,list);
     
    
   

    

     

    
    

     

       printList(list);
     
    
   

    

     

    
    

     

       deleteKey(2,list);
     
    
   

    

     

    
    

     

       printList(list);
     
    
   

    

     

    
    

     

       insert(10,list,0);
     
    
   

    

     

    
    

     

       printList(list);
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/82784343