Linked lists provide efficient node rearrangement and sequential node access, and can flexibly adjust the length of the list by adding and deleting nodes.

Linked lists are widely used in Redis. For example, one of the bottom implementations of list keys is linked lists. Redis uses linked lists as the underlying implementation of list keys when a list key contains a large number of elements, or when the list contains long strings of elements.

3.1 Implementation of linked lists and linked list nodes

Each linked listNode is represented using a listNode structure:

typedef struct listNode{
	// The front node
	struct listNode * prev;
	// back node
	struct listNode * next;
	// Node value
	void* the value; }listNode;Copy the code

Multiple ListNodes can form double-ended lists with prev and NEXT Pointers, as shown in the figure below:Although multiple listnodes can be used to form a list, it is more convenient to use the following list to form a list.

typedef struct list {
	// The first node of the list
	listNode * head;
	// The last node of the list
	listNode * tail;
	// The number of nodes in the list
	unsigned long len;
	// Node value copy function
	void *(*dup)(void *ptr);
	// Node value release function
	void (*free) (void *ptr);
	// Node value comparison function
	int (*match)(void *ptr,void *key);
} list;
Copy the code

The list structure provides the head pointer, tail pointer, and len length counter for the list, while the dUP, free, and match members are the type-specific functions needed to implement polymorphic lists:

  • The dUP function is used to copy the values stored by the linked list node.
  • The free function frees the value held by the linked list node;
  • The match function compares whether the values stored by the list nodes are equal to the values entered.

As shown in the figure, a linked list consists of a list structure and three listNode structures.The characteristics of Redis’s linked list implementation can be summarized as follows:

  • Double-ended: Linked list nodes have prev and next Pointers, and the complexity of obtaining the pre-node and post-node of a node is O(1).
  • Acyclic: The prev pointer on the head node and the next pointer on the tail node point to NULL, and access to the linked list ends at NULL.
  • With head pointer and tail pointer: through the head pointer and tail pointer of the list structure, the program obtains the head node and tail node of the linked list with O(1) time complexity.
  • List length counter: the program uses the len attribute of the list structure to perform technical operations on the list nodes held by the list. The program obtains the number of nodes in the list in a time complexity of O(1).
  • Polymorphic: Linked list nodes use void * Pointers to hold node values, and can be typed by the dUP, free, and match properties of the list structure. Therefore, linked lists can hold different types of values.

3.2 Apis for linked lists and linked list nodes

3.3 Key Reviews

  • Linked lists are widely used to implement redis features such as list keys, publish subscriptions, slow queries, and monitors.
  • Each linked listNode is represented by a listNode structure, and each node has a pointer to the front node and the back node, so the linked list of Redis is a bidirectional linked list.
  • Each list is represented by a list, which has a header pointer, a tail pointer, and the length of the list.
  • Redis implements acyclic lists because both the prev of the front node of the head node and the next of the back node point to NULL.
  • Redis lists can be used to store a variety of different types of values by setting different type-specific functions for the lists.