精华内容
下载资源
问答
  • 单链表和双链表

    2020-05-04 11:33:26
    链表有两种类型:单链表和双链表。上面给出的例子是一个单链表,这里有一个双链表的例子: 一 简介 - 单链表 单链表中的每个结点不仅包含值,还包含链接到下一个结点的引用字段。通过这种方式,单链表将所有结点按...

    链表

    与数组相似,链表也是一种线性数据结构。这里有一个例子:

    img

    链表中的每个元素实际上是一个单独的对象,而所有对象都通过每个元素中的引用字段链接在一起。

    链表有两种类型:单链表和双链表。上面给出的例子是一个单链表,这里有一个双链表的例子:

    img

    一 简介 - 单链表

    单链表中的每个结点不仅包含,还包含链接到下一个结点的引用字段。通过这种方式,单链表将所有结点按顺序组织起来。

    1. 结点结构

    在大多数情况下,我们将使用头结点(第一个结点)来表示整个列表。

    // Definition for singly-linked list.
    struct SinglyListNode {
        int val;
        SinglyListNode *next;
        SinglyListNode(int x) : val(x), next(NULL) {}
    };
    

    2. 操作

    与数组不同,我们无法在常量时间内访问单链表中的随机元素。 如果我们想要获得第 i 个元素,我们必须从头结点逐个遍历。 我们按索引访问元素平均要花费 O(N)时间,其中 N 是链表的长度。

    例如,在上面的示例中,头结点是 23。访问第 3 个结点的唯一方法是使用头结点中的“next”字段到达第 2 个结点(结点 6); 然后使用结点 6 的“next”字段,我们能够访问第 3 个结点。

    你可能想知道为什么链表很有用,尽管它在通过索引访问数据时(与数组相比)具有如此糟糕的性能。 接下来,我们将介绍插入和删除操作,你将了解到链表的好处。

    2.1 添加操作 - 单链表

    如果我们想在给定的结点 prev 之后添加新值,我们应该:

    1. 使用给定值初始化新结点 cur;img
    2. cur的“next”字段链接到 prev 的下一个结点 nextimg
    3. prev 中的“next”字段链接到 curimg

    与数组不同,我们不需要将所有元素移动到插入元素之后。因此,您可以在 O(1) 时间复杂度中将新结点插入到链表中,这非常高效。

    示例

    img

    让我们在第二个结点 6 之后插入一个新的值 9。

    我们将首先初始化一个值为 9 的新结点。然后将结点 9 链接到结点 15。最后,将结点 6 链接到结点 9。

    插入之后,我们的链表将如下所示:

    img

    2.2 在开头添加结点

    众所周知,我们使用头结点来代表整个列表。

    因此,在列表开头添加新节点时更新头结点 head 至关重要。

    1. 初始化一个新结点 cur;
    2. 将新结点链接到我们的原始头结点 head
    3. cur 指定为 head

    例如,让我们在列表的开头添加一个新结点 9。

    1. 我们初始化一个新结点 9 并将其链接到当前头结点 23。img
    2. 指定结点 9 为新的头结点。 img
    2.3 删除操作 - 单链表

    如果我们想从单链表中删除现有结点 cur,可以分两步完成:

    1. 找到 cur 的上一个结点 prev 及其下一个结点 next;img
    2. 接下来链接 prev 到 cur 的下一个节点 next。img

    在我们的第一步中,我们需要找出 prevnext。使用 cur 的参考字段很容易找出 next,但是,我们必须从头结点遍历链表,以找出 prev,它的平均时间是 O(N),其中 N 是链表的长度。因此,删除结点的时间复杂度将是 O(N)

    空间复杂度为 O(1),因为我们只需要常量空间来存储指针。

    示例

    img

    让我们尝试把结点 6 从上面的单链表中删除。

    1. 从头遍历链表,直到我们找到前一个结点 prev,即结点 23
    2. prev(结点 23)与 next(结点 15)链接

    img

    结点 6 现在不在我们的单链表中。

    2.4 删除第一个结点

    如果我们想删除第一个结点,策略会有所不同。

    正如之前所提到的,我们使用头结点 head 来表示链表。我们的头是下面示例中的黑色结点 23。

    img
    如果想要删除第一个结点,可以简单地将下一个结点分配给 head。也就是说,删除之后我们的头将会是结点 6。

    img链表从头结点开始,因此结点 23 不再在我们的链表中。

    3. 链表中的双指针

    让我们从一个经典问题开始:

    给定一个链表,判断链表中是否有环。

    你可能已经使用哈希表提出了解决方案。但是,使用双指针技巧有一个更有效的解决方案。

    想象一下,有两个速度不同的跑步者。如果他们在直路上行驶,快跑者将首先到达目的地。但是,如果它们在圆形跑道上跑步,那么快跑者如果继续跑步就会追上慢跑者。

    这正是我们在链表中使用两个速度不同的指针时会遇到的情况:

    1. 如果没有环,快指针将停在链表的末尾。
    2. 如果有环,快指针最终将与慢指针相遇。

    所以剩下的问题是:

    这两个指针的适当速度应该是多少?

    一个安全的选择是每次移动慢指针一步,而移动快指针两步。每一次迭代,快速指针将额外移动一步。如果环的长度为 M,经过 M 次迭代后,快指针肯定会多绕环一周,并赶上慢指针。

    那其他选择呢?它们有用吗?它们会更高效吗?

    // Initialize slow & fast pointers
    ListNode* slow = head;
    ListNode* fast = head;
    /**
     * Change this condition to fit specific problem.
     * Attention: remember to avoid null-pointer error
     **/
    while (slow && fast && fast->next) {
        slow = slow->next;          // move slow pointer one step each time
        fast = fast->next->next;    // move fast pointer two steps each time
        if (slow == fast) {         // change this condition to fit specific problem
            return true;
        }
    }
    return false;   // change return value to fit specific problem
    

    提示

    它与我们在数组中学到的内容类似。但它可能更棘手而且更容易出错。你应该注意以下几点:

    1. 在调用 next 字段之前,始终检查节点是否为空。

    获取空节点的下一个节点将导致空指针错误。例如,在我们运行 fast = fast.next.next 之前,需要检查 fastfast.next 不为空。

    2. 仔细定义循环的结束条件。

    运行几个示例,以确保你的结束条件不会导致无限循环。在定义结束条件时,你必须考虑我们的第一点提示。

    复杂度分析

    空间复杂度分析容易。如果只使用指针,而不使用任何其他额外的空间,那么空间复杂度将是 O(1)。但是,时间复杂度的分析比较困难。为了得到答案,我们需要分析运行循环的次数

    在前面的查找循环示例中,假设我们每次移动较快的指针 2 步,每次移动较慢的指针 1 步。

    1. 如果没有循环,快指针需要 N/2 次才能到达链表的末尾,其中 N 是链表的长度。
    2. 如果存在循环,则快指针需要 M 次才能赶上慢指针,其中 M 是列表中循环的长度。

    显然,M <= N 。所以我们将循环运行 N 次。对于每次循环,我们只需要常量级的时间。因此,该算法的时间复杂度总共为 O(N)

    自己分析其他问题以提高分析能力。别忘了考虑不同的条件。如果很难对所有情况进行分析,考虑最糟糕的情况。

    4. 反转链表

    让我们从一个经典问题开始:

    反转一个单链表。

    一种解决方案是按原始顺序迭代结点,并将它们逐个移动到列表的头部。似乎很难理解。我们先用一个例子来说明我们的算法。

    算法概述

    让我们看一个例子:

    img

    请记住,黑色结点 23 是原始的头结点。

    1. 首先,我们将黑色结点的下一个结点(即结点 6)移动到列表的头部:

    img

    1. 然后,我们将黑色结点的下一个结点(即结点 15)移动到列表的头部:

    img

    1. 黑色结点的下一个结点现在是空。因此,我们停止这一过程并返回新的头结点 15。
    更多

    在该算法中,每个结点只移动一次

    因此,时间复杂度为 O(N),其中 N 是链表的长度。我们只使用常量级的额外空间,所以空间复杂度为 O(1)。

    二 简介 - 双链表

    单链接列表中的结点具有 Value 字段,以及用于顺序链接结点的“Next”引用字段。

    在本文中,我们将介绍另一种类型的链表:双链表

    1. 定义

    双链表以类似的方式工作,但还有一个引用字段,称为“prev”字段。有了这个额外的字段,您就能够知道当前结点的前一个结点。

    让我们看一个例子:

    img

    绿色箭头表示我们的“prev”字段是如何工作的。

    2. 结点结构

    下面是双链表中结点结构的典型定义:

    // Definition for doubly-linked list.
    struct DoublyListNode {
        int val;
        DoublyListNode *next, *prev;
        DoublyListNode(int x) : val(x), next(NULL), prev(NULL) {}
    };
    

    与单链接列表类似,我们将使用头结点来表示整个列表。

    3. 操作

    与单链表类似,我们将介绍在双链表中如何访问数据、插入新结点或删除现有结点。

    我们可以与单链表相同的方式访问数据:

    1. 我们不能在常量级的时间内访问随机位置
    2. 我们必须从头部遍历才能得到我们想要的第一个结点。
    3. 在最坏的情况下,时间复杂度将是 O(N),其中 N 是链表的长度。

    对于添加和删除,会稍微复杂一些,因为我们还需要处理“prev”字段。

    3.1 添加操作 - 双链表

    如果我们想在现有的结点 prev 之后插入一个新的结点 cur,我们可以将此过程分为两个步骤:

    1. 链接 curprevnext,其中 nextprev 原始的下一个节点;img
    2. cur 重新链接 prevnextimg

    与单链表类似,添加操作的时间和空间复杂度都是 O(1)

    示例

    img

    让我们在现有结点 6 之后添加一个新结点 9:

    1. 链接 cur(结点 9)与 prev(结点 6)和 next(结点 15)img
    2. cur(结点 9)重新链接 prev(结点 6)和 next(结点 15)img
    3.2 删除操作 - 双链表

    如果我们想从双链表中删除一个现有的结点 cur,我们可以简单地将它的前一个结点 prev 与下一个结点 next 链接起来。

    与单链表不同,使用“prev”字段可以很容易地在常量时间内获得前一个结点。

    因为我们不再需要遍历链表来获取前一个结点,所以时间和空间复杂度都是O(1)

    示例

    img

    我们的目标是从双链表中删除结点 6。

    因此,我们将它的前一个结点 23 和下一个结点 15 链接起来:img结点 6 现在不在我们的双链表中。

    三 小结 - 链表

    让我们简要回顾一下单链表和双链表的表现。

    它们在许多操作中是相似的。

    1. 它们都无法在常量时间内随机访问数据
    2. 它们都能够在 O(1) 时间内在给定结点之后或列表开头添加一个新结点
    3. 它们都能够在 O(1) 时间内删除第一个结点

    但是删除给定结点(包括最后一个结点)时略有不同。

    • 在单链表中,它无法获取给定结点的前一个结点,因此在删除给定结点之前我们必须花费 O(N) 时间来找出前一结点。
    • 在双链表中,这会更容易,因为我们可以使用“prev”引用字段获取前一个结点。因此我们可以在 O(1) 时间内删除给定结点。

    对照

    这里我们提供链表和其他数据结构(包括数组,队列和栈)之间时间复杂度的比较:img经过这次比较,我们不难得出结论:

    如果你需要经常添加或删除结点,链表可能是一个不错的选择。

    如果你需要经常按索引访问元素,数组可能是比链表更好的选择。

    展开全文
  • 单链表和双向链表

    2019-12-24 22:48:05
    单链表和双向链表 链表和数组的优缺点 **数组:** 优点:可以通过数组索引很快地访问数据元素,可以通过数组下标随机访问 缺点:删除和插入元素比较麻烦 **链表:** 优点:删除和插入元素方便快捷 缺点:只...

    单链表和双向链表

    链表和数组的优缺点

     **数组:**
     优点:可以通过数组索引很快地访问数据元素,可以通过数组下标随机访问
     缺点:删除和插入元素比较麻烦
     **链表:**
     优点:删除和插入元素方便快捷
     缺点:只能够顺序访问,不能够随机访问
    
     所以在需要可以随机访问元素的时候选择数组,而在需要经常删除和插入操作的时候
     使用链表。另外数据存放数据时需要知道元素的个数,但是链表能够动态进行存储分
     配。
    

    单向链表和双向链表的结构

    单向链表

    typedef struct single 
    {
      int data;
      struct single *next;
    }
    

    双向链表

    typedef struct double
    {
      int data;
      struct double *front;//前驱指针
      struct double *next;//后驱指针
    }
    

    单向链表操作(插入元素)//以后再添加删除操作

    下面我将用图、文字和代码一起解释单向链表的插入元素操作(暂时只解释了在中间插入
    元素操作,在末尾和开头插入元素也类似),因为用笔画比较快就用笔画了图,请勿介意。
    
    原本的链表如下图所示,我们需要做的就是在这两个元素间插入一个元素。
    

    在这里插入图片描述
    相关代码:

    head->next=NEXT;
    

    在插入元素后的图片

    在这里插入图片描述
    如图所示,插入元素需要做的就是将head->next指针释放出来,再将它指向新元素,新元素New->next指针指向NEXT。

    插入元素后的代码

    New->next=NEXT;
    head->next=New;
    

    双向链表操作(插入元素)//以后再添加删除操作

    下面将用图片、文字以及代码解释双向链表的插入元素操作

    下图是未插入元素前的图片,我们需要做的就是在这两个元素间插入一个元素。
    在这里插入图片描述
    此时的相关代码:

    head->next=NEXT;
    NEXT->pre=head;
    

    下图所示为插入元素后的图片
    在这里插入图片描述
    插入元素就是前一个元素的后驱指针head->next指向新元素,新元素的后驱指针New->next指向后一个元素,后一个的前驱指针NEXT->pre指向新元素,新元素的前驱指针New->pre指向前一个元素。

    插入元素后的代码

    head->next=New;
    New->next=NEXT;
    NEXT->pre=New;
    New->pre=head;
    
    展开全文
  • 单链表和双向链表的数据结构都包含指向下一个元素指针 next, 双向链表还包括指向上一个元素指针 previous 单链表只能向后遍历, 双向链表向前向后都可以遍历
    • 单链表和双向链表的数据结构都包含指向下一个元素指针 next, 双向链表还包括指向上一个元素指针 previous
    • 单链表只能向后遍历, 双向链表向前向后都可以遍历
    展开全文
  • 概要线性表是一种线性结构,它是具有相同类型的n(n≥0)个数据元素组成... C++实现双链表更多内容数组数组有上界下界,数组的元素在上下界内是连续的。存储10,20,30,40,50的数组的示意图如下:数组的特点是:数据是...

    概要

    线性表是一种线性结构,它是具有相同类型的n(n≥0)个数据元素组成的有限序列。本章先介绍线性表的几个基本组成部分:数组、单向链表、双向链表;随后给出双向链表的C、C++和Java三种语言的实现。内容包括:

    数组

    单向链表

    双向链表

    1. C实现双链表

    2. C++实现双链表

    更多内容

    数组

    数组有上界和下界,数组的元素在上下界内是连续的。

    存储10,20,30,40,50的数组的示意图如下:

    f23804a91132c83afcc6de45e958780e.png

    数组的特点是:数据是连续的;随机访问速度快。

    数组中稍微复杂一点的是多维数组和动态数组。对于C语言而言,多维数组本质上也是通过一维数组实现的。至于动态数组,是指数组的容量能动态增长的数组;对于C语言而言,若要提供动态数组,需要手动实现;而对于C++而言,STL提供了Vector;对于Java而言,Collection集合中提供了ArrayList和Vector。

    单向链表

    单向链表(单链表)是链表的一种,它由节点组成,每个节点都包含下一个节点的指针。

    单链表的示意图如下:

    f79bc1ceeeb56b341422ace7d12c2673.png

    表头为空,表头的后继节点是"节点10"(数据为10的节点),"节点10"的后继节点是"节点20"(数据为10的节点),...

    单链表删除节点

    d081cf7f6b0edf8e79d0af6a45a280e5.png

    删除"节点30"

    删除之前:"节点20" 的后继节点为"节点30",而"节点30" 的后继节点为"节点40"。

    删除之后:"节点20" 的后继节点为"节点40"。

    单链表添加节点

    91296f3af75f071d6a5abd36a337eea5.png

    在"节点10"与"节点20"之间添加"节点15"

    添加之前:"节点10" 的后继节点为"节点20"。

    添加之后:"节点10" 的后继节点为"节点15",而"节点15" 的后继节点为"节点20"。

    单链表的特点是:节点的链接方向是单向的;相对于数组来说,单链表的的随机访问速度较慢,但是单链表删除/添加数据的效率很高。

    双向链表

    双向链表(双链表)是链表的一种。和单链表一样,双链表也是由节点组成,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

    双链表的示意图如下:

    6ab2eb2392128dc4bd9fb02c8df137be.png

    表头为空,表头的后继节点为"节点10"(数据为10的节点);"节点10"的后继节点是"节点20"(数据为10的节点),"节点20"的前继节点是"节点10";"节点20"的后继节点是"节点30","节点30"的前继节点是"节点20";...;末尾节点的后继节点是表头。

    双链表删除节点

    946a9e1ebb867c127a060bdf392ee2ab.png

    删除"节点30"

    删除之前:"节点20"的后继节点为"节点30","节点30" 的前继节点为"节点20"。"节点30"的后继节点为"节点40","节点40" 的前继节点为"节点30"。

    删除之后:"节点20"的后继节点为"节点40","节点40" 的前继节点为"节点20"。

    双链表添加节点

    2673c70c327da78d5e74eba0813f7eff.png

    在"节点10"与"节点20"之间添加"节点15"

    添加之前:"节点10"的后继节点为"节点20","节点20" 的前继节点为"节点10"。

    添加之后:"节点10"的后继节点为"节点15","节点15" 的前继节点为"节点10"。"节点15"的后继节点为"节点20","节点20" 的前继节点为"节点15"。

    下面介绍双链表的实现,分别介绍C/C++/Java三种实现。

    1. C实现双链表

    实现代码

    双向链表头文件(double_link.h)

    8f900a89c6347c561fdf2122f13be562.png

    961ddebeb323a10fe0623af514929fc1.png

    1 #ifndef _DOUBLE_LINK_H2 #define _DOUBLE_LINK_H

    3

    4 //新建“双向链表”。成功,返回表头;否则,返回NULL

    5 extern intcreate_dlink();6 //撤销“双向链表”。成功,返回0;否则,返回-1

    7 extern intdestroy_dlink();8

    9 //“双向链表是否为空”。为空的话返回1;否则,返回0。

    10 extern intdlink_is_empty();11 //返回“双向链表的大小”

    12 extern intdlink_size();13

    14 //获取“双向链表中第index位置的元素”。成功,返回节点指针;否则,返回NULL。

    15 extern void* dlink_get(intindex);16 //获取“双向链表中第1个元素”。成功,返回节点指针;否则,返回NULL。

    17 extern void*dlink_get_first();18 //获取“双向链表中最后1个元素”。成功,返回节点指针;否则,返回NULL。

    19 extern void*dlink_get_last();20

    21 //将“value”插入到index位置。成功,返回0;否则,返回-1。

    22 extern int dlink_insert(int index, void *pval);23 //将“value”插入到表头位置。成功,返回0;否则,返回-1。

    24 extern int dlink_insert_first(void *pval);25 //将“value”插入到末尾位置。成功,返回0;否则,返回-1。

    26 extern int dlink_append_last(void *pval);27

    28 //删除“双向链表中index位置的节点”。成功,返回0;否则,返回-1

    29 extern int dlink_delete(intindex);30 //删除第一个节点。成功,返回0;否则,返回-1

    31 extern intdlink_delete_first();32 //删除组后一个节点。成功,返回0;否则,返回-1

    33 extern intdlink_delete_last();34

    35 #endif

    View Code

    双向链表实现文件(double_link.c)

    8f900a89c6347c561fdf2122f13be562.png

    961ddebeb323a10fe0623af514929fc1.png

    1 #include

    2 #include

    3

    4 /**5 * C 语言实现的双向链表,能存储任意数据。6 *7 * @author skywang8 * @date 2013/11/079 */

    10 //双向链表节点

    11 typedef structtag_node12 {13 struct tag_node *prev;14 struct tag_node *next;15 void*p;16 }node;17

    18 //表头。注意,表头不存放元素值!!!

    19 static node *phead=NULL;20 //节点个数。

    21 static int count=0;22

    23 //新建“节点”。成功,返回节点指针;否则,返回NULL。

    24 static node* create_node(void *pval)25 {26 node *pnode=NULL;27 pnode = (node *)malloc(sizeof(node));28 if (!pnode)29 {30 printf("create node error!\n");31 returnNULL;32 }33 //默认的,pnode的前一节点和后一节点都指向它自身

    34 pnode->prev = pnode->next =pnode;35 //节点的值为pval

    36 pnode->p =pval;37

    38 returnpnode;39 }40

    41 //新建“双向链表”。成功,返回0;否则,返回-1。

    42 intcreate_dlink()43 {44 //创建表头

    45 phead =create_node(NULL);46 if (!phead)47 return -1;48

    49 //设置“节点个数”为0

    50 count = 0;51

    52 return 0;53 }54

    55 //“双向链表是否为空”

    56 intdlink_is_empty()57 {58 return count == 0;59 }60

    61 //返回“双向链表的大小”

    62 intdlink_size() {63 returncount;64 }65

    66 //获取“双向链表中第index位置的节点”

    67 static node* get_node(intindex)68 {69 if (index<0 || index>=count)70 {71 printf("%s failed! index out of bound!\n", __func__);72 returnNULL;73 }74

    75 //正向查找

    76 if (index <= (count/2))77 {78 int i=0;79 node *pnode=phead->next;80 while ((i++) next;82

    83 returnpnode;84 }85

    86 //反向查找

    87 int j=0;88 int rindex = count - index - 1;89 node *rnode=phead->prev;90 while ((j++) prev;92

    93 returnrnode;94 }95

    96 //获取“第一个节点”

    97 static node*get_first_node()98 {99 return get_node(0);100 }101

    102 //获取“最后一个节点”

    103 static node*get_last_node()104 {105 return get_node(count-1);106 }107

    108 //获取“双向链表中第index位置的元素”。成功,返回节点值;否则,返回-1。

    109 void* dlink_get(intindex)110 {111 node *pindex=get_node(index);112 if (!pindex)113 {114 printf("%s failed!\n", __func__);115 returnNULL;116 }117

    118 return pindex->p;119

    120 }121

    122 //获取“双向链表中第1个元素的值”

    123 void*dlink_get_first()124 {125 return dlink_get(0);126 }127

    128 //获取“双向链表中最后1个元素的值”

    129 void*dlink_get_last()130 {131 return dlink_get(count-1);132 }133

    134 //将“pval”插入到index位置。成功,返回0;否则,返回-1。

    135 int dlink_insert(int index, void*pval)136 {137 //插入表头

    138 if (index==0)139 returndlink_insert_first(pval);140

    141 //获取要插入的位置对应的节点

    142 node *pindex=get_node(index);143 if (!pindex)144 return -1;145

    146 //创建“节点”

    147 node *pnode=create_node(pval);148 if (!pnode)149 return -1;150

    151 pnode->prev = pindex->prev;152 pnode->next =pindex;153 pindex->prev->next =pnode;154 pindex->prev =pnode;155 //节点个数+1

    156 count++;157

    158 return 0;159 }160

    161 //将“pval”插入到表头位置

    162 int dlink_insert_first(void *pval)163 {164 node *pnode=create_node(pval);165 if (!pnode)166 return -1;167

    168 pnode->prev =phead;169 pnode->next = phead->next;170 phead->next->prev =pnode;171 phead->next =pnode;172 count++;173 return 0;174 }175

    176 //将“pval”插入到末尾位置

    177 int dlink_append_last(void *pval)178 {179 node *pnode=create_node(pval);180 if (!pnode)181 return -1;182

    183 pnode->next =phead;184 pnode->prev = phead->prev;185 phead->prev->next =pnode;186 phead->prev =pnode;187 count++;188 return 0;189 }190

    191 //删除“双向链表中index位置的节点”。成功,返回0;否则,返回-1。

    192 int dlink_delete(intindex)193 {194 node *pindex=get_node(index);195 if (!pindex)196 {197 printf("%s failed! the index in out of bound!\n", __func__);198 return -1;199 }200

    201 pindex->next->prev = pindex->prev;202 pindex->prev->next = pindex->next;203 free(pindex);204 count--;205

    206 return 0;207 }208

    209 //删除第一个节点

    210 intdlink_delete_first()211 {212 return dlink_delete(0);213 }214

    215 //删除组后一个节点

    216 intdlink_delete_last()217 {218 return dlink_delete(count-1);219 }220

    221 //撤销“双向链表”。成功,返回0;否则,返回-1。

    222 intdestroy_dlink()223 {224 if (!phead)225 {226 printf("%s failed! dlink is null!\n", __func__);227 return -1;228 }229

    230 node *pnode=phead->next;231 node *ptmp=NULL;232 while(pnode !=phead)233 {234 ptmp =pnode;235 pnode = pnode->next;236 free(ptmp);237 }238

    239 free(phead);240 phead =NULL;241 count = 0;242

    243 return 0;244 }

    View Code

    双向链表测试程序(dlink_test.c)

    8f900a89c6347c561fdf2122f13be562.png

    961ddebeb323a10fe0623af514929fc1.png

    1 #include

    2 #include "double_link.h"

    3

    4 /**5 * C 语言实现的双向链表的测试程序。6 *7 * (01) int_test()8 * 演示向双向链表操作“int数据”。9 * (02) string_test()10 * 演示向双向链表操作“字符串数据”。11 * (03) object_test()12 * 演示向双向链表操作“对象”。13 *14 * @author skywang15 * @date 2013/11/0716 */

    17

    18 //双向链表操作int数据

    19 voidint_test()20 {21 int iarr[4] = {10, 20, 30, 40};22

    23 printf("\n----%s----\n", __func__);24 create_dlink(); //创建双向链表

    25

    26 dlink_insert(0, &iarr[0]); //向双向链表的表头插入数据

    27 dlink_insert(0, &iarr[1]); //向双向链表的表头插入数据

    28 dlink_insert(0, &iarr[2]); //向双向链表的表头插入数据

    29

    30 printf("dlink_is_empty()=%d\n", dlink_is_empty()); //双向链表是否为空

    31 printf("dlink_size()=%d\n", dlink_size()); //双向链表的大小32

    33 //打印双向链表中的全部数据

    34 inti;35 int *p;36 int sz =dlink_size();37 for (i=0; i

    43 destroy_dlink();44 }45

    46 voidstring_test()47 {48 char* sarr[4] = {"ten", "twenty", "thirty", "forty"};49

    50 printf("\n----%s----\n", __func__);51 create_dlink(); //创建双向链表

    52

    53 dlink_insert(0, sarr[0]); //向双向链表的表头插入数据

    54 dlink_insert(0, sarr[1]); //向双向链表的表头插入数据

    55 dlink_insert(0, sarr[2]); //向双向链表的表头插入数据

    56

    57 printf("dlink_is_empty()=%d\n", dlink_is_empty()); //双向链表是否为空

    58 printf("dlink_size()=%d\n", dlink_size()); //双向链表的大小59

    60 //打印双向链表中的全部数据

    61 inti;62 char *p;63 int sz =dlink_size();64 for (i=0; i

    70 destroy_dlink();71 }72

    73 typedef structtag_stu74 {75 intid;76 char name[20];77 }stu;78

    79 static stu arr_stu[] =

    80 {81 {10, "sky"},82 {20, "jody"},83 {30, "vic"},84 {40, "dan"},85 };86 #define ARR_STU_SIZE ( (sizeof(arr_stu)) / (sizeof(arr_stu[0])) )

    87

    88 voidobject_test()89 {90 printf("\n----%s----\n", __func__);91 create_dlink(); //创建双向链表

    92

    93 dlink_insert(0, &arr_stu[0]); //向双向链表的表头插入数据

    94 dlink_insert(0, &arr_stu[1]); //向双向链表的表头插入数据

    95 dlink_insert(0, &arr_stu[2]); //向双向链表的表头插入数据

    96

    97 printf("dlink_is_empty()=%d\n", dlink_is_empty()); //双向链表是否为空

    98 printf("dlink_size()=%d\n", dlink_size()); //双向链表的大小99

    100 //打印双向链表中的全部数据

    101 inti;102 int sz =dlink_size();103 stu *p;104 for (i=0; iid, p->name);108 }109

    110 destroy_dlink();111 }112

    113 intmain()114 {115 int_test(); //演示向双向链表操作“int数据”。

    116 string_test(); //演示向双向链表操作“字符串数据”。

    117 object_test(); //演示向双向链表操作“对象”。

    118

    119 return 0;120 }

    View Code

    运行结果

    ----int_test----

    dlink_is_empty()=0

    dlink_size()=3

    dlink_get(0)=30

    dlink_get(1)=20

    dlink_get(2)=10

    ----string_test----

    dlink_is_empty()=0

    dlink_size()=3

    dlink_get(0)=thirty

    dlink_get(1)=twenty

    dlink_get(2)=ten

    ----object_test----

    dlink_is_empty()=0

    dlink_size()=3

    dlink_get(0)=[30, vic]

    dlink_get(1)=[20, jody]

    dlink_get(2)=[10, sky]

    2. C++实现双链表

    实现代码

    双向链表文件(DoubleLink.h)

    8f900a89c6347c561fdf2122f13be562.png

    961ddebeb323a10fe0623af514929fc1.png

    1 #ifndef DOUBLE_LINK_HXX2 #define DOUBLE_LINK_HXX

    3

    4 #include

    5 using namespacestd;6

    7 template

    8 structDNode9 {10 public:11 T value;12 DNode *prev;13 DNode *next;14 public:15 DNode() { }16 DNode(T t, DNode *prev, DNode *next) {17 this->value =t;18 this->prev =prev;19 this->next =next;20 }21 };22

    23 template

    24 classDoubleLink25 {26 public:27 DoubleLink();28 ~DoubleLink();29

    30 intsize();31 intis_empty();32

    33 T get(intindex);34 T get_first();35 T get_last();36

    37 int insert(intindex, T t);38 intinsert_first(T t);39 intappend_last(T t);40

    41 int del(intindex);42 intdelete_first();43 intdelete_last();44

    45 private:46 intcount;47 DNode *phead;48 private:49 DNode *get_node(intindex);50 };51

    52 template

    53 DoubleLink::DoubleLink() : count(0)54 {55 //创建“表头”。注意:表头没有存储数据!

    56 phead = new DNode();57 phead->prev = phead->next =phead;58 //设置链表计数为059 //count = 0;

    60 }61

    62 //析构函数

    63 template

    64 DoubleLink::~DoubleLink()65 {66 //删除所有的节点

    67 DNode*ptmp;68 DNode* pnode = phead->next;69 while (pnode !=phead)70 {71 ptmp =pnode;72 pnode=pnode->next;73 delete ptmp;74 }75

    76 //删除"表头"

    77 delete phead;78 phead =NULL;79 }80

    81 //返回节点数目

    82 template

    83 int DoubleLink::size()84 {85 returncount;86 }87

    88 //返回链表是否为空

    89 template

    90 int DoubleLink::is_empty()91 {92 return count==0;93 }94

    95 //获取第index位置的节点

    96 template

    97 DNode* DoubleLink::get_node(intindex)98 {99 //判断参数有效性

    100 if (index<0 || index>=count)101 {102 cout << "get node failed! the index in out of bound!" <

    106 //正向查找

    107 if (index <= count/2)108 {109 int i=0;110 DNode* pindex = phead->next;111 while (i++ next;113 }114

    115 returnpindex;116 }117

    118 //反向查找

    119 int j=0;120 int rindex = count - index -1;121 DNode* prindex = phead->prev;122 while (j++ prev;124 }125

    126 returnprindex;127 }128

    129 //获取第index位置的节点的值

    130 template

    131 T DoubleLink::get(intindex)132 {133 return get_node(index)->value;134 }135

    136 //获取第1个节点的值

    137 template

    138 T DoubleLink::get_first()139 {140 return get_node(0)->value;141 }142

    143 //获取最后一个节点的值

    144 template

    145 T DoubleLink::get_last()146 {147 return get_node(count-1)->value;148 }149

    150 //将节点插入到第index位置之前

    151 template

    152 int DoubleLink::insert(intindex, T t)153 {154 if (index == 0)155 returninsert_first(t);156

    157 DNode* pindex =get_node(index);158 DNode* pnode = new DNode(t, pindex->prev, pindex);159 pindex->prev->next =pnode;160 pindex->prev =pnode;161 count++;162

    163 return 0;164 }165

    166 //将节点插入第一个节点处。

    167 template

    168 int DoubleLink::insert_first(T t)169 {170 DNode* pnode = new DNode(t, phead, phead->next);171 phead->next->prev =pnode;172 phead->next =pnode;173 count++;174

    175 return 0;176 }177

    178 //将节点追加到链表的末尾

    179 template

    180 int DoubleLink::append_last(T t)181 {182 DNode* pnode = new DNode(t, phead->prev, phead);183 phead->prev->next =pnode;184 phead->prev =pnode;185 count++;186

    187 return 0;188 }189

    190 //删除index位置的节点

    191 template

    192 int DoubleLink::del(intindex)193 {194 DNode* pindex =get_node(index);195 pindex->next->prev = pindex->prev;196 pindex->prev->next = pindex->next;197 delete pindex;198 count--;199

    200 return 0;201 }202

    203 //删除第一个节点

    204 template

    205 int DoubleLink::delete_first()206 {207 return del(0);208 }209

    210 //删除最后一个节点

    211 template

    212 int DoubleLink::delete_last()213 {214 return del(count-1);215 }216

    217 #endif

    View Code

    双向链表测试文件(DlinkTest.cpp)

    8f900a89c6347c561fdf2122f13be562.png

    961ddebeb323a10fe0623af514929fc1.png

    1 #include

    2 #include "DoubleLink.h"

    3 using namespacestd;4

    5 //双向链表操作int数据

    6 voidint_test()7 {8 int iarr[4] = {10, 20, 30, 40};9

    10 cout << "\n----int_test----" <

    12 DoubleLink* pdlink = new DoubleLink();13

    14 pdlink->insert(0, 20); //将 20 插入到第一个位置

    15 pdlink->append_last(10); //将 10 追加到链表末尾

    16 pdlink->insert_first(30); //将 30 插入到第一个位置17

    18 //双向链表是否为空

    19 cout << "is_empty()=" << pdlink->is_empty() <

    21 cout << "size()=" << pdlink->size() <

    23 //打印双向链表中的全部数据

    24 int sz = pdlink->size();25 for (int i=0; iget(i) <

    29 voidstring_test()30 {31 string sarr[4] = {"ten", "twenty", "thirty", "forty"};32

    33 cout << "\n----string_test----" <

    35 DoubleLink* pdlink = new DoubleLink();36

    37 pdlink->insert(0, sarr[1]); //将 sarr中第2个元素 插入到第一个位置

    38 pdlink->append_last(sarr[0]); //将 sarr中第1个元素 追加到链表末尾

    39 pdlink->insert_first(sarr[2]); //将 sarr中第3个元素 插入到第一个位置40

    41 //双向链表是否为空

    42 cout << "is_empty()=" << pdlink->is_empty() <

    44 cout << "size()=" << pdlink->size() <

    46 //打印双向链表中的全部数据

    47 int sz = pdlink->size();48 for (int i=0; iget(i) <

    52 structstu53 {54 intid;55 char name[20];56 };57

    58 static stu arr_stu[] =

    59 {60 {10, "sky"},61 {20, "jody"},62 {30, "vic"},63 {40, "dan"},64 };65 #define ARR_STU_SIZE ( (sizeof(arr_stu)) / (sizeof(arr_stu[0])) )

    66

    67 voidobject_test()68 {69 cout << "\n----object_test----" <

    71 DoubleLink* pdlink = new DoubleLink();72

    73 pdlink->insert(0, arr_stu[1]); //将 arr_stu中第2个元素 插入到第一个位置

    74 pdlink->append_last(arr_stu[0]); //将 arr_stu中第1个元素 追加到链表末尾

    75 pdlink->insert_first(arr_stu[2]); //将 arr_stu中第3个元素 插入到第一个位置76

    77 //双向链表是否为空

    78 cout << "is_empty()=" << pdlink->is_empty() <

    80 cout << "size()=" << pdlink->size() <

    82 //打印双向链表中的全部数据

    83 int sz = pdlink->size();84 structstu p;85 for (int i=0; iget(i);88 cout << "pdlink("<

    92

    93 intmain()94 {95 int_test(); //演示向双向链表操作“int数据”。

    96 string_test(); //演示向双向链表操作“字符串数据”。

    97 object_test(); //演示向双向链表操作“对象”。

    98

    99 return 0;100 }

    View Code

    示例说明

    在上面的示例中,我将双向链表的"声明"和"实现"都放在头文件中。而编程规范告诫我们:将类的声明和实现分离,在头文件(.h文件或.hpp)中尽量只包含声明,而在实现文件(.cpp文件)中负责实现!

    那么为什么要这么做呢?这是因为,在双向链表的实现中,采用了模板;而C++编译器不支持对模板的分离式编译!简单点说,如果在DoubleLink.h中声明,而在DoubleLink.cpp中进行实现的话;当我们在其他类中创建DoubleLink的对象时,会编译出错。具体原因,可以参考"为什么C++编译器不能支持对模板的分离式编译"。

    运行结果

    ----int_test----is_empty()=0size()=3pdlink(0)=30pdlink(1)=20pdlink(2)=10

    ----string_test----is_empty()=0size()=3pdlink(0)=thirty

    pdlink(1)=twenty

    pdlink(2)=ten----object_test----is_empty()=0size()=3pdlink(0)=[30, vic]

    pdlink(1)=[20, jody]

    pdlink(2)=[10, sky]

    3. Java实现双链表

    实现代码

    双链表类(DoubleLink.java)

    8f900a89c6347c561fdf2122f13be562.png

    961ddebeb323a10fe0623af514929fc1.png

    1 /**

    2 * Java 实现的双向链表。3 * 注:java自带的集合包中有实现双向链表,路径是:java.util.LinkedList4 *5 *@authorskywang6 * @date 2013/11/077 */

    8 public class DoubleLink{9

    10 //表头

    11 private DNodemHead;12 //节点个数

    13 private intmCount;14

    15 //双向链表“节点”对应的结构体

    16 private class DNode{17 publicDNode prev;18 publicDNode next;19 publicT value;20

    21 publicDNode(T value, DNode prev, DNode next) {22 this.value =value;23 this.prev =prev;24 this.next =next;25 }26 }27

    28 //构造函数

    29 publicDoubleLink() {30 //创建“表头”。注意:表头没有存储数据!

    31 mHead = new DNode(null, null, null);32 mHead.prev = mHead.next =mHead;33 //初始化“节点个数”为0

    34 mCount = 0;35 }36

    37 //返回节点数目

    38 public intsize() {39 returnmCount;40 }41

    42 //返回链表是否为空

    43 public booleanisEmpty() {44 return mCount==0;45 }46

    47 //获取第index位置的节点

    48 private DNode getNode(intindex) {49 if (index<0 || index>=mCount)50 throw newIndexOutOfBoundsException();51

    52 //正向查找

    53 if (index <= mCount/2) {54 DNode node =mHead.next;55 for (int i=0; i

    58 returnnode;59 }60

    61 //反向查找

    62 DNode rnode =mHead.prev;63 int rindex = mCount - index -1;64 for (int j=0; j

    67 returnrnode;68 }69

    70 //获取第index位置的节点的值

    71 public T get(intindex) {72 returngetNode(index).value;73 }74

    75 //获取第1个节点的值

    76 publicT getFirst() {77 return getNode(0).value;78 }79

    80 //获取最后一个节点的值

    81 publicT getLast() {82 return getNode(mCount-1).value;83 }84

    85 //将节点插入到第index位置之前

    86 public void insert(intindex, T t) {87 if (index==0) {88 DNode node = new DNode(t, mHead, mHead.next);89 mHead.next.prev =node;90 mHead.next =node;91 mCount++;92 return;93 }94

    95 DNode inode =getNode(index);96 DNode tnode = new DNode(t, inode.prev, inode);97 inode.prev.next =tnode;98 inode.next =tnode;99 mCount++;100 return;101 }102

    103 //将节点插入第一个节点处。

    104 public voidinsertFirst(T t) {105 insert(0, t);106 }107

    108 //将节点追加到链表的末尾

    109 public voidappendLast(T t) {110 DNode node = new DNode(t, mHead.prev, mHead);111 mHead.prev.next =node;112 mHead.prev =node;113 mCount++;114 }115

    116 //删除index位置的节点

    117 public void del(intindex) {118 DNode inode =getNode(index);119 inode.prev.next =inode.next;120 inode.next.prev =inode.prev;121 inode = null;122 mCount--;123 }124

    125 //删除第一个节点

    126 public voiddeleteFirst() {127 del(0);128 }129

    130 //删除最后一个节点

    131 public voiddeleteLast() {132 del(mCount-1);133 }134 }

    View Code

    测试程序(DlinkTest.java)

    8f900a89c6347c561fdf2122f13be562.png

    961ddebeb323a10fe0623af514929fc1.png

    1 /**

    2 * Java 实现的双向链表。3 * 注:java自带的集合包中有实现双向链表,路径是:java.util.LinkedList4 *5 *@authorskywang6 * @date 2013/11/077 */

    8

    9 public classDlinkTest {10

    11 //双向链表操作int数据

    12 private static voidint_test() {13 int[] iarr = {10, 20, 30, 40};14

    15 System.out.println("\n----int_test----");16 //创建双向链表

    17 DoubleLink dlink = new DoubleLink();18

    19 dlink.insert(0, 20); //将 20 插入到第一个位置

    20 dlink.appendLast(10); //将 10 追加到链表末尾

    21 dlink.insertFirst(30); //将 30 插入到第一个位置22

    23 //双向链表是否为空

    24 System.out.printf("isEmpty()=%b\n", dlink.isEmpty());25 //双向链表的大小

    26 System.out.printf("size()=%d\n", dlink.size());27

    28 //打印出全部的节点

    29 for (int i=0; i

    33

    34 private static voidstring_test() {35 String[] sarr = {"ten", "twenty", "thirty", "forty"};36

    37 System.out.println("\n----string_test----");38 //创建双向链表

    39 DoubleLink dlink = new DoubleLink();40

    41 dlink.insert(0, sarr[1]); //将 sarr中第2个元素 插入到第一个位置

    42 dlink.appendLast(sarr[0]); //将 sarr中第1个元素 追加到链表末尾

    43 dlink.insertFirst(sarr[2]); //将 sarr中第3个元素 插入到第一个位置44

    45 //双向链表是否为空

    46 System.out.printf("isEmpty()=%b\n", dlink.isEmpty());47 //双向链表的大小

    48 System.out.printf("size()=%d\n", dlink.size());49

    50 //打印出全部的节点

    51 for (int i=0; i

    55

    56 //内部类

    57 private static classStudent {58 private intid;59 privateString name;60

    61 public Student(intid, String name) {62 this.id =id;63 this.name =name;64 }65

    66 @Override67 publicString toString() {68 return "["+id+", "+name+"]";69 }70 }71

    72 private static Student[] students = newStudent[]{73 new Student(10, "sky"),74 new Student(20, "jody"),75 new Student(30, "vic"),76 new Student(40, "dan"),77 };78

    79 private static voidobject_test() {80 System.out.println("\n----object_test----");81 //创建双向链表

    82 DoubleLink dlink = new DoubleLink();83

    84 dlink.insert(0, students[1]); //将 students中第2个元素 插入到第一个位置

    85 dlink.appendLast(students[0]); //将 students中第1个元素 追加到链表末尾

    86 dlink.insertFirst(students[2]); //将 students中第3个元素 插入到第一个位置87

    88 //双向链表是否为空

    89 System.out.printf("isEmpty()=%b\n", dlink.isEmpty());90 //双向链表的大小

    91 System.out.printf("size()=%d\n", dlink.size());92

    93 //打印出全部的节点

    94 for (int i=0; i

    99

    100 public static voidmain(String[] args) {101 int_test(); //演示向双向链表操作“int数据”。

    102 string_test(); //演示向双向链表操作“字符串数据”。

    103 object_test(); //演示向双向链表操作“对象”。

    104 }105 }

    View Code

    运行结果

    ----int_test----isEmpty()=falsesize()=3dlink(0)=30dlink(1)=20dlink(2)=10

    ----string_test----isEmpty()=falsesize()=3dlink(0)=thirty

    dlink(1)=twenty

    dlink(2)=ten----object_test----isEmpty()=falsesize()=3dlink(0)=[30, vic]

    dlink(1)=[20, jody]

    dlink(2)=[10, sky]

    展开全文
  • C++单链表和双向链表

    2020-04-05 22:56:11
    C++单链表和双向链表 1.单链表 #include <assert.h> // 单链表节点 template<class T> struct Node { T value; Node<T>* next; public: Node(T value, Node<T>* next) { this->...
  • 反转单链表和双链表

    2018-09-25 22:08:24
    反转单链表和双链表,额外空间复杂度为O(1) //两个变量,一个保存当前节点的之前的next,一个保存当前节点, public static Node reverseList(Node head){ Node oldNext = null; Node newNext = null; while...
  • 单链表和双链表的反转总结 #include&lt;iostream&gt; #include&lt;vector&gt; using namespace std; struct singlenode { int value; singlenode *next; }; struct doublenode { int value; ...
  • 单链表与双向链表单链表双向链表 概念 链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的。 分类 实际中链表的结构非常多样,以下情况组合起来就有8种链表结构: 单向...
  • 由于最近要用单链表和双向链表所以这里总结一些常用的操作。 1.单链表 forward_list<int> a;//创建一个单向链表 cout << a.max_size() << endl;//单链表保存的最大元素数目 for (int i = 0; ...
  •  链表是一种比较常用的数据结构,链表虽然保存比较复杂,但是在查询时候比较便捷,在多种计算机语言都相应的应用,链表有多种类别,文章针对单链表和双链表进行分析。链表中数据就像被一个链条串联一起,轻易的可以...
  • 文章目录在单链表和双链表中删除倒数第K个节点【题目】【要求】【解答】 在单链表和双链表中删除倒数第K个节点 【题目】 分别实现两个函数,一个可以删除单链表中倒数第k个节点,另一个可以删除双链表中倒数第k个...
  • 单链表和双链表的删除和插入的时间复杂度分析 单向链表要删除某一节点时,必须要先通过遍历的方式找到前驱节点(开发中大致分为两种删除方式:1.通过待删除节点序号2.按值查找)。若仅仅知道待删除节点,是不能...
  • 1、链表(Linked List)介绍 1.1、内存结构 ...又由于此链表的每个结点中只有一个指向后继的指针,所以称其为单链表或线性链表。下图的单链表是带有头结点的单链表,头结点的作用是方便单链表的特殊操作,简化代

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,716
精华内容 1,486
关键字:

单链表和双链表