手撸双向链表（c 语言）

什么是链表？

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表应该在学习数据结构中最简单的一种了吧，其实在linux内核中链表也随处可见，今天就来重新温习一下链表，该文以双向链表结构讲解。

链表分类

其实链表有好多种，对于初学者来说，被搞的乱七八糟。下面以图解的方式呈现给大家：
链表001.png

看上面的图 2 × 2 × 2 可以得到8种链表，比如非循环带头单向链表就是最简单的，也是学数据结构最开始学习的链表结构。

双向链表

那么双向带头链表，其实对于单链表来说，最大的区别就是在当前链表某个节点，不仅仅知道下一个节点，也知道它的上一个节点

结构

链表002.png


typedef struct Node{
    struct Node *prev;
    int elements;
    struct Node *next;
}T_Node,*P_Node;

上面定义了该链表的结构体

创建头结点

首先创建双向链表的头结点


P_Node Create_Head(void)
{
    P_Node head = NULL;
    head = malloc(sizeof(struct Node));
    head->next = NULL;
    head->prev = NULL;
    return head;
}

插入节点元素

插入节点有好多种方式，可以在头部插入，也可以在尾部，同时也可以在尾部插入，在此仅进行尾部插入。

下图是在中间插入元素节点图像：

链表003.png


/*
 * 在尾部节点插入新元素，也可以改为头部节点，或者某个位置插入，在此仅仅实现尾部插入新元素
 */
int Insert_Element(P_Node head,int element)
{
    if(!head)
    {
        printf("Head NULL\n");
        return (-1);
    }
    P_Node pTemp = head;
    while(pTemp->next)
        pTemp = pTemp->next;
    P_Node pElement = malloc(sizeof(struct Node));
    pElement->elements = element;
    pTemp->next = pElement;
    pElement->prev = pTemp;
    printf("Insert_Element success : %d\n",element);
    return (0);
}

删除链表节点

写了两个函数一个是删除链表所有节点，包括头结点，另一个是找到某个节点元素，删除这个元素。


/*
 * 删除全部节点
 */
int Delete_List(P_Node head)
{
    if(!head)
    {
        printf("Head NULL\n");
        return (-1);
    }
    P_Node pTemp = head;
    while(pTemp->next)
    {
        pTemp = pTemp->next;
    }

    while(pTemp != NULL)
    {
        free(pTemp);
        pTemp = pTemp->prev;
    }
    return (0);
}
/*
 * 删除某个节点
 */
int Delete_element(P_Node head,int element){
    P_Node pTmp = head->next;
    while(pTmp){
        if(pTmp->elements == element){
            if(!pTmp->prev){//如果是第一个元素
                head->next = pTmp->next;
                pTmp->next = NULL;
                free(pTmp);
                return (0);
            } else if(!pTmp->next){//如果是最后一个元素
                pTmp->prev->next = NULL;
                free(pTmp);
                return (0);
            }else{
                pTmp->prev->next = pTmp->next;
                pTmp->next->prev = pTmp->prev;
                free(pTmp);
                return (0);
            }
        }
        pTmp = pTmp->next;
    }
    printf("Not Found ！\n");
    return (-1);
}

遍历链表元素

遍历链表有好多种方法，在此进提供从头遍历代码参考，遍历链表，其实应该是很简单的操作，一个while循环就可以解决。


int Print_List(P_Node head)
{
    if(!head->next)
    {
        printf("Head NULL\n");
        return (-1);
    }
    P_Node pTemp = head->next;
    printf("list:  ");
    while(pTemp)
    {
        if(!pTemp->next){
            printf("%d\n",pTemp->elements);
        }else{
            printf("%d->",pTemp->elements);
        }
        pTemp = pTemp->next;
    }

    return (0);
}

查找链表元素

查找与遍历类似，只不过在遍历的基础上查找元素是否匹配。


int Find_List(P_Node head,int element)
{
    P_Node pTmp = head->next;
    int i=1;
    while (pTmp)
    {
        if (pTmp->elements == element)
        {
            printf("find %d in %d \n",element,i);
            return i;
        }
        i++;
        pTmp=pTmp->next;
    }
    printf("Not Found ！\n");
    return (-1);
}

完整代码


#include "stdio.h"
#include "stdlib.h"

typedef struct Node{
    struct Node *prev;
    int elements;
    struct Node *next;
}T_Node,*P_Node;

P_Node Create_Head(void)
{
    P_Node head = NULL;
    head = malloc(sizeof(struct Node));
    head->next = NULL;
    head->prev = NULL;
    return head;
}
/*
 * 在尾部节点插入新元素，也可以改为头部节点，或者某个位置插入，在此仅仅实现尾部插入新元素
 */
