Parlons en profondeur des listes doubles chaînées dans Redis

Cet article vous fera comprendre la liste doublement chaînée dans la structure de données Redis et présentera brièvement l'utilisation des listes doublement chaînées. J'espère qu'il sera utile à tout le monde !

Dans la list du type de données Redis, les commandes couramment utilisées pour ajouter et supprimer des données sont lpush, rpush, lpop, rpop, où l signifie à gauche, r signifie à droite, et peut être à gauche ou à droite Les opérations d'ajout et de suppression des deux côtés indiquent qu'il s'agit d'une structure de données bidirectionnelle, et la structure de données de liste est une liste doublement chaînée, similaire à LinekdList en Java. [Recommandations associées : Tutoriel vidéo Redis]

La liste chaînée offre des capacités efficaces de réarrangement des nœuds et un accès séquentiel aux nœuds. Les données de la liste chaînée peuvent être modifiées en modifiant les pointeurs pré et suivant des nœuds.

Le langage C n'a pas de structure de données de liste chaînée intégrée, donc Redis crée sa propre structure de liste chaînée.

La structure des données de la liste chaînée, de la liste chaînée et des nœuds de liste chaînée

La liste chaînée est composée de la liste chaînée et des nœuds de liste chaînée. Chaque nœud de liste chaînée est représenté par un adlist.h/listNode. structure :

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

Plusieurs listNodes peuvent être transmis via prev et next. Les pointeurs forment une double liste chaînée, comme indiqué dans le titre :

Plusieurs listNodes peuvent former une liste chaînée, mais pour la commodité de la gestion, utilisez adlist .h/list pour gérer la liste chaînée. La structure de la liste est la suivante :

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 fournit une liste chaînée. La tête du pointeur, la queue du pointeur et la longueur de calcul du numéro de nœud sont incluses. La figure suivante montre une liste chaînée composée d'une structure de liste et de trois nœuds listNode :

Les caractéristiques de l'implémentation de la liste chaînée Redis sont résumées comme suit :

• Bidirectionnel : les nœuds de liste chaînée ont des pointeurs prev et next, et chaque pointeur peut être obtenu via le pointeur. Une donnée
• Calculez rapidement la longueur de la liste chaînée : calculez la longueur de la liste via l'attribut len ​​dans la structure de la liste, et la complexité temporelle est O(1)
• Polymorphisme : les nœuds de liste chaînée utilisent des pointeurs void* pour enregistrer les nœuds, de sorte que la liste chaînée prend en charge l'enregistrement de divers types de valeurs

Utilisation de listes chaînées doubles

Clés de liste, publication et abonnement, requêtes et moniteurs lents, etc. .

Résumé

• Cet article présente la structure de données de la liste chaînée. La liste chaînée est composée de listes chaînées et de nœuds de liste chaînée
• Les nœuds de liste chaînée ont un pointeur avant et arrière, donc la liste chaînée Redis est un deux. -way linked list
• La liste chaînée peut être stockée nœud principal, nœud de queue, mieux gérer vos propres nœuds, l'attribut len ​​calcule rapidement la longueur de la liste chaînée
• La liste chaînée utilise void* et différentes fonctions de configuration de type, donc la liste chaînée peut avoir différents types de valeurs

Plus de programmation Pour des connaissances connexes, veuillez visiter : Introduction à la programmation ! !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!