双向链表

「爱情、让人受尽委屈。」 2022-07-03 13:57 274阅读 0赞

**一、解析**

在单链表中，有了next指针，要查找下一节点的时间复杂度为O(1)，如果要查找的是上一节点的话，最坏的时间复杂度是O(n)了，以为每次都要从头开始查找。为了克服这个缺点引入了双链表设计：

**双链表（doublelinked list）:是在单链表的每个节点中，在设置一个指向其前驱节点的指针域。**双链表有两个指针域，一个指向直接前驱，一个指向直接后继。

/*线性表的双向链表存储结构*/
    typedef struct DulNode
    {
    	ElemType data;
    	struct DulNode *prior;//直接前驱指针
    	struct DulNode *next;//直接后继指针
    }DulNode,*DuLinkList;

双向链表的循环带头结点的空链表如图所示：

![Center][]

非空的循环的带头结点的双向链表如下图所示：

![Center 1][]

废话：双向链表中的某一结点p，他的后继的前驱是它自身，即p;

p->next->prior = p =->prior->next

**二、元素插入**

元素e的结点为s，要实现将结点s插入到结点p和p->next之间需要如下操作：

![Center 2][]

s->prior =p;//把p赋值给s的前驱，如图中①

s->next =p->next;//把p->next赋值给s的后继，如图中②

p->next->prior= s;//把s赋值给p->next的前驱，如图中③

p->next = s；//把s赋值给p的后继，如图中④

关键在于他们的顺序，由于第2步和第三步都用到了p->next。如果第4步先执行，则会使得p->next提前变成s，使得插入的工作完不成。理解记忆，插入的顺序是先搞定s的前驱和后继，再搞定结点的前驱，最后解决前结点的后继。

**四、元素删除**

删除结点p：

![Center 3][]

p->prior->next = p->next;//把p->next赋值给p->prior的后继，如图中①

p->prior->prior = p->prior;//把p->prior赋值给p->next的前驱，如图中②

free(p);

双向链表最大的特点就是用空间换取时间，提升程序运行速度。

C语言实现双向链表：

