精华内容
下载资源
问答
  • 一、双向链表(double linked list)是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。双向链表的基本操作与单链表基本一样,除了插入和删除的时候需要更改两个指针变量,需要注意的是修改的顺序很重要,...

    一、双向链表(double linked list)是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。双向链表的基本操作与单链表基本一样,除了插入和删除的时候需要更改两个指针变量,需要注意的是修改的顺序很重要,插入如图3-14-5,删除如图3-14-6。

    b9ad5e9a3029b7bc89cc94366d9076f3.png

    0bf5532ec11cb19c3a1b4765bc3dc6a4.png

    由于引入了prev指针,insert和delete函数中都有一些特殊情况需要用特殊的代码处理,不能和一般情况用同样的代码处理,这非常不爽,如果在表头和表尾各添加一个Sentinel节点(这两个节点只用于界定表头和表尾,不保存数据),就可以把这些特殊情况都转化为一般情况了。如图26.6

    dadb9d71319ee7faba78a24fa31a73b1.png

    在《队列的链式存储结构》中我们使用单链表实现队列的尾进头出,下面我们演示使用双向链表实现队列的头进尾出。

    参考:《Linux C编程 一站式学习》

    C++ Code

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28

    29

    30

    31

    32

    33

    34

    /*************************************************************************

    > File Name: doublylinkedlist.h

    > Author: Simba

    > Mail: dameng34@163.com

    > Created Time: Fri 28 Dec 2012 08:02:35 PM CST

    ************************************************************************/

    #ifndef DOUBLYLINKEDLIST_H

    #define DOUBLYLINKEDLIST_H

    typedef

    struct node

    {

    unsigned

    char item;

    struct node *prev;

    struct node *next;

    } node;

    typedef node *link;

    link make_node(

    unsigned

    char item);

    void free_node(link p);

    link search(

    unsigned

    char key);

    void insert(link p);

    void deletep(link p);

    void traverse(

    void (*visit)(link));

    void destroy(

    void);

    void enqueue(link p);

    link dequeue(

    void);

    #endif

    C++ Code

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28

    29

    30

    31

    32

    33

    34

    35

    36

    37

    38

    39

    40

    41

    42

    43

    44

    45

    46

    47

    48

    49

    50

    51

    52

    53

    54

    55

    56

    57

    58

    59

    60

    61

    62

    63

    64

    65

    66

    67

    68

    69

    70

    71

    72

    73

    74

    75

    76

    77

    78

    79

    80

    81

    82

    83

    84

    85

    86

    87

    88

    89

    90

    91

    92

    93

    94

    95

    96

    97

    98

    99

    100

    101

    102

    103

    104

    /*************************************************************************

    > File Name: doublylinkedlist.c

    > Author: Simba

    > Mail: dameng34@163.com

    > Created Time: Fri 28 Dec 2012 08:07:21 PM CST

    ************************************************************************/

    #include

    #include

    #include

    "doublylinkedlist.h"

    node tailsentinel;

    node headsentinel = {

    0,

    NULL, &tailsentinel};

    node tailsentinel = {

    0, &headsentinel,

    NULL};

    static link head = &headsentinel;

    static link tail = &tailsentinel;

    link make_node(

    unsigned

    char item)

    {

    link p =  malloc(

    sizeof(node));

    p->item = item;

    p->prev = p->next =

    NULL;

    printf(

    "make node from Item %d\n", item);

    return p;

    }

    void free_node(link p)

    {

    printf(

    "free node ...\n");

    free(p);

    }

    link search(

    unsigned

    char key)

    {

    link p;

    printf(

    "search by key %d\n", key);

    for (p = head->next; p != tail; p = p->next)

    if (p->item == key)

    return p;

    return

    NULL;

    }

    void insert(link p)

    {

    printf(

    "insert node from head ...\n");

    p->next = head->next;

    head->next->prev = p;

    head->next = p;

    p->prev = head;

    }

    void deletep(link p)

    {

    printf(

    "delete node from ptr ...\n");

    p->prev->next = p->next;

    p->next->prev = p->prev;

    }

    void traverse(

    void (*visit)(link))

    {

    link p;

    printf(

    "doublylinkedlist traverse ...\n");

    for (p = head->next; p != tail; p = p->next)

    visit(p);

    printf(

    "\n");

    }

    void destroy(

    void)

    {

    link q, p = head->next;

    printf(

    "destory doublylinkedlist ...\n");

    head->next = tail;

    tail->prev = head;

    while (p != tail)

    {

    q = p;

    p = p->next;

    free_node(q);

    }

    }

    void enqueue(link p)

    {

    printf(

    "enqueue from head ...\n");

    insert(p);

    }

    link dequeue(

    void)

    {

    if (tail->prev == head)

    return

    NULL;

    else

    {

    link p = tail->prev;

    printf(

    "dequeue from tail ...\n");

    deletep(p);

    return p;

    }

    }

    C++ Code

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28

    29

    30

    31

    32

    33

    34

    35

    36

    37

    38

    39

    40

    41

    42

    43

    44

    45

    46

    47

    /*************************************************************************

    > File Name: main2.c

    > Author: Simba

    > Mail: dameng34@163.com

    > Created Time: Fri 28 Dec 2012 08:18:57 PM CST

    ************************************************************************/

    #include

    #include

    "doublylinkedlist.h"

    void print_item(link p)

    {

    printf(

    "print item %d \n", p->item);

    }

    int main(

    void)

    {

    link p = make_node(

    10);

    insert(p);

    p = make_node(

    5);

    insert(p);

    p = make_node(

    90);

    insert(p);

    p = search(

    5);

    deletep(p);

    free_node(p);

    traverse(print_item);

    destroy();

    printf(

    "..................\n");

    p = make_node(

    100);

    enqueue(p);

    p = make_node(

    200);

    enqueue(p);

    p = make_node(

    250);

    enqueue(p);

    while ((p = dequeue()))

    {

    print_item(p);

    free_node(p);

    }

    return

    0;

    }

    输出为:

    48fa802e97c39bfe605deee7b856acd3.png

    解决的error:

    关于错误 error C2275: “XXX”: 将此类型用作表达式非法

    在移植c++代码到c的时候,经常会出现一个奇怪的错误, error C2275: “XXX”: 将此类型用作表达式非法,这个错误是由于c的编译器要求将变量的定义放在所有函数调用语句之前,而c++没有这样的要求造成的。解决的办法就是把变量的定义全部放在变量的生存块的开始。

    ------------------------------------------------------------------------------------------------------------------------------------

    二、将单链表中终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表就称为单循环链表,简称循环链表(circular linked list)。如下图所示。

    d0c0007c4392fd388533384ee0567959.png

    其实循环链表和单链表的主要差异就在于循环的判断条件上,原来是判断p->next是否为空,现在则是p->next不等于头结点,则循环未结束。

    我们在《队列的顺序存储结构(循环队列)》中使用数组实现了环形队列,我们还要“假想”它是首尾相接的,而如果基于链表实现环形队列,我们本来就可以用指针串成首尾相接的。把上面的程序改成双向环形链表也非常简单,只需要将

    把doublylinkedlist.c中的

    node tailsentinel;

    node headsentinel = {0, NULL, &tailsentinel};

    node tailsentinel = {0, &headsentinel, NULL};

    static link head = &headsentinel;

    static link tail = &tailsentinel;

    改成:

    node sentinel = {0, &sentinel, &sentinel};

    static link head = &sentinel;

    再把doublylinkedlist.c中所有的tail替换成head即可,相当于把head和tail合二为一了。如图26.7:

    a5e08c7c1578c37fb94f15557bb1caea.png

    展开全文
  • 若是不清楚链表的结构,该篇文章不适合观看,这里只做文字说明,没有链表结构的图示


    前言:
    线性表是我们最常用的一种数据结构,线性表包含顺序表和链表,顺序表典型应用就是我们常用的ArrayList,链表的典型应用其中就有我们常用的LinkedList。LinkedList他的底层就是使用链表来存储数据元素的。这篇文章用以总结链表中的双向循环链表,为单链表的结点增加一个指向前驱的指针域,单链表就变成了双链表,将双链表的头尾相连,双链表就成了双向循环链表。

    一、相关概念

    第一部分主要介绍下和链表有关的相关概念,这里给出的概念都是书本上的官方定义,并不是作者胡诌的,为什么给出这些官方的定义呢 ?因为笔者认为官方给出的定义,是对一个概念最本质的解释,它的解释经过了时间的考验,被认为是解释的最合理深入简明扼要的。

    1.什么是线性表

    线性表是由n个数据元素构成的有限序列,n为线性表的表长,当n为0时表示当前线性表是空表。线性表有且仅有一个开始结点和终端节点。且开始结点没有前驱,终端节点没有后继,其余节点有且仅有一个前驱和后继。线性表一般分为顺序表和链表。

    2.什么是顺序表

    采用顺序存储结构存储数据元素的线性表被称为顺序表,顺序表,要求逻辑上相邻的数据元素在物理内存的存储上也是相邻的,当在顺序表的第i(0<=i<=n)插入一个数据元素时,需要后移n-i+1个数据元素,当删除第i个元素时需要移动n-i个数据元素。java实现顺序表

    3.什么是链表

    采用链式存储结构存储数据元素的线性表被称为链表,链表不要求逻辑上相邻的数据元素内存上必须相邻,链表的每个节点都包含两部分,一部分是数据域用以存储数据,一部分是指针域用以存储指向相邻结点的指针或者引用。链表通过每个节点的指针域将一串数据串联成链。当结点只有一个指针域时,被称为单链表。单链表-含头结点单链表-不含头结点

    4.单链表、双链表、循环单链表、循环双链表

    当链表的结点只有一个指针域时被称为单链表,循环单链表是单链表的一种特殊变化,只是将尾结点又指向了头结点(也可能是首结点)。
    当链表的结点有两个时,一个指向前驱,一个指向后继这种链表便是双链表,循环双链表是双链表的一种特殊变化,只是将尾结点又指向了头结点(也可能是首结点)。
    所有的链表的实现均有两种方式,一种是带有头结点,一种是不带有头结点的实现方式,两种实现略有区别。

    5.为什么需要循环链表?

    循环链表一般就是指循环单链表,不特殊指明是双向循环链表,那么该名称描述的就是单项循环链表,之所以需要循环链表是因为在操作系统中,循环链表有特定的应用场景,在一些场景中,链表中的元素需要循环的执行,但是在实际的开发中应用最多的还是双向循环链表。

    6.为什么需要双向链表?

    若是给定了一个结点,根据当前结点获取该结点的上一个结点,那么我们是没有办法直接获取的,只能是遍历链表,但若是使用了双向链表,我们则可以直接获取到该元素的上一个结点,时间复杂度就变成了O(1)。所以双向链表的实际应用意义更强,将双向链表的首尾相连就成了双向循环链表,双向循环链表的应用最常见的就是LinkedList。

    7.头结点和首结点

    首节点:真正存储第一个数据元素的结点被称为首节点。
    头结点:当链表采用带头结点方式实现时,会创建一个数据域为null的节点,该节点的指针域存储的指针指向首节点的指针,他的唯一作用是标识链表的开始,带有头结点的链表更易于操作。

    8.常见的栈和队列与线性表的关系

    栈和队列也是常见的数据结构,但是栈和队列并不是线性表的一种,线性表只包含了顺序表和链表。不过我们可以将栈和队列看成是特殊的线性表。怎么特殊呢,栈是被限制了只能在一端进行插入和删除操作的线性表,所以栈的特性是先入后出,队列是被限制了只能在一端插入另一端删除的线性表,所以队列的特性是先入先出。既然栈和队列都是特殊的线性表,那么栈和队列自然就可以使用线性表来实现了,通常可以使用线性表中的顺序表和队列来实现栈和队列。

    二、实现过程

    单链表-含头结点
    单链表-不含头结点
    上面是两种单链表的实现方式,其实无论是双链表还是双向循环链表他的实现方式都是类似的,区别都很有限,上面两篇文章里详细实现了单链表的各种常用方法,因此在该文章里只会总结必须用到的几个方法,比如插入、删除、清空、长度、判空、根据下标获取等,其他方法的实现都不难,就不一一展示了。

    1.提供节点类:DupNode

    双向循环链表的实现,我们首先必须为其提供一个结点类,该类需要有三个属性,一个数据域,一个指向前驱的指针域,还有一个指向后继的指针域,然后提供必要的构造方法即可,如下:

    /**
     * @author pcc
     * @version 1.0.0
     * @className DupNode
     * @date 2021-04-19 16:43
     * 该类是双向链表的结点类
     * 该类包含了数据域,后继指针域、前驱指针域三个属性。
     */
    public class DupNode {
        Object object;
        DupNode prior;//前驱指针域
        DupNode next;//后继指针域
    
        public DupNode(){
            this(null);
        }
        public DupNode(Object object){
            this(object,null,null);
        }
        public DupNode(Object object,DupNode prior,DupNode next){
            this.object = object;
            this.prior = prior;
            this.next = next;
        }
    }
    

    2.提供双向循环链表的实现类:DoubleLinkedTable

    采用带有头结点的方式实现双向循环链表,因此我们需要定义一个头结点。然后提供初始化它的构造器。值得注意的是,在初始化头结点时,我们必须将他的前驱和后继都声明为自己,这样才是一个空的双向循环链表。

    public class DoubleLinkedTable {
        //头结点
        DupNode head;
    
        public DoubleLinkedTable(){
            head = new DupNode();
            head.prior = head;
            head.next = head;
        }
    }
    

    3.提供长度(length)、打印(display)、清空(clear)等方法

    这些方法的实现原理都很简单,求链表长就是遍历链表计数即可,打印也是遍历链表,清空则是将头结点的前驱和后继都声明为自己,下面是三个方法的实现:

        //长度
        public int length(){
            DupNode node = head.next;
            int j = 0;
            while(!node.equals(head)){
                j++;
                node = node.next;
            }
            return j;
        }
    
        //打印
        public void display(){
            DupNode node = head.next;
            while(!node.equals(head)){
                System.out.println(node.object);
                node = node.next;
            }
        }
        //清空
        public void clear(){
            head.next = head;
            head.prior = head;
        }
    

    4.提供根据下标插入方法:insert(int i,Object object)
    学习双向循环链表建议还是先学习单链表,会了单链表双向循环链表就是窗户纸,一桶就破,因为他们的实现思路都是一样的,只是稍微的变化而已。单链表的遍历我们的退出条件是找到尾结点就退出(node.next == null),循环链表肯定没有尾结点了,退出循环的条件就成了碰到头结点再退出(node ==head),另外一点区别就是双向循环链表的赋值问题,我们需要为新结点的前驱指针和后继指针赋值,同时需要为新结点的上一个节点的后继后继指针从新赋值,还需要为新节点的后继结点的前驱指针重新赋值,代码实现如下:

       /**
         * 思路:
         * 1.寻找下标为i-1的数据元素,注意退出循环的条件应该是node!=head
         * 2.赋值即可,循环链表的核心就是空表也会有循环体系
         * 3,赋值时,i+1位置的元素应该是node.next 所以,应为node.next最后赋值
         * @param i
         * @param object
         * @throws Exception
         */
        public void insert(int i,Object object) throws Exception{
            if(i<0 || i>length())
                throw new Exception("下标不合法");
             DupNode node = head;
             int j = 0;
             while(!node.next.equals(head) && j<i){
                 j++;
                 node = node.next;
             }
    //         DupNode newNode = new DupNode(object);
    //         node.next.prior = newNode;
    //         newNode.prior = node;
    //         newNode.next = node.next;
    //         node.next = newNode;
    
            //写成以下这种和上面注释的部分,效果一样,无区别
             DupNode newNode = new DupNode(object,node,node.next);
             node.next.prior = newNode;
             node.next = newNode;
        }
    

    到了这里,我们就可以初步测试下,双向链表的插入是否有效了,下面创建一个测试类测试下,如下图所示,将几个元素插入到了双向循环链表中,然后输出结果正常,说明插入方法实现无误。有了这些头插法、尾插法直接根据下标即可轻松实现,这里不展示了。
    在这里插入图片描述

    5.提供根据下标删除的方法:remove(int i)

    实现思路其实和单链表的删除是没有区别的:寻找到下标为i-1的数据元素,然后将他的后继更改为i+1的数据元素,然后将下标为i+1的数据元素的前驱更改为,下标为i-1的数据元素即可,实现如下:

        //删除
        public void remove(int i) throws Exception{
            if(i<0 || i>length()-1)
                throw new Exception("下标不合法");
            DupNode node = head;
            int j = 0;
            while(!node.next.equals(head) && j<i){
                j++;
                node = node.next;
            }
            node.next = node.next.next;
            node.next.prior = node;
        }
    

    然后来测试下删除方法,就测试下删除下标为2的元素吧,理论上删除后,输出的应该是:张三、李四、赵柳,如下图可见,输出无误,可见删除方法实现时无误的。
    在这里插入图片描述

    6.提供根据下标获取方法(get(int i))、根据指定结点获取前一个结点方法(getPrior)、根据指定结点获取后一个结点信息方法(getNext)

    上面也说过,双向链表解决的问题就是在获取指定结点的上一个结点时是无需遍历链表的,这样大大节省了时间成本,这里就测试下该方法的实现。三个方法的实现如下所示:

        //根据下标获取
        public Object get(int i) throws Exception{
            return getNode(i).object;
        }
    
        //根据下标获取其前一个元素
        public Object getPrior(int i) throws Exception{
            return getNode(i).prior.object;
        }
    
        //根据下标获取其后一个元素
        public Object getNext(int i) throws Exception{
            return getNode(i).next.object;
        }
    
        public DupNode getNode(int i) throws Exception{
            if(i<0 || i>length())
                throw new Exception("下标不合法");
            DupNode node = head.next;
            int j =0;
            while(node.equals(head) && j<i){
                j++;
                node = node.next;
            }
            return node;
        }
    

    下面我们来测试下这三个方法是否正确,使用李四所在结点来进行测试,李四的下标应该是1,传入1分别运行三个方法,若是正确应该输出的是:李四、张三、王五,如下图可见结果正确。
    在这里插入图片描述

    三、总结

    1.链表的缺点

    线性表的两种实现顺序表、链表。相比于顺序表,链表的缺点就是查找元素比较慢,查找元素的时间复杂度是O(n),而顺序表的时间复杂度是O(1),在查找上顺序表要优于链表,链表查找慢,就是它的缺点了,但是双向循环链表在一定程度上减少了查找时的时间复杂度,但是依然是不及顺序表的查找效率的,所以具体的使用场景还是静态数据适合使用顺序表,动态数据适合使用链表。

    2.链表的优点

    顺序表在指定下标x位置插入元素,组需要后移n-x+1个元素,若是删除下标为x的数据元素,则需要向前移动n-x个数据元素,但是链表则不需要移动任何元素,链表需要做的只是找到对应的元素将指针域中的指针进行更新即可。链表的插入和删除的时间复杂度可以看成O(1),而顺序表插入和删除操作的都是O(n).所以链表的优点就是插入和删除比较快。

    3.如何使用链表

    所以综合链表的优点与缺点我们可以发现,顺序表更适合存储“静态”型数据,而链表更适合存储“动态”型数据,何为动态型呢,就是那些插入、删除操作比较频繁的数据。这类数据更适合使用链表存储。而数据结构不易改变的数据使用顺序表存储更合适。顺序表可类比java中的ArrayList,链表可类比java中的LinkedList。这两者都是顺序表与链表的典型应用。

    展开全文
  • Go实现双向链表

    2021-04-12 22:15:14
    本文介绍什么是链表,常见的链表有哪些,然后介绍链表...目录1、链表1.1 说明1.2 单向链表1.3 循环链表1.4 双向链表2、redis队列2.1 说明2.2 应用场景2.3 演示3、Go双向链表3.1 说明3.2 实现4、总结5、参考文献1、...

    本文介绍什么是链表,常见的链表有哪些,然后介绍链表这种数据结构会在哪些地方可以用到,以及 Redis 队列是底层的实现,通过一个小实例来演示 Redis 队列有哪些功能,最后通过 Go 实现一个双向链表。

    a184a7b0552b8f3522b4439186766e4e.png

    目录

    1、链表

    1.1 说明

    1.2 单向链表

    1.3 循环链表

    1.4 双向链表

    2、redis队列

    2.1 说明

    2.2 应用场景

    2.3 演示

    3、Go双向链表

    3.1 说明

    3.2 实现

    4、总结

    5、参考文献

    1、链表

    1.1 说明

    bd4d0e941e57d358f652c3b62c91b092.png

    链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(1)。

    链表有很多种不同的类型:单向链表,双向链表以及循环链表。

    优势:

    可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。链表允许插入和移除表上任意位置上的节点。

    劣势:

    由于链表增加了节点指针,空间开销比较大。链表一般查找数据的时候需要从第一个节点开始每次访问下一个节点,直到访问到需要的位置,查找数据比较慢。

    用途:

    常用于组织检索较少,而删除、添加、遍历较多的数据。

    如:文件系统、LRU cache、Redis 列表、内存管理等。

    1.2 单向链表

    链表中最简单的一种是单向链表,

    一个单向链表的节点被分成两个部分。它包含两个域,一个信息域和一个指针域。第一个部分保存或者显示关于节点的信息,第二个部分存储下一个节点的地址,而最后一个节点则指向一个空值。单向链表只可向一个方向遍历。

    单链表有一个头节点head,指向链表在内存的首地址。链表中的每一个节点的数据类型为结构体类型,节点有两个成员:整型成员(实际需要保存的数据)和指向下一个结构体类型节点的指针即下一个节点的地址(事实上,此单链表是用于存放整型数据的动态数组)。链表按此结构对各节点的访问需从链表的头找起,后续节点的地址由当前节点给出。无论在表中访问哪个节点,都需要从链表的头开始,顺序向后查找。链表的尾节点由于无后续节点,其指针域为空,写作为NULL。

    1.3 循环链表

    循环链表是与单向链表一样,是一种链式的存储结构,所不同的是,循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点,从而构成一个环形的链。

    循环链表的运算与单链表的运算基本一致。所不同的有以下几点:

    1、在建立一个循环链表时,必须使其最后一个结点的指针指向表头结点,而不是像单链表那样置为NULL。

    2、在判断是否到表尾时,是判断该结点链域的值是否是表头结点,当链域的值等于表头指针时,说明已到表尾。而非象单链表那样判断链域的值是否为NULL。

    1.4 双向链表

    18ba45b9ab7661f1ab4b4d102e23ed7b.png

    双向链表其实是单链表的改进,当我们对单链表进行操作时,有时你要对某个结点的直接前驱进行操作时,又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域,那么能不能定义一个既有存储直接后继结点地址的链域,又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢?这就是双向链表。

    在双向链表中,结点除含有数据域外,还有两个链域,一个存储直接后继结点地址,一般称之为右链域(当此“连接”为最后一个“连接”时,指向空值或者空列表);一个存储直接前驱结点地址,一般称之为左链域(当此“连接”为第一个“连接”时,指向空值或者空列表)。

    2、redis队列

    2.1 说明

    Redis 列表是简单的字符串列表,按照插入顺序排序。你可以添加一个元素到列表的头部(左边)或者尾部(右边)

    Redis 列表使用两种数据结构作为底层实现:双端列表(linkedlist)、压缩列表(ziplist)

    通过配置文件中(list-max-ziplist-entries、list-max-ziplist-value)来选择是哪种实现方式

    在数据量比较少的时候,使用双端链表和压缩列表性能差异不大,但是使用压缩列表更能节约内存空间

    2.2 应用场景

    消息队列,秒杀项目

    秒杀项目:

    提前将需要的商品码信息存入 Redis 队列,在抢购的时候每个用户都从 Redis 队列中取商品码,由于 Redis 是单线程的,同时只能有一个商品码被取出,取到商品码的用户为购买成功,而且 Redis 性能比较高,能抗住较大的用户压力。

    2.3 演示

    如何通过 Redis 队列中防止并发情况下商品超卖的情况。

    假设:

    网站有三件商品需要卖,我们将数据存入 Redis 队列中

    1、 将三个商品码(10001、10002、10003)存入 Redis 队列中

    # 存入商品

    RPUSH commodity:queue 10001 10002 10003

    复制代码

    2、 存入以后,查询数据是否符合预期

    # 查看全部元素

    LRANGE commodity:queue 0 -1

    # 查看队列的长度

    LLEN commodity:queue

    复制代码

    3、 抢购开始,获取商品码,抢到商品码的用户则可以购买(由于 Redis 是单线程的,同一个商品码只能被取一次

    )

    # 出队

    LPOP commodity:queue

    复制代码

    这里了解到 Redis 列表是怎么使用的,下面就用 Go 语言实现一个双向链表来实现这些功能。

    3、Go双向链表

    3.1 说明

    这里只是用 Go 语言实现一个双向链表,实现:查询链表的长度、链表右端插入数据、左端取数据、取指定区间的节点等功能( 类似于 Redis 列表的中的 RPUSH、LRANGE、LPOP、LLEN功能 )。

    3.2 实现

    a184a7b0552b8f3522b4439186766e4e.png

    节点定义

    双向链表有两个指针,分别指向前一个节点和后一个节点

    链表表头 prev 的指针为空,链表表尾 next 的指针为空

    // 链表的一个节点

    type ListNode struct {

    prev *ListNode // 前一个节点

    next *ListNode // 后一个节点

    value string // 数据

    }

    // 创建一个节点

    func NewListNode(value string) (listNode *ListNode) {

    listNode = &ListNode{

    value: value,

    }

    return

    }

    // 当前节点的前一个节点

    func (n *ListNode) Prev() (prev *ListNode) {

    prev = n.prev

    return

    }

    // 当前节点的前一个节点

    func (n *ListNode) Next() (next *ListNode) {

    next = n.next

    return

    }

    // 获取节点的值

    func (n *ListNode) GetValue() (value string) {

    if n == nil {

    return

    }

    value = n.value

    return

    }

    复制代码定义一个链表

    链表为了方便操作,定义一个结构体,可以直接从表头、表尾进行访问,定义了一个属性 len ,直接可以返回链表的长度,直接查询链表的长度就不用遍历时间复杂度从 O(n) 到 O(1)。

    // 链表

    type List struct {

    head *ListNode // 表头节点

    tail *ListNode // 表尾节点

    len int // 链表的长度

    }

    // 创建一个空链表

    func NewList() (list *List) {

    list = &List{

    }

    return

    }

    // 返回链表头节点

    func (l *List) Head() (head *ListNode) {

    head = l.head

    return

    }

    // 返回链表尾节点

    func (l *List) Tail() (tail *ListNode) {

    tail = l.tail

    return

    }

    // 返回链表长度

    func (l *List) Len() (len int) {

    len = l.len

    return

    }

    复制代码在链表的右边插入一个元素

    // 在链表的右边插入一个元素

    func (l *List) RPush(value string) {

    node := NewListNode(value)

    // 链表未空的时候

    if l.Len() == 0 {

    l.head = node

    l.tail = node

    } else {

    tail := l.tail

    tail.next = node

    node.prev = tail

    l.tail = node

    }

    l.len = l.len + 1

    return

    }

    复制代码从链表左边取出一个节点

    // 从链表左边取出一个节点

    func (l *List) LPop() (node *ListNode) {

    // 数据为空

    if l.len == 0 {

    return

    }

    node = l.head

    if node.next == nil {

    // 链表未空

    l.head = nil

    l.tail = nil

    } else {

    l.head = node.next

    }

    l.len = l.len - 1

    return

    }

    复制代码通过索引查找节点

    通过索引查找节点,如果索引是负数则从表尾开始查找。

    自然数和负数索引分别通过两种方式查找节点,找到指定索引或者是链表全部查找完则查找完成。

    // 通过索引查找节点

    // 查不到节点则返回空

    func (l *List) Index(index int) (node *ListNode) {

    // 索引为负数则表尾开始查找

    if index < 0 {

    index = (-index) - 1

    node = l.tail

    for true {

    // 未找到

    if node == nil {

    return

    }

    // 查到数据

    if index == 0 {

    return

    }

    node = node.prev

    index--

    }

    } else {

    node = l.head

    for ; index > 0 && node != nil; index-- {

    node = node.next

    }

    }

    return

    }

    复制代码返回指定区间的元素

    // 返回指定区间的元素

    func (l *List) Range(start, stop int) (nodes []*ListNode) {

    nodes = make([]*ListNode, 0)

    // 转为自然数

    if start < 0 {

    start = l.len + start

    if start < 0 {

    start = 0

    }

    }

    if stop < 0 {

    stop = l.len + stop

    if stop < 0 {

    stop = 0

    }

    }

    // 区间个数

    rangeLen := stop - start + 1

    if rangeLen < 0 {

    return

    }

    startNode := l.Index(start)

    for i := 0; i < rangeLen; i++ {

    if startNode == nil {

    break

    }

    nodes = append(nodes, startNode)

    startNode = startNode.next

    }

    return

    }

    复制代码

    4、总结

    到这里关于链表的使用已经结束,介绍链表是有哪些(单向链表,双向链表以及循环链表),也介绍了链表的应用场景(Redis 列表使用的是链表作为底层实现),最后用 Go 实现了双向链表,演示了链表在 Go 语言中是怎么使用的,大家可以在项目中更具实际的情况去使用。

    5、参考文献

    有疑问加站长微信联系(非本文作者)

    展开全文
  • 和单向链表不同的是,双链表除了有一个指向下一节点的指针外,还有一个指向前一节点的指针,这也就意味着,双向链表能够快速找到前驱节点,也能快速找到后驱节点。 和单向链表相比,对于插入或删除指定节点的操作,...

    双向链表的复杂度分析

    我们先看一下双向链表的的概念:

    它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。(摘抄自百度百科)

    和单向链表不同的是,双链表除了有一个指向下一节点的指针外,还有一个指向前一节点的指针,这也就意味着,双向链表能够快速找到前驱节点,也能快速找到后驱节点。

    和单向链表相比,对于插入或删除指定节点的操作,因为单向链表需要从头遍历定位到这个节点的前驱节点,所以它的平均复杂度是O(n)。而对于双向链表,因为知道了指定节点,就能马上知道它的前驱节点,所以它的复杂度是O(1)。

    那么,问题来了,既然双链表效率比单链表高,为什么还要保留单链表呢,甚至单链表的应用比双链表还要广泛?

    依我看,主要是因为以下几个方面:

    1、单链表的学习成本要双链表低,而且学习了单链表就能更好的理解双链表

    2、存储效率,每个双链表的节点要比单链表的节点多一个指针,也就意味着更高的内存开销,如果你对于效率和内存开销,更在意的是内存开销,又或者你的程序就没有指定节点插入或删除的操作,那这时候就可以用单链表。

    下面我们来对双链表进一步分析 !

    节点定义

    我们先来双向链表的节点定义:

    public class DoublyNode {
        int val;
        DoublyNode next;
        DoublyNode prev;
    
        DoublyNode(int element) {
            this.val = element;
        }
    }
    

    每个节点包含一个值val、前节点和后节点。(为了方便,这里直接以int作为val的类型)

    所以,它的链式结构大概是长这样的:… <-> A <-> B <-> C <-> …

    操作复杂度分析

    双向链表插入

    1、头插/尾插,O(1)

    头插和尾插的比较容易理解,因为双向链表内部会维护指向头部和尾部的指针的,所以找到头部和尾部的节点,并在前或后插入数据,只需要O(1)的复杂度。

    2、在指定节点前/后插入数据,O(1)

    对于这个操作,我们举个例子来理解一下:

    假设我们有一个双向链表:… <-> A <-> B <-> C <-> …现在我们要往【B】节点后插入【X】节点,即:… <-> A <-> B <-> X <-> C <-> …

    这个插入操作可以分为以下几个步骤:

    1、找到节点 B 的下一个节点,即 C (复杂度O(1),因为节点 B 已经存储了节点 C 的位置)
    2、插入节点 X 将 prev 指针指向节点 B, next 指针指向节点 C (O(1))
    3、修改节点 B 的 next 指针指向 X (O(1))
    4、修改节点 C 的 prev 指针指向 X (O(1))

    相加所得,时间复杂度为 O(1)

    3、找到值等于x的节点,并插入在其前/后插入数据,O(n)

    还是上面那个例子,相对于【在指定节点前/后插入数据】的操作来说,多了一个查找并定位节点 B 的操作,而等值查找操作在双向链表中的平均时间复杂度为 O(n), 故当前操作的时间复杂度也是 O(n)。

    双向链表的删除

    1、头删,O(1)

    2、尾删,O(1)

    3、删除指定节点前/后的数据,O(1)

    4、删除值为x的节点,O(n)

    删除和插入的操作同理,就不再赘述了。

    双向链表的查找

    1、查找值为x的节点,O(n)

    2、查找索引为x的节点,O(n)

    这个很好理解,跟单向链表一样,不管是按值查找还是按索引查找,都需要遍历取得对应值的节点,所以复杂度O(n)

    数组、单链表、双链表的时间复杂度对比表

    下面贴一个数组、单链表、双链表的时间复杂度对比表:

    展开全文
  • Java语言中链表和双向链表链表是一种重要的数据结构,在程序设计中占有很重要的地位。C语言和C++语言中是用指针来实现链表结构的,由于Java语言不提供指针,所以有人认为在Java语言中不能实现链表,其实不然,Java...
  • 1、链表dlist.h/**dlist.h*描述:*有头循环双表*Data:*2014-07-21*/#pragma once#include #include #include struct node_info{struct node_info *prev;struct node_info *next;char par[]; /*0长数组,不占空间*/};...
  • 队列 1、 先进先出 栈 1、先进后出 2、允许元素插入与删除的一端称为栈顶,另一端称为栈底 pop push 3、 在使用标准库的栈时,应该使用头文件: #include< stack > ,若定义 stack <int> s; ...
  • 前言 先复习一下几种数据结构吧。 链表,就是一个个结点,用指针的...双向队列,就是两端都能插入删除的队列,这个的实现需要双向链表。 循环队列,之前是list实现的,这里我们用一次node,结构基于循环链表。 双向
  • 实现双向链表结点插入双向链表结点删除双向链表基本实现二、双向链表应用再议双端队列双向链表实现双端队列在文章【数据结构与算法Python描述】——单向线性链表简介及其Python实现中,我们讨论了相对于列表,使用...
  • 手撸双链表,图解

    2021-03-28 00:10:46
    C语言,链表C++实现单向链表深入理解Linux内核链表跟单链表不同,双链表的节点包含两个指针,一个指针指向上一个元素,一个指针指向下一个元素。▌如下图学习数据结构的时候,要像认识一个人一...
  • 数据结构中的栈、队列链表应该是最基础的了,还有像是图、树、二叉树、最优二叉树/解等等也很重要,前端也要会数据结构是我没想到的,总结一下用JavaScript实现数据结构中的栈、队列链表中的双向链表
  • 我根据这些文件编写了无锁双向链表:“基于引用计数的高效可靠的无锁内存回收”,Anders Gidenstam,成员,IEEE,Marina Papatriantafilou,H˚akan Sundell和Philippas Tsigas“无锁双端队列双链表”,Philippas ...
  • 前言:初读此题,根据题意,顺势想到了用刚学的数据结构中的循环队列及循环链表,便想借此来熟练一下新学知识。 题目描述: 一群猴子要选新猴王。新猴王的选择方法是:让N只候选猴子围成一圈,从某位置起顺序编号...
  • 什么是双向循环链表在了解双向循环链表之前,如果对链表还没有一个清晰的概念,建议你看看单链表和单向循环链表,这有利于你更好的理解下面的内容。(废话有点多[逃]相比单链表,双向循环链表是一个更加...双向循环...
  • 他采用HashMap+双向链表实现LRU(淘汰掉最不经常使用的)。先来将原文简单引用介绍下,以免原作者删除。很久前参加过今日头条的面试,遇到一个题,目前半部分是如何实现 LRU,后半部分是 Redis 中如何实现 LRU。我的第...
  • 数据结构实验5_C语言_链队列的基本操作、入队、出队、获取队头元数据结构实验5_C语言_链队列的基本操作、入队、出队、获取队头元素等实验5、链队列的基本操作(1)实验目的通过该实验,使学生理解链队列的构造特点并...
  • LinkedList介绍 知识点 ...它也可以被当作堆栈、队列或双端队列进行操作。 LinkedList 的成员变量只有三个:头节点 first、尾节点 last、容量 size LinkedList 实现 List 接口,能对它进行队列操作。 Lin
  • 文章目录前言题目大意方法一:双端队列 + 启发式合并方法二:List模拟方法三:无向图dfs模拟(待补)方法四:splay解法(待补)方法五:treap解法(待补)代码仓库1.12.1 前言 这题做法很多。 1.双端队列 + 启发式合并. 2.List ...
  • 链表 树 图 哈希表 一. 数组 数组(Array)是最简单,也是最常用的数据结构了。其他一些数据结构,比如栈和队列都是由数组衍 生出来的。 每一个数组元素的位置称为下标或者索引(index)标识的。大多数编程语言的数组...
  • } }(4)双链表class Chain{ Chain pre=null,next=null; int id; String name; } class List{ private Chain header=new Chain(); public Chain add(int id,String name){ //在链表尾添加节点 Chain current=new ...
  • 和单链表相比,循环单链表的长处是从尾到链头比较方便。当要处理的数据元素序列具有环型结构特点时,适合于采用循环单链表。2、单向循环链表和单链表相同,循环单链表也有带头结点结构和不带头结点结构两种,带头...
  • 1)创建一个双向链表,该链表由Node和List类组成,Node类用于创建结点,List类负责整个链表的管理工作,需要定义指定的成员函数,用于实现对人员信息的增删改查。 2) 从List类派生出Set类,定义成员运算符重载函数,...
  • 链表和数组是数据类型中两个重要又常用的基础数据类型。数组是连续存储在内存中的数据结构,因此它的优势是可以通过下标迅速的找到元素的位置,而它的缺点则是在插入和删除元素时会导致大量元素的被迫移动,为了解决...
  • 通过该实验,使学生理解链队列的构造特点并灵活应用,掌握链队基本操作的编程实现,认识栈是在一端进行插入,在另一端进行删除集中操作的线性结构,掌握队列的“先入先出”操作特点,知道判断队列空和满的条件,...
  • 文章目录1.int epoll_create(int size) //...③rdlist成员被初始化成指向一个双向链表的根【有了这个根,就可以向双向链表中插入节点,或者说插入数据了】;2.int epoll_ctl(int efpd,int op,int sockid,struct epoll
  • 单向链表结构 单向链表定义 单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过从头部开始顺序读取。 自定义一个简单的单向链表结构 i.创建MyList接口 package CustomStructure; ...
  • 链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比...
  • LinkList(双向链表实现)

    2021-03-11 14:04:20
    linkedlist是用链表结构存储数据的,比较适合数据的动态插入和删除,随机访问和遍历速度比较慢,还提供了list接口i中没有定义的方法,专门用于操作表头和表尾的元素,所以可以当作堆栈、队列和双向队列来使用。...
  • 单端队列有数组和链表两种实现方式。数组的实现方式相对比链表复杂一些,需要理解数学关系。接下来,是时候实现双端队列了。简单介绍单端队列只能从一端插入元素,另一端取出元素。而双端队列则可以在两端均可以插入...
  • 队列是一个有序列表,可以使用数组或链表实现 一次性队列,不能复用: 数据满了之后,条件:rear==maxSize-1,不会改变(rear++) 数据取空了之后,条件:front==rear,不会改变(front++) 思路:队列(数组)最大...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 41,796
精华内容 16,718
关键字:

链队列双链表

友情链接: code.zip