美文网首页
双向链表&双向循环链表

双向链表&双向循环链表

作者: AlexChou | 来源:发表于2020-09-22 09:46 被阅读0次

1. 双向链表

1.1 结构与初始化

双向链表
  • 单向链表只能找到后驱。
  • 双向链表能轻松地获取前驱和后继。
  • 插入时，不管是单向还是双向，都需要先找对应位置的前驱。
  • 删除时，由于双向链表可以访问前驱和后继，就不需要先找对应位置的前驱。
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define NOT_FOUND -1

/* ElemType类型根据实际情况而定，这里假设为int */
typedef int ElemType;
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;

/*线性结构使用顺序表的方式存储*/

//链表结构设计
typedef struct Node {
    struct Node *prior;
    ElemType data;
    struct Node *next;
} Node, *LinkList;

Status InitList(LinkList *L)
{
    //产生头结点，并使用L指向此头结点
    *L = (LinkList)malloc(sizeof(Node));
    //存储空间分配失败
    if (*L == NULL) return ERROR;
    //将头结点的指针域置空
    (*L)->prior = NULL;
    (*L)->next = NULL;
    return OK;
}

1.2 遍历

Status ListTraverse(LinkList L)
{
    if (L == NULL) return ERROR; // 空表
    LinkList p = L->next; // 跳过头结点
    while (p) {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}

1.3 插入

插入节点

插入时，需要前一个节点来找到后一个节点。

Status ListInsert(LinkList *L, int loc, ElemType elem)
{
    if (*L == NULL) return ERROR; // 空表
    LinkList p, q;
    p = *L;
    int i = 1;
    for (; p && i < loc; p = p->next, i++); // 找到idx位置
    if(!p || i > loc) return ERROR; // 第idx个元素不存在
    q = (LinkList)malloc(sizeof(Node));
    if (!q) return ERROR; // 没创建出来报错
    q->data = elem;
    q->next = p->next; // q的后继指向p的后继，p-next可能为NULL，q->next也不用显式赋值NULL
    p->next = q; // p的后继指向q
    if (q->next) q->next->prior = q; // q的后继的前驱指向q，最后可能为NULL
    q->prior = p; // q的前驱指向p
    return OK;
}

1.4 删除

删除节点

找到被删除节点，让前后牵手就行了。

Status ListDeleteLoc(LinkList *L, int loc, ElemType *elem)
{
    if (*L == NULL) return ERROR; // 空表
    LinkList p = (*L)->next;
    int i = 1;
    for (; p && i < loc; p = p->next, i++); // 找到idx位置
    if(!p || i > loc) return ERROR; // 第idx个元素不存在
    p->prior->next = p->next; // p的前驱的后继指向p的后继
    if (p->next) p->next->prior = p->prior; // p的后继的前驱指向p的前驱，最后可能为NULL
    *elem = p->data;
    free(p); // 释放被删除节点
    return OK;
}

1.5 删除指定元素

Status ListDeleteElem(LinkList *L, ElemType elem)
{
    if (*L == NULL) return ERROR; // 空表
    LinkList p = (*L)->next;
    while (p && p->data != elem) p = p->next; // 找到对应元素
    if(!p) return ERROR; // 元素elem不存在
    p->prior->next = p->next; // 将p的前驱指向p的后继
    if (p->next) p->next->prior = p->prior; // 将p的后继指向p的前驱，最后可能为NULL
    free(p); // 释放被删除节点
    return OK;
}

1.6 更新指定位置

Status ListUpdateElem(LinkList L, int loc, ElemType elem)
{
    if (L == NULL) return ERROR; // 空表
    LinkList p = L->next;
    int i = 1;
    for (; p && i < loc; p = p->next, i++); // 找到idx位置
    if(!p || i > loc) return ERROR; // 第idx个元素不存在
    p->data = elem;
    return OK;
}

2. 循环双向链表

2.1 结构与初始化

线性双向链表 循环双向链表

循环双向链表的创建实际就是双向链表的尾节点后驱指向头结点，头结点前驱指向尾节点，最终形成一个环。

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define NOT_FOUND -1

/* ElemType类型根据实际情况而定，这里假设为int */
typedef int ElemType;
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;

/*线性结构使用顺序表的方式存储*/

//链表结构设计
typedef struct Node {
    struct Node *prior;
    ElemType data;
    struct Node *next;
} Node, *LinkList;

Status InitList(LinkList *L, ElemType elem)
{
    //产生头结点，并使用L指向此头结点
    *L = (LinkList)malloc(sizeof(Node));
    //存储空间分配失败
    if (*L == NULL) return ERROR;
    //将头结点的指针指向自己
    (*L)->prior = *L;
    (*L)->next = *L;
    (*L)->data = elem;
    return OK;
}

依次输入创建双向循环链表：

Status CreateList2(LinkList *L) {
    ElemType elem;
    LinkList tail = NULL;
    while (1) {
        scanf("%d", &elem); // 输入数据
        if (elem == 0) break; // 输入0时结束
        if (*L == NULL) { // 表是空的时候
            *L = (LinkList)malloc(sizeof(Node)); // 创建表头
            if (*L == NULL) return ERROR; // 没创建出来报错
            (*L)->data = elem; // 存入数据
            tail = *L; // 尾节点，方便后续添加
        } else { // 表不为空
            tail->next = (LinkList)malloc(sizeof(Node)); // 创建新节点
            if (!tail->next) return ERROR; // 没创建出来报错
            tail->next->data = elem; // 存入数据
            tail->next->prior = tail;
            tail = tail->next; // 之前的尾节点指向新节点
        }
    }
    tail->next = *L; // 形成环
    (*L)->prior = tail;
    return OK;
}

2.1 正向遍历

Status ListTraverse(LinkList L)
{
    LinkList p = L; // 从自己开始
    do {
        printf("%d ",p->data);
        p = p->next;
    } while (p != L); // 到自己的时候停止
    printf("\n");
    return OK;
}

2.2 反向遍历

Status ListTraverseBackwards(LinkList L)
{
    LinkList p = L->prior;
    do {
        printf("%d ",p->data);
        p = p->prior;
    } while (p != L->prior);
    printf("\n");
    return OK;
}

2.3 插入

插入节点

插入时，不管是单向还是双向，都需要先找对应位置的前驱。

Status ListInsert(LinkList *L, int loc, ElemType elem)
{
    if (*L == NULL || loc < 1) return ERROR; // 空表，位置非法
    LinkList tmp = (LinkList)malloc(sizeof(Node)); // 创建新节点
    if (!tmp) return ERROR; // 没创建出来报错
    tmp->data = elem; // 存入数据
    LinkList target = *L; // 不管loc是多少，都是从头开始找
    if (loc == 1) {
        for (; target->next != *L; target = target->next); // 找到头结点的前一个节点(尾节点)
        *L = tmp; // 头结点变为新节点
    } else {
        int idx = 1;
        for (; target->next != *L && idx < loc - 1; target = target->next, ++idx); // 找到loc结点的前一个节点
        if (target->next == *L || idx > loc - 1) return ERROR; // 找了一圈了，还没到指定位置，越界
    }
    tmp->next = target->next; // 新节点的后驱指向前一个节点的后驱
    target->next = tmp; // 前一个节点指向新节点
    tmp->next->prior = tmp; // 新节点后继的前驱指向新节点
    tmp->prior = target; // 新节点的前驱指向前一个节点
    return OK;
}

2.4 删除

删除节点

删除时，由于双向链表可以访问前驱和后继，就不需要先找对应位置的前驱。

Status ListDeleteLoc(LinkList *L, int loc, ElemType *elem)
{
    if (*L == NULL || loc < 1) return ERROR; // 空表，位置非法
    LinkList target = *L; // 不管loc是多少，都是从头开始找
    if (loc == 1) {
        if ((*L)->next == *L) { // 如果只有1个节点
            free(*L);
            *L = NULL;
            return OK;
        };
        *L = (*L)->next; // 头节点变为尾节点的下一个节点
    } else {
        int idx = 1;
        for (; target->next != *L && idx < loc; target = target->next, ++idx); // 找到loc节点
        if (target->next == *L || idx > loc) return ERROR; // 找了一圈了，还没到指定位置，越界
    }
    target->prior->next = target->next; // target的前驱指向target的后继
    target->next->prior = target->prior; // 将target的后继的前驱指向target的前驱
    *elem = target->data;
    free(target); // 释放被删除节点
    return OK;
}

2.5 删除指定元素

Status ListDeleteElem(LinkList *L, ElemType elem)
{
    if (*L == NULL) return ERROR; // 空表
    LinkList target = *L; // 都是从头开始找
    for (; target->next != *L && target->data != elem; target = target->next); // 找到elem元素所在节点
    if (target->next == *L && target->data != elem) return ERROR; // 找了一圈了，没有找到
    if (target->next == target->prior) { // 前驱和后继相等，说明只有一个节点
        free(target);
        *L = NULL;
        return OK;
    }
    target->prior->next = target->next; // target的前驱指向target的后继
    target->next->prior = target->prior; // 将target的后继的前驱指向target的前驱
    if (*L == target) *L = (*L)->next; // 如果是头节点，移动为下一个
    free(target); // 释放被删除节点
    return OK;
}

相关文章

  • 双向链表&双向循环链表

    链表分为：单链表、单向循环链表、双向链表、双向循环链表本节主要说明：双向链表、双向循环链表 定义结点 一、双向链表...

  • 0x05双向循环链表

    1 双向循环链表创建 2 双向循环链表插入元素 3 遍历双向循环链表 4双向循环链表删除结点

  • 双向链表

    双向链表的结构 既然单链表有循环链表，双向链表当然也有双向循环链表，如下图： 问： 双向链表中某个节点p的后继节点...

  • 线性表--链式存储结构--双向链表

    双向链表 一、双向链表结构 双向链表结点结构 既然单链表可以有循环链表，那么双向链表当然也可以有。 由于这是双向链...

  • 数据结构与算法之数组与链表

    线性表包括数组，链表（单链表，双向链表，循环链表，双向循环链表，静态链表），栈（顺序栈，链式栈），队列（普通队列，...

  • 链表

    链表 缺点：查找复杂有点：定点删除／插入元素 单链表 双向链表 循环链表 双向循环链表 数组与链表的区别 数据存储...

  • 数据结构与算法之栈与队列

    线性表包括数组，链表（单链表，双向链表，循环链表，双向循环链表，静态链表），栈（顺序栈，链式栈），队列（普通队列，...

  • 数据结构与算法04-双向链表以及双向循环链表

    一、双向链表 0、定义结点 1、创建双向链接 2、打印循环链表的元素 3、双向链表插入元素 4、删除双向链表指定位...

  • 如何设计一个内存缓存库

    双向链表 + LRU淘汰算法 + 线程安全 双向链表的设计 用OC来设计双向链表（不是循环链表） 单个节点 整个链...

  • 常见的数据结构

    常见的数据结构有： 数组 链表单链表、双向链表、循环链表、双向循环链表、静态链表 栈顺序栈、链式栈 队列普通队列、...

网友评论

      本文标题：双向链表&双向循环链表

      本文链接：https://www.haomeiwen.com/subject/rgrhyktx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|双向链表&双向循环链表|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！