【数据结构】双向链表-蒲公英云

1.LinkedList.h

#ifndef LINKED_LIST_H
#define LINKED_LIST_H
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
//首先定义一个链表节点结构体
typedef struct LINKNODE{
    void* data;//表示节点中存储任意类型的数据
    struct LINKNODE* pre;//注意这种定义的方式啊
    struct LINKNODE* next;//注意这种定义的方式啊，前面是struct 后面是LINKNODE是最开始定义的结构体名称，LinkNode是另外定义的名称
}LinkNode;
//再定义链表结构体
typedef struct {
        //注意，下面的LinkNode可以不是指针就是LinkNode head,改成不是指针后可能还方便点，
        //如果head不是指针至少在初始化list的时候不用新开辟一片内存，同样也是作为头节点， 
        //而不是数据存储的第一个点，读者可以自行尝试把下面的指针改为不是指针
    LinkNode* head;//给链表定义一个头
    int size;//记录当前list存储的元素数量
}LinkList;
//打印函数指针
typedef void(*PRINTLINKNODE)(void*);
//初始化链表
LinkList* initLinkList();
//指定位置插入
void insertLinkList(LinkList* list, int pos, void* data);
//删除指定位置的值
void removeByPosLinkList(LinkList* list, int pos);
//获得链表的长度
int getLinkListSize(LinkList* list);
//查找
int findPosByData(LinkList* list, void* data);
//返回第一个结点
void* frontLinkList(LinkList* list);
//返回最后一个结点
void* backLinkList(LinkList* list);
//打印链表结点
void printLinkList(LinkList* list, PRINTLINKNODE print);
//释放链表内存
void freeSpaceLinkList(LinkList* list);
//从后面加入
void pushBack(LinkList* list, void* data);
//从后面弹出
void popBack(LinkList* list);
//从前面加入
void pushFront(LinkList* list, void* data);
//从前面弹出
void popFront(LinkList* list);
#endif // !LINKED_LIST_H

2.LinkedList.c

