Let’s talk in depth about double linked lists in Redis

This article will take you to understand the double-linked list in the Redis data structure, and briefly introduce the use of double-linked lists. I hope it will be helpful to everyone!

In the list list of the Redis data type, the commonly used commands for adding and deleting data are lpush, rpush, lpop, rpop, among which l It means on the left side, r means on the right side. You can add and delete operations on the left and right sides, indicating that this is a two-way data structure, and the list data structure is a doubly linked list, similar to the LinekdList in Java. [Related recommendations: Redis Video Tutorial]

The linked list provides efficient node rearrangement capabilities and sequential node access methods. The data of the linked list can be modified by modifying the pre and next pointers of the nodes. .

The C language does not have a built-in linked list data structure, so Redis builds its own linked list structure.

Data structure of linked list, linked list and linked list nodes

The linked list is composed of linked list and linked list nodes. Each linked list node is represented by a adlist.h/listNode structure :

typedef struct listNode {
    //前置节点
    struct listNode *prev;
    //后置节点
    struct listNode *next;
    // 节点值
    void *value;
} listNode;

Multiple listNodes can form a double linked list through prev and next pointers, as shown in the title:

##Multiple listNodes can form a linked list, but in order To facilitate management, use

adlist.h/list to manage the linked list. The list structure is as follows:

typedef struct list {
    // 列表头结点
    listNode *head;
    // 列表尾结构
    listNode *tail;
    // 节点值复制函数
    void *(*dup)(void *ptr);
    // 节点值释放函数
    void (*free)(void *ptr);
    // 节点值对比函数 
    int (*match)(void *ptr, void *key);
    // 列表节点数量
    unsigned long len;
} list;

list structure provides the head pointer head, the tail pointer tail, and the node number calculation len for the linked list. . The following figure shows a linked list consisting of a list structure and three listNode nodes:

The characteristics of the Redis linked list implementation are summarized as follows:

Bidirectional: The linked list nodes have prev and next pointers, and each data can be obtained through the pointers
• Quickly calculate the length of the linked list: Calculate the length of the list through the len attribute in the list structure, and the time complexity is O(1)
• Polymorphism: Linked list nodes use void* pointers to save nodes, so linked lists support saving various types of values

Use of double linked lists

List keys, Publish and subscribe, slow queries, monitors, etc.

Summary

This article introduces the data structure of the linked list. The linked list is composed of linked lists and linked list nodes.
• The linked list nodes have a front and rear pointers. , so the linked list of Redis is a two-way linked list
• The linked list can store the head node and the tail node to better manage its own nodes. The len attribute can quickly calculate the length of the linked list
• The linked list passes void* And different type setting functions, so the linked list can have different types of values

For more programming-related knowledge, please visit:

Introduction to Programming! !

The above is the detailed content of Let’s talk in depth about double linked lists in Redis. For more information, please follow other related articles on the PHP Chinese website!