数据结构之手撕链表（讲解➕源代码）-2-阿里云开发者社区

数据结构之手撕链表（讲解➕源代码）-2

2023-11-20 40

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 数据结构之手撕链表（讲解➕源代码）-2

6.带头双向循环链表的实现（接口实现代码）

6.1 带头双向循环链表的定义

typedef int LTDataType;
typedef struct ListNode
{
    struct ListNode* prev; //前驱
    LTDataType data;
    struct ListNode* next; //后继
}ListNode;

6.2 带头双向循环链表的初始化

ListNode* ListInit() //初始化链表
{
    ListNode *head = (ListNode*) malloc(sizeof (ListNode));
    if(head ==  NULL)
    {
        perror("初始化开辟空间失败");
        exit(-1);
    }
    head->data = -1;
    head->prev = head;
    head->next = head;
    return head;
}

6.3 带头双向循环链表的销毁

void ListDestory(ListNode* pHead) //销毁
{
    int len = ListSize(pHead) + 1;
    while (len--)
        ListPopFront(pHead);
}

6.4 带头双向循环链表的打印

void ListPrint(ListNode* phead) //打印
{
    assert(phead);
    ListNode *phead_next = phead->next;
    printf("phead <-> ");
    while(phead_next != phead)
    {
        printf("%d <-> ",phead_next->data);
        phead_next = phead_next->next;
    }
    printf("phead\n");
}

6.5 带头双向链表的增加节点

ListNode* BuyListNode(LTDataType x) //增加节点
{
    ListNode *newnode = (ListNode*) malloc(sizeof (ListNode));
    if(newnode == NULL)
    {
        perror("增加节点开辟空间失败");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    newnode->prev = NULL;
    return newnode;
}

6.6 带头双向循环链表的在pos之前插入

void ListInsert(ListNode* pos,LTDataType x)//在pos位置之前插入
{
    assert(pos);
    ListNode *newnode = BuyListNode(x);
    ListNode *pos_prev = pos->prev;
    pos_prev->next = newnode;
    newnode->prev = pos_prev;
    newnode->next = pos;
    pos->prev = newnode;
}

6.7 带头双向循环链表删除pos位置

void ListErase(ListNode* pos)//删除pos位置的节点
{
    assert(pos);
    ListNode *pos_next = pos->next;
    ListNode *pos_prev = pos->prev;
    pos_prev->next = pos_next;
    pos_next->prev = pos_prev;
    free(pos);
}

6.8 带头双向循环链表的尾插尾删

void ListPushBack(ListNode* phead,LTDataType x)//尾插
{
    assert(phead);
    ListInsert(phead,x);
}
void ListPopBack(ListNode* phead)//尾删
{
    assert(phead);
    ListErase(phead->prev);
}

6.9 带头双向循环链表的头插头删

void ListPushFront(ListNode* phead,LTDataType x)//头插
{
    assert(phead);
    ListInsert(phead->next,x);
}
void ListPopFront(ListNode* phead)//头删
{
    assert(phead);
    ListErase(phead->next);
}

6.10 带头双向循环链表的长度求解

int ListSize(ListNode* phead)//求链表的长度
{
    assert(phead);
    int len = 0;
    ListNode *phead_next = phead->next;
    while(phead != phead_next)
    {
        len++;
        phead_next = phead_next->next;
    }
    return len;
}

6.11 带头双向循环链表的寻找某一节点

ListNode*ListFind(ListNode* phead, LTDataType num)//寻找某一个节点
{
    assert(phead);
    ListNode *find = phead->next;
    while(find != phead)
    {
        if(find->data == num)
        {
            return find;
        }
        find = find->next;
    }
    return NULL;
}

7. 顺序表和链表的区别

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑一定连续，物理不一定

任意位置插入或者删除

元素

需要覆盖数据

通过指针就能找到

插入

动态顺序表需要扩容

没有容量概念，需要一个给一个

缓存利用率

高

低