双链表实现

柔情只为你懂 2022-05-10 20:50 239阅读 0赞

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

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

下面贴代码

#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);
    }