#include <stdio.h>
    #include <malloc.h>
    #include <stdlib.h>
    #include <string.h>
    
    enum
    {
    	PRINT_LIST = 1,
    	PRINT_LIST_REVE,
    	LIST_LEN,
    	IS_NULL,
    	CLEAR_LIST,
    	INSERT_EML_LIST,
    	DELETE_EML_LIST,
    	DEST_LIST
    };
    
    //打印选项
    void help()
    {
        printf("\n");
    	printf("%d.打印双向链表\n",PRINT_LIST);
    	printf("%d.逆序打印双向链表\n",PRINT_LIST_REVE);
    	printf("%d.求链表长度\n",LIST_LEN);
    	printf("%d.判断链表是否为空\n",IS_NULL);
    	printf("%d.清空链表\n",CLEAR_LIST);
    	printf("%d.插入元素\n",INSERT_EML_LIST);
    	printf("%d.删除元素\n",DELETE_EML_LIST);
    	printf("%d.释放链表\n",DEST_LIST);
    	printf("0.退出\n");
    	printf("\n");
    }
    
    typedef struct DuLnode
    {
        int data;              //数据
        struct DuLnode *prior; //前驱
        struct DuLnode *next;  //后继
    }DuLnode,*DuLinkList;
    
    //初始化双向链表
    void initList(DuLinkList &L)
    {
        int i = 0;
        DuLinkList p,q;
    	char initDate[10] = {1,2,3,4,5,6,7,8,9};
        L = (DuLinkList)malloc(sizeof(DuLnode));
        L->next = NULL;
        L->prior = NULL;        //构造头结点
        p = L;
    
    	for(i = 0;i < strlen(initDate);i++)
        {
            q = (DuLinkList)malloc(sizeof(DuLnode));
            q->data = initDate[i];  //得到的是输入字符的ASCII码，减去30H就变成想要的数字，十六进制30h即为十进制48
            q->next = NULL;
            q->prior = p;
            p->next = q;
            p = q;
    
        }
        printf("双向链表构造完毕!\n");
    }
    
    //打印双向链表
    void printList(DuLinkList &L)
    {
        DuLinkList p;
    
        if(L == NULL)
        {
            printf("链表不存在，请先初始化!\n");
        }
        else if(L->next == NULL)
        {
            p = L->next;
            printf("链表为空!\n");
        }
        else
        {
            p = L->next;
            while(p)
            {
                printf("%d ",p->data);
                p = p->next;
            }
    		printf("\n");
        }
    }
    
    //逆序打印双向链表
    void printListReverse(DuLinkList &L)
    {
        DuLinkList p;
    
        if(L == NULL)
        {
            printf("链表不存在，请先初始化!\n");
        }
        else if( L->next == NULL )
        {
            p = L->next;
            printf("链表为空!\n");
        }
        else
        {
            p = L->next;
            while(p->next)
            {
                p = p->next;
            }
    
            while(p->prior)
            {
                printf("%d ",p->data);
                p = p->prior;
            }
    		printf("\n");
        }
    }
    
    //求链表长度
    int lengthDlist(DuLinkList &L)
    {
        int i = 0;
    
        if(L == NULL)
        {
            printf("链表不存在，请先初始化!\n");
        }
        else
        {
            DuLinkList p = L->next;
            while(p)
            {
                i++;
                p = p->next;
            }
        }
    
        return i;
    }
    
    //判断链表是否为空
    void isEmptyList(DuLinkList &L)
    {
        if(L == NULL)
        {
            printf("链表不存在，请先初始化!\n");
        }
        else if( L->next == NULL )
        {
            printf("链表为空!\n");
        }
        else
        {
            printf("链表非空!\n");
        }
    }
    
    //把双向链表置空
    void clearList(DuLinkList &L)
    {
        if(L==NULL)
        {
            printf("链表不存在，请先初始化!\n");
        }
        else
        {
            DuLinkList p,q;
            p = q = L->next;   //是p、q指向第一个元素
            L->next = NULL;
    
            while(p)          //逐个释放元素所占内存
            {
                p = p->next;
                free(q);
                q = p;
            }
        }
    }
    
    //删除双向链表
    void destroyList(DuLinkList &L)
    {
        clearList(L);
        free(L);
        L = NULL;
    }
    
    //在双向链表中第i个位置后面插入元素m
    void insertElmList(DuLinkList &L)
    {
        int i,m;
        printf("输入插入的元素:\n");
        scanf("%d",&m);
        printf("输入插入的位置:\n");
        scanf("%d",&i);
        DuLinkList p,q;
        p = L;
        int j = 0;
    
        if(L == NULL)
        {
            printf("链表不存在，请先初始化!\n");
        }
        else if(L->next == NULL)
        {
            printf("链表为空，请初始化后再进行插入数据操作!\n");
        }
        else if( i<1 || i>lengthDlist(L)+1 )
        {
            printf("插入位置错误!\n");
        }
        else
        {
            while( j<i )
            {
                p = p->next;
                j++;
            }
    
            if( j == lengthDlist(L) )      //如果在最后一个元素后面插入m
            {
                q = (DuLinkList)malloc(sizeof(DuLnode));
                q->data = m;
                q->next = NULL;
                q->prior = p;
                p->next = q;
            }
            else
            {
                q = (DuLinkList)malloc(sizeof(DuLnode));
                q->data = m;
                q->next = p->next;
                p->next->prior = q;
                p->next = q;
                q->prior = p;
            }
        }
    }
    
    //删除双向链表中的第i个元素
    void delElmList(DuLinkList &L)
    {
        int i;
        printf("输入要删除的位置:");
        scanf("%d",&i);
        int j = 0;
        DuLinkList p = L;
    
        if(L == NULL)
        {
            printf("链表不存在，请先初始化!\n");
        }
        else if( i<1 || i>lengthDlist(L) )
        {
            printf("删除的位置不存在!\n");
        }
        else
        {
            while( j<i )
            {
                p = p->next;
                j++;
            }
    
            if( j == lengthDlist(L) )
            {
                p->prior->next = NULL;
                free(p);
            }
            else
            {
                p->prior->next = p->next;
                p->next->prior = p->prior;
                free(p);
            }
        }
    }
    
    
    int main()
    {
        int i;
        DuLinkList L = NULL;
        help();
    
    	//初始化双向链表
    	initList(L);
        printf("请输入操作:");
        scanf("%d",&i);
        while( 0 != i)
        {
            switch(i)
            {
            case PRINT_LIST:
    			printList(L);
                break;
            case PRINT_LIST_REVE:
    			printListReverse(L);
                break;
            case LIST_LEN:
    			printf("链表长度为:%d\n",lengthDlist(L));
                break;
            case IS_NULL:
    			isEmptyList(L);
                break;
            case CLEAR_LIST:
    			clearList(L);
                break;
            case INSERT_EML_LIST:
    			insertElmList(L);
                break;
            case DELETE_EML_LIST:
    			delElmList(L);
                break;
            case DEST_LIST:
    			destroyList(L);
                break;
            default:
    			printf("输入错误，请重新输入!\n");
                break;
            }
            help();
            printf("请输入操作:");
            scanf("%d",&i);
        }
        if(0 == i)
        {
            printf("程序退出....\n");
        }
        return 0;
    }

[Center]: /images/20220618/3fc959df10f6463eb556dd37304bb1f0.png
[Center 1]: /images/20220618/23ed7ed773784a9aa1d71b924bea38cc.png
[Center 2]: /images/20220618/124b6e66011e45a4af35a27943f21c42.png
[Center 3]: /images/20220618/0686ff046fbb4a0aa648c9f6df4538da.png