int Insert_Element(P_Node head,int element)
{
    if(!head)
    {
        printf("Head NULL\n");
        return (-1);
    }
    P_Node pTemp = head;
    while(pTemp->next)
        pTemp = pTemp->next;
    P_Node pElement = malloc(sizeof(struct Node));
    pElement->elements = element;
    pTemp->next = pElement;
    pElement->prev = pTemp;
    printf("Insert_Element success : %d\n",element);
    return (0);
}
/*
 * 遍历链表
 */
int Print_List(P_Node head)
{
    if(!head->next)
    {
        printf("Head NULL\n");
        return (-1);
    }
    P_Node pTemp = head->next;
    printf("list:  ");
    while(pTemp)
    {
        if(!pTemp->next){
            printf("%d\n",pTemp->elements);
        }else{
            printf("%d->",pTemp->elements);
        }
        pTemp = pTemp->next;
    }

    return (0);
}
/*
 * 删除全部节点
 */
int Delete_List(P_Node head)
{
    if(!head)
    {
        printf("Head NULL\n");
        return (-1);
    }
    P_Node pTemp = head;
    while(pTemp->next)
    {
        pTemp = pTemp->next;
    }

    while(pTemp != NULL)
    {
        free(pTemp);
        pTemp = pTemp->prev;
    }
    return (0);
}
/*
 * 删除某个节点
 */
int Delete_element(P_Node head,int element){
    P_Node pTmp = head->next;
    while(pTmp){
        if(pTmp->elements == element){
            if(!pTmp->prev){//如果是第一个元素
                head->next = pTmp->next;
                pTmp->next = NULL;
                free(pTmp);
                return (0);
            } else if(!pTmp->next){//如果是最后一个元素
                pTmp->prev->next = NULL;
                free(pTmp);
                return (0);
            }else{
                pTmp->prev->next = pTmp->next;
                pTmp->next->prev = pTmp->prev;
                free(pTmp);
                return (0);
            }
        }
        pTmp = pTmp->next;
    }
    printf("Not Found ！\n");
    return (-1);
}
/*
 * 查找
 */
int Find_List(P_Node head,int element)
{
    P_Node pTmp = head->next;
    int i=1;
    while (pTmp)
    {
        if (pTmp->elements == element)
        {
            printf("find %d in %d \n",element,i);
            return i;
        }
        i++;
        pTmp=pTmp->next;
    }
    printf("Not Found ！\n");
    return (-1);
}

int main(int argc,char* argv[]){
    P_Node p_head = Create_Head();
    Insert_Element(p_head,1);
    Insert_Element(p_head,2);
    Insert_Element(p_head,3);
    Insert_Element(p_head,4);
    Insert_Element(p_head,5);
    Insert_Element(p_head,6);
    Print_List(p_head);
    Delete_element(p_head,4);
    Print_List(p_head);
    Find_List(p_head,5);
    Delete_List(p_head);
    return 0;
}

小结

代码很简单，手撸双向链表，链表的知识应该是数据结构中最基础的，学习内核知识，链表也是绕不开的弯，如果从事嵌入式行业，这更是基础，会一直与指针打交道，下次有时间手撸一个栈，今天的内容就分享到这了。

以上代码已测试，如有错误欢迎指正。

欢迎关注 #公众号：技术乱舞一起交流

灵魂碰撞

C

6 引用
技术

115 引用
笔记

22 引用

艾恩凝(Nick) 3 年前 via Mac OS 大连位置

2 点赞

0 关注

0 收藏

作者勋章

2 感谢

8 回帖

1.2K

登录参与讨论 ...

adlered • 3 年前

太硬核了

1 回复 0 0 0
G (Gakkiyomi) • 3 年前 via Mac OS

C语言大佬，跪了

1 回复 0 0 0
艾恩凝(Nick) (aeneag) • 3 年前 via Mac OS

就会个c

0 0 0
艾恩凝(Nick) (aeneag) • 3 年前 via Mac OS

赶不上社区主人

0 0 0
糖醋鱼 (tangcuyu) • 3 年前 via Android

学数据结构的时候，我也肝了c++版本的？（虽然我把c++当c用

1 回复 0 0 0
艾恩凝(Nick) (aeneag) • 3 年前 via Mac OS

说实话面向对象的语言现在不太会写代码了

0 0 0
王哒哒（006） (wangy) • 1 年前

别卷了

0 0 0
fisher man (fisher-man) • 1 年前

别挖了

0 0 0