双向链表的介绍及相关的代码

双向链表

特性

逻辑结构：线性结构

存储结构：链式结构

操作：增删改查

代码

结构体

int len = 0;        //定义一个全局变量，来保存长度
typedef struct ListNade
{
    struct ListNade *prev;    //头指针
    struct ListNade *next;    //尾指针
    int data;                 //存储数据
} LTNode;

初始化

LTNode *LTInit()
{
    LTNode *p = (LTNode *)malloc(sizeof(LTNode));    //开辟空间
    if (p == NULL)                                   //容错判断
    {
        perror("LTNode malloc err");                 //错误提示
        return NULL;
    }
    p->prev = NULL;                                  //头指针指向空
    p->next = NULL;                                  //尾指针指向空
    return p;                                        //返回开辟的指针
}

插入

        头插

LTNode *tinsertIntoDoubleLinkList(LTNode *p, int data)
{
    LTNode *q = (LTNode *)malloc(sizeof(LTNode));   //开辟一个空间
    if (q == NULL)                                  //容错判断  
    {
        perror("LTNode malloc err");
        return NULL;
    }
    q->data = data;                                 //把数据赋值给开辟空间的数据        
    q->prev = p->prev;                              //头结点的头指针赋值给新开辟空间的头指针
    q->next = p;                                    //新开辟空间的尾指针指向头结点
    p->prev = q;                                    //头节点的头指针指向新开辟的地址
    len++;                                          //长度加1
    return q;                                       //返回新开辟的节点地址
}

        尾插入

LTNode *winsertIntoDoubleLinkList(LTNode *p, int data)
{
    LTNode *q = (LTNode *)malloc(sizeof(LTNode)); // 开辟一个空间
    if (q == NULL)                                // 容错判断
    {
        perror("LTNode malloc err");
        return NULL;
    }
    while (p->next != NULL) // 判断当前节点后面是否还有
    {
        p = p->next; // 将头节点往后移动
    }
    q->data = data;    // 将数据赋值给新开辟的节点
    q->next = p->next; // 将新开辟的尾指针指向头结点的指向的地址
    q->prev = p;       // 将新开辟的头指针指向头结点
    p->next = q;       // 头结点的尾指针指向新开辟的节点地址
    len++;
    return q;
}

遍历

        从头开始遍历

void tshowDoubleLinkList(LTNode *p)
{
    while (p->next != NULL)       //p判断当前节点后面是否还有
    {
        p = p->next;              //打印当前节点的数据
        printf("%d", p->data);    //将当前的节点往后移动
    }
    printf("\n");                 //执行完成后换行
}

        从尾节点开始遍历

void wshowDoubleLinkList(LTNode *p)
{
    while (p->prev!=NULL)         //p判断当前节点后面是否还有
    {
        printf("%d", p->data);    //打印当前节点的数据
        p = p->prev;              //将当前的节点往前移动
    }
    printf("\n");                //执行完成后换行
}

删除指定位置

LTNode *deletePostDoubleLinkList(LTNode *p, LTNode *w, int n)
{
    LTNode *pdel = NULL;     // 定义一个LTNode类型的空指针
    int i = 0;               // 循环次数
    if (n < ((len - 1) / 2)) // 判断删除的位置是否小于链表的长度一半
    {
        while (i < n) // 将头结点移动要删除位置的前面
        {
            p = p->next; // 移动头结点
            i++;         // 统计循环字数
        }
        pdel = p->next;          // 将要删除的指针的地址赋值给pdel
        p->next->next->prev = p; // 把将要删除的节点后面的节点头指针指向当前的节点
        p->next = p->next->next; // 把当前的节点的尾指针指向删除节点的后一节点
        free(pdel);              // 释放要删除的节点
        len--;                   // 长度减一
    }
    else if (n >= (len) / 2) // 判断删除的位置是否大于等于链表的长度一半
    {
        if (n == len - 1) // 若要删除的位置等于长度减一
        {
            pdel = w;             // 把链表的尾指针的地址赋值给Pdel
            w->prev->next = NULL; // 链表的尾节点的前一个节点的尾指针等于NULL
            w = pdel->prev;       // 链表的尾节点往前移动
            free(pdel);           // 释放原链表的尾节点
            len--;                // 长度减一
            return w;
        }
        else//若若要删除的位置大于链表长度的一半
        {
            i = len;//将长度的大小赋值给i
            LTNode *t = w;//创建一个 LTNode类型的指针并把链表的尾节点的地址赋值给他
            while (i != n)//i不等于要删除的位置
            {
                t = t->prev;//将虚拟的尾节点的地址往前移动
                i--;
            }
            t->next->prev = t->prev;//将虚拟的尾节点的后一个节点的头指针指向当前节点的头指针
            t->prev->next = t->next;//将虚拟的尾节点的前一个节点的尾指针指向当前节点的尾指针
            free(t);//释放当前的节点
            len--;//长度减一
            return w;//返回实际尾地址
        }
    }
}

