Getting started with redis - Chapter 2 - data structures and objects - linked lists

The list is in Redis It is widely used in , For example, one of the underlying implementations of the list key is the linked list . When a list key contains a large number of elements , Or when the elements in the list are relatively long strings ,Redis Will use the linked list as the underlying implementation of the list key .

The realization of linked list and linked list node ：

typedef struct listNode {
struct listNode * prev; //  Front node pointer 
struct listNode * next; //  Post node pointer 
void * value;           //  Node values 
}listNode;

typedef struct list {
listNode * head;                     //  Header node 
listNode * tail;                     //  Tail node 
unsigned long len;                   //  Number of nodes 
void *(*dup)(void *ptr);             //  Node copy function 
void (*free)(void *ptr);             //  Node release function 
void (*match)(void *ptr, void *key); //  Node value comparison function 
}list;

Redis The linked list implementation of can be summarized as ：

• Two ends ： Linked list nodes have prev and next The pointer , The time complexity of obtaining the pre node and post node of a node is O(1)
• acyclic ： Of the header node prev And at the end of the table next The hands all point to NULL, Access to the linked list NULL End point
• Pointer with header and footer ： adopt list Of head and tail Property to obtain the header and footer nodes. The time complexity is O(1) 
• With linked list length counter ： adopt  list Of len attribute , The time complexity of obtaining the number of linked list nodes is O(1) 
• polymorphic ： Linked list usage void * Pointer to save the node value , And through list Structural dup、free、match Three properties set type specific functions for node values , So linked lists can be used to store various types of data