C++ 双链表的 创建、链接、删除

#include <stdio.h>
#include <stdlib.h>

//定义一个双链表节点
 struct Node
{
    int date; //数据
    Node* next; //下个数据
    Node* last; //上个数据
};

//定义list存放node指针
 struct List
{
    int size; //存放node节点的大小
    Node* head; //指针指向头节点
    Node* tail; //指针指向尾节点

};

//初始化双链表节点
 Node* init_node(int x)
{
    Node* temp= (Node*)malloc(sizeof(Node));
    temp->date = x;
    temp->next = temp->last = NULL;
    return temp;
}

//初始化双链表
List* init_list()
{
    List* temp = (List*)malloc(sizeof(List));
    temp->head = NULL;
    temp->tail = NULL;
    temp->size = 0;
    return temp;
}

//节点的链接传参，第一个参数数据在前，第二个参数数据在后
void  link_node(Node* n1, Node* n2)
{
    n1->next = n2;
    n2->last = n1;
}


//双链表链接
List* push_head(List* list, Node* n1)
{
    if (list->size == 0)
    {
        list->head = n1;    //双链表第一次添加节点时，此时双链表中只有一个元素，list的头指针和尾指针都指向一个链表，
        list->tail = list->head;
        list->size=1;
    }
    else
    {
        link_node(n1, list->head); 
        list->head = n1;
        list->size++;
    }
    return list;
}

//从头开始双链表
void list_head_printf(List* list)
{
    if (list->head == NULL)
    {
        printf("双链表为空!\n");
        return;
    }
    else
    {
        printf("双链表输出从头部开始输出：");

        for (Node *temp = list->head; temp != NULL; temp = temp->next)
        {
            printf("%d", temp->date);
            if (temp == list->tail)
                printf("\n");
            else
                printf(" ");
        }
    }
}


void push_end(List* data,Node*temp1 ) //双链表尾插
{
    List* temp = data;
    if (temp->head == NULL)
    {
        temp->head = temp1;
        temp->tail = temp->head;
        temp->size = 1;
        return ;
    }
    else
    {
        link_node(temp->tail, temp1);
        temp1->last = temp->tail;  //将temp1的前驱挂在尾节点上，
        temp->tail = temp1;        //尾节点的值现在指向temp1
        temp->size++;
        return ;
    }

}


void del_node(List* list, int num)  //双链表删除某个位置的节点 传参:1.双链表节点，2，需要删除的位置
{
    Node* tt = (Node*)malloc(sizeof(Node)); //动态申请一个结构体指针用于free对象
    if (list->head == NULL) //若双链表为空则直接返回
    {
        printf("双链表为空!\n");
        return;
    }
    if (list->size < num) //判断查找的位置是否和空间大小范围内
    {
        printf("双链表不存在该位置!\n");
        return ;
    }
    if (list->size == 1) //判断删除双链表节点时，双链表只有1个节点
    {
        tt = list->head;
        free(tt);
        list->head = list->tail = NULL;
        list->size = 0;
        return;
    }
    if (list->size == 2) //判断删除双链表节点时，双链表只有2个节点
    {
        Node* temp = (Node*)malloc(sizeof(Node));
        temp = list->tail;
        free(temp);
        list->head->next = NULL;
        list->tail = list->head;
        list->size--;
        return;
    }
    if (list->size > 2) //判断删除双链表节点时，双链表只有2个以上个节点
    {
        int n = 1;    
        for (Node* temp = list->head; temp->next != NULL; temp = temp->next) //循环遍历双链表节点
        {
            if (n == num)  //找到当前需要删除的节点
            {
                if (temp->next == NULL) //判断要删除的节点位置是否是在最后，
                {
                    tt = temp;
                    temp = temp->last;
                    list->tail = temp;
                    free(tt);
                    list->size--;
                    return ;
                }
                else   
                {
                    tt = temp;
                    link_node(temp->last, temp->next);
                    free(tt);
                    list->size--;
                    return;
                }                
            }
            n++;
        }
    }
}


int main()
{
    List* list = init_list();
    Node* temp1 = init_node(1);
    Node* temp2 = init_node(2);
    Node* temp3 = init_node(3);
    push_head(list, temp1);
    push_head(list, temp2);
    push_head(list, temp3);
    printf("当前双链表中的内容\n");
    list_head_printf(list);
    printf("即将删除位置2的双链表\n");
    del_node(list, 2);
    list_head_printf(list);
    return 0;
}

原文链接: https://www.cnblogs.com/shenji/p/12549150.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