This is the sixth day of my participation in the August More text Challenge. For details, see: August More Text Challenge

preface

We talked about an implementation of the SDS character set in Redis, but today we’re going to talk about the underlying implementation of arrays, another data type in Redis.

For array structures, one of the underlying implementations is a linked list. Today we will look at how the list is implemented in Redis.

Linked list and linked list node implementation

Similarly, the structure of a linked list node is very simple

type listNode struct {
    Prev *listNode // Front node
    Next *listNode // Rear node
    Value interface{} // The value of the node
}
Copy the code

From the structure, we can know that multiple nodes are connected to each other through the front and back Pointers, that is, through Prev and Next to achieve a double-ended linked list structure.

Operation chain table

The list is actually through a large number of linked list nodes connected together, a data structure, so let’s take a look at a bottom implementation of the list

type List struct {
    Head *listNode // Header node
    Tail *listNode // Table tail node
    Len  int // Number of nodes in the list
}
Copy the code

In addition, the struct has three built-in methods: dup, free, and match.

Summary of linked list features

In fact, the implementation of the list can be summed up into four points:

  1. Double-ended, as you can see, each list node has a prev and a next pointer, so the complexity is O(1) when you get a node before or after it.

2. Acyclic: A linked list node refers to both the head node and the end node of the table as Null, so the access is Null.

3. With the length of the list: this is similar to the implementation of SDS, which stores a length of the list in the struct itself.

  1. Polymorphism: The only value a linked list can hold is interface, that is, any value can hold as a linked list.

The last

The implementation of the list has been applied to redis to achieve a variety of functions, not only the regular list of keys, and publish subscription and so on, are through the list to achieve.