Redis の二重リンクリストについて詳しく話しましょう-Redis-php.cn

Redis の二重リンクリストについて詳しく話しましょう

青灯夜游

リリース： 2021-12-01 09:53:25

転載

2152 人が閲覧しました

この記事では、Redis データ構造の二重リンクリストを理解し、二重リンクリストの使用方法を簡単に紹介します。

Redis の二重リンクリストについて詳しく話しましょう

Redis データ型の list list では、データの追加と削除によく使用されるコマンドは、lpush、rpush、lpop、rpop です。 l は左側を意味し、r は右側を意味します。左側と右側で操作を追加および削除できます。これは、これが双方向のデータ構造であり、リストのデータ構造が二重リンクリストであることを示します、Java の LinekdList に似ています。 [関連する推奨事項: Redis ビデオチュートリアル ]

リンクリストは、効率的なノード再配置機能と順次ノードアクセス方法を提供します。リンクリストのデータは、pre および next ポインターを変更することで変更できます。ノードの。

C 言語には組み込みのリンクリストデータ構造がないため、Redis は独自のリンクリスト構造を構築します。

リンクリスト、リンクリスト、リンクリストノードのデータ構造

リンクリストはリンクリストとリンクリストノードで構成され、各リンクリストノードは adlist で表されます。 h/listNode 構造 :

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

ログイン後にコピー

タイトルに示すように、複数の listNode は prev ポインターと next ポインターを介して二重リンクリストを形成できます。 listNodes はリンクリストを形成できますが、管理を容易にするために、

adlist.h/list

を使用してリンクリストを管理します。リストの構造は次のとおりです: Redis の二重リンクリストについて詳しく話しましょう

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 構造は、ヘッドポインタhead、テールポインタtail、およびリンクリストのノード番号計算len。次の図は、リスト構造と 3 つの listNode ノードで構成されるリンクリストを示しています。

#Redis リンクリスト実装の特徴は次のように要約されます。

# 双方向: リンクリストノードには前ポインタと次ポインタがあり、各データはポインタを介して取得できます。

リンクリストの長さをすばやく計算します: len 属性を使用してリストの長さを計算しますリスト構造内での時間計算量は O(1) Redis の二重リンクリストについて詳しく話しましょう