#include "LinkedList.h"
//初始化链表
LinkList* initLinkList() {
    LinkList* linkList = (LinkList*)malloc(sizeof(LinkList));
    //新建个数据节点,让list指向这个节点，这个节点作为list的头节点，不存储数据，只用next记录下真实的存储的第一个位置
    //这样做的目的是为了便于遍历
    linkList->head= (LinkNode*)malloc(sizeof(LinkNode));
    linkList->head->data = NULL;
    linkList->head->pre = NULL;
    linkList->head->next = NULL;
    linkList->size = 0;
    return linkList;
}
//指定位置插入
void insertLinkList(LinkList* list, int pos, void* data) {
    if (list == NULL) {
        return;
    }
    if (data == NULL) {
        return;
    }
    if (pos < 0 || pos >= list->size) {
        pos = list->size;
    }
    //创建新的结点
    LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));
    newNode->data = data;
    newNode->next = NULL;
    //辅助指针
    LinkNode* pCurrent = list->head;
    for (int i = 0; i < pos; i++) {
        pCurrent = pCurrent->next;
    }
    //将新节点加入链表
    newNode->pre = pCurrent;
    newNode->next = pCurrent->next;
    pCurrent->next = newNode;
    list->size++;
}
//删除指定位置的值
void removeByPosLinkList(LinkList* list, int pos) {
    if (list == NULL) {
        return;
    }
    if (pos < 0 || pos >= list->size) {
        return;
    }
    //辅助指针
    LinkNode* pCurrent = list->head;
    for (int i = 0; i < pos; i++) {
        pCurrent = pCurrent->next;
    }
    //缓存删除的节点
    LinkNode* pDel = pCurrent->next;
    pCurrent->next = pDel->next;
    //释放删除节点的内存
    free(pDel);
    list->size--;
}
//获得链表的长度
int getLinkListSize(LinkList* list) {
    return list->size;
}
//查找
int findPosByData(LinkList* list, void* data) {
    if (list == NULL) return -10086;
    if (data == NULL) return -10086;
    LinkNode* firstNode = list->head->next;
    int pos = 0;
    while (firstNode!= NULL) {
        if (firstNode->data == data) {
            return pos;
        }
        firstNode = firstNode->next;
        pos++;
    }
    return -10086;//表示没有找到
}
//返回第一个结点
void* frontLinkList(LinkList* list) {
    if (list == NULL) return NULL;
    return list->head->next->data;
}
//返回最后一个结点
void* backLinkList(LinkList* list) {
    if (list == NULL) return NULL;
    LinkNode* pCurrent = list->head;
    for (int i = 0; i < list->size; i++) {
        pCurrent = pCurrent->next;
    }
    return pCurrent->data;
}
//打印链表结点
void printLinkList(LinkList* list, PRINTLINKNODE print) {
    if (list == NULL) return;
    //辅助指针变量
    LinkNode* pCurrent = list->head->next;
    while (pCurrent != NULL) {
        print(pCurrent->data);
        pCurrent = pCurrent->next;
    }
}
//释放链表内存
void freeSpaceLinkList(LinkList* list){
    if (list == NULL) {
        return;
    }
    //辅助指针变量
    LinkNode* pCurrent = list->head;
    while (pCurrent != NULL) {
        //缓存下一个结点
        LinkNode* pNext = pCurrent->next;
        free(pCurrent);
        pCurrent = pNext;
    }
    //释放链表内存
    list->size = 0;
    free(list);
}
//从后面加入
void pushBack(LinkList* list, void* data) {
    if (list == NULL) {
        return;
    }
    if (data == NULL) {
        return;
    }
    insertLinkList(list, list->size, data);
}
//从后面弹出
void popBack(LinkList* list) {
    if (list == NULL) return;
    //获得最后一个指针
    LinkNode* pCurrent = list->head;
    while (pCurrent->next != NULL) {
        pCurrent = pCurrent->next;
    }
    //把最后一个的前一个的指针的next指向NULL
    pCurrent->pre->next = NULL;
    //释放掉最后一个指针
    free(pCurrent);
    list->size--;
}
//从前面加入
void pushFront(LinkList* list, void* data) {
    if (list == NULL) {
        return;
    }
    if (data == NULL) {
        return;
    }
    insertLinkList(list, 0, data);
}
//从前面弹出
void popFront(LinkList* list) {
    if (list == NULL) return;
    if (list->size == 0) return;
    //先保存第一个阶段的的指针
    LinkNode* firstNode = list->head->next;
    //再将头指针的下一个指针指向第一个的下一个
    list->head->next = firstNode->next;
    //再将第二个的pre设置为头指针
    firstNode->next->pre = list->head;
    //最后释放第一个指针
    free(firstNode);
    //size减小一个
    list->size--;
}

3.测试

#include "LinkedList.h"
//自定义数据类型
typedef struct PERSON {
    char name[64];
    int age;
    int score;
}Person;
//打印函数
void MyPrint(void* data) {
    Person* p = (Person*)data;
    printf("Name:%s Age:%d Score:%d\n", p->name, p->age, p->score);
}
void test01() {
    LinkList* list = initLinkList();
    Person p1 = { "xiaodong",20,56 };
    Person p2 = { "xiaoxiao",30,78 };
    Person p3 = { "dogndong",20,22 };
    Person p4 = { "kankan",46,13 };
    Person p5 = { "hehe",62,34 };
    Person p6 = { "lishang",67,55 };
    printf("size:%d\n", getLinkListSize(list));
    pushBack(list, &p1);
    printf("size:%d\n", getLinkListSize(list));
    pushBack(list, &p2);
    pushBack(list, &p3);
    pushBack(list, &p4);
    pushBack(list, &p5);
    pushFront(list, &p6);
    printLinkList(list, MyPrint);
    printf("size:%d\n", getLinkListSize(list));
    printf("-----------从后面弹出----------\n");
    popBack(list);
    printLinkList(list, MyPrint);
    printf("size:%d\n", getLinkListSize(list));
    printf("-----------从前面弹出----------\n");
    popFront(list);
    printLinkList(list, MyPrint);
    printf("size:%d\n", getLinkListSize(list));
    printf("-----------返回第一个节点数据----------\n");
    MyPrint(frontLinkList(list));
    printf("-----------返回最后一个节点数据----------\n");
    MyPrint(backLinkList(list));
}
int main(void) {
    test01();
    system("pause");
    return 0;
}