全部代码

#include <stdio.h>
#include <stdlib.h>
int len = 0;
typedef struct ListNade
{
    struct ListNade *prev;
    struct ListNade *next;
    int data;
} LTNode;
LTNode *LTInit()
{
    LTNode *p = (LTNode *)malloc(sizeof(LTNode));
    if (p == NULL)
    {
        perror("LTNode malloc err");
        return NULL;
    }
    p->prev = NULL;
    p->next = NULL;
    return p;
}
LTNode *tinsertIntoDoubleLinkList(LTNode *p, int i);
LTNode *winsertIntoDoubleLinkList(LTNode *p, int i);
void wshowDoubleLinkList(LTNode *p);
void tshowDoubleLinkList(LTNode *p);
LTNode *deletePostDoubleLinkList(LTNode *p, LTNode *q, int n);
void charu(LTNode *p, LTNode *w, int n, int data);
void xiugai(LTNode *p, LTNode *q, int n, int data);
void delZD(LTNode *p, LTNode *q, int data);

int main()
{
    LTNode *l = LTInit();
    LTNode *w = NULL;
    for (int i = 1; i <= 5; i++)
    {
        w = wBuyLTNode(l, i);
    }
    tbianli(l);
    w = deletePostDoubleLinkList(l, w, 3);
    wbianli(w);
    charu(l, w, 2, 3);
    wbianli(w);
    xiugai(l, w, 2, 2);
    wbianli(w);
    delZD(l, w, 2);
    wbianli(w);
}
// 尾插
LTNode *winsertIntoDoubleLinkList(LTNode *p, int data)
{
    LTNode *q = (LTNode *)malloc(sizeof(LTNode)); // 开辟一个空间
    if (q == NULL)                                // 容错判断
    {
        perror("LTNode malloc err");
        return NULL;
    }
    while (p->next != NULL) // 判断当前节点后面是否还有
    {
        p = p->next; // 将头节点往后移动
    }
    q->data = data;    // 将数据赋值给新开辟的节点
    q->next = p->next; // 将新开辟的尾指针指向头结点的指向的地址
    q->prev = p;       // 将新开辟的头指针指向头结点
    p->next = q;       // 头结点的尾指针指向新开辟的节点地址
    len++;
    return q;
}
// 头插
LTNode *tinsertIntoDoubleLinkList(LTNode *p, int data)
{
    LTNode *q = (LTNode *)malloc(sizeof(LTNode)); // 开辟一个空间
    if (q == NULL)                                // 容错判断
    {
        perror("LTNode malloc err");
        return NULL;
    }
    q->data = data;    // 把数据赋值给开辟空间的数据
    q->prev = p->prev; // 头结点的头指针赋值给新开辟空间的头指针
    q->next = p;       // 新开辟空间的尾指针指向头结点
    p->prev = q;       // 头节点的头指针指向新开辟的地址
    len++;             // 长度加1
    return q;          // 返回新开辟的节点地址
}
// 尾遍历
void wshowDoubleLinkList(LTNode *p)
{
    while (p->prev != NULL)
    {
        printf("%d", p->data);
        p = p->prev;
    }
    printf("\n");
}
// 头遍历
void tshowDoubleLinkList(LTNode *p)
{
    while (p->next != NULL) // p判断当前节点后面是否还有
    {
        p = p->next;           // 打印当前节点的数据
        printf("%d", p->data); // 将当前的节点往后移动
    }
    printf("\n"); // 执行完成后换行
}
// 删除指定位置
LTNode *deletePostDoubleLinkList(LTNode *p, LTNode *w, int n)
{
    LTNode *pdel = NULL;     // 定义一个LTNode类型的空指针
    int i = 0;               // 循环次数
    if (n < ((len - 1) / 2)) // 判断删除的位置是否小于链表的长度一半
    {
        while (i < n) // 将头结点移动要删除位置的前面
        {
            p = p->next; // 移动头结点
            i++;         // 统计循环字数
        }
        pdel = p->next;          // 将要删除的指针的地址赋值给pdel
        p->next->next->prev = p; // 把将要删除的节点后面的节点头指针指向当前的节点
        p->next = p->next->next; // 把当前的节点的尾指针指向删除节点的后一节点
        free(pdel);              // 释放要删除的节点
        len--;                   // 长度减一
    }
    else if (n >= (len) / 2) // 判断删除的位置是否大于等于链表的长度一半
    {
        if (n == len - 1) // 若要删除的位置等于长度减一
        {
            pdel = w;             // 把链表的尾指针的地址赋值给Pdel
            w->prev->next = NULL; // 链表的尾节点的前一个节点的尾指针等于NULL
            w = pdel->prev;       // 链表的尾节点往前移动
            free(pdel);           // 释放原链表的尾节点
            len--;                // 长度减一
            return w;
        }
        else//若若要删除的位置大于链表长度的一半
        {
            i = len;//将长度的大小赋值给i
            LTNode *t = w;//创建一个 LTNode类型的指针并把链表的尾节点的地址赋值给他
            while (i != n)//i不等于要删除的位置
            {
                t = t->prev;//将虚拟的尾节点的地址往前移动
                i--;
            }
            t->next->prev = t->prev;//将虚拟的尾节点的后一个节点的头指针指向当前节点的头指针
            t->prev->next = t->next;//将虚拟的尾节点的前一个节点的尾指针指向当前节点的尾指针
            free(t);//释放当前的节点
            len--;//长度减一
            return w;//返回实际尾地址
        }
    }
}
// 判断为空 1为空 0不为空
int empty(LTNode *p)
{
    if (len == 0)
    {
        return 1;
    }
    return 0;
}
// 查找指定数据
int chazhao(LTNode *p, int data)
{
    int i = 0;
    while (p->next != NULL)
    {
        p = p->next;
        if (p->data == data)
        {
            return i = 0;
        }
        i++;
    }
    return -1;
}
// 插入指定数据
void charu(LTNode *p, LTNode *w, int n, int data)
{
    int i = 0;
    if (n < ((len - 1) / 2))
    {
        while (i < n)
        {
            p = p->next;
            i++;
        }
        LTNode *q = (LTNode *)malloc(sizeof(LTNode));
        q->next = p->next;
        p->next = q;
        p->next->prev = q;
        q->prev = p;
        q->data = data;
        len++;
    }
    else
    {
        i = len;
        while (i != n)
        {
            w = w->prev;
            i--;
        }
        LTNode *q = (LTNode *)malloc(sizeof(LTNode));
        q->next = w;
        q->prev = w->prev;
        w->prev->next = q;
        w->prev = q;
        len++;
    }
}
// 修改指定位置数值
void xiugai(LTNode *p, LTNode *q, int n, int data)
{
    int i = 0;
    if (n < ((len - 1) / 2))
    {
        while (i < n)
        {
            p = p->next;
            i++;
        }
        p->data = data;
    }
    else
    {
        i = len;
        while (i != n)
        {
            q = q->prev;
            i--;
        }
        q->data = data;
    }
}
void delZD(LTNode *p, LTNode *q, int data)
{
    LTNode *pdel = NULL;
    int i = 1;
    while (p->next != NULL)
    {
        if (p->next->data == data)
        {
            if (i == len)
            {
                q->prev->next = NULL;
                pdel = q->prev;
                free(q);
                len--;
            }
            else
            {
                pdel = p->next;
                p->next = p->next->next;
                pdel->next->prev = p;
                free(pdel);
                len--;
            }
        }
        else
        {
            p = p->next;
            i++;
        }
    }
}