「初心者」Golang の二重リンクリスト(Doubly-Linked List)（英語）

Although list has rarely been used in Go (Just about always when you are thinking of a list - use a slice instead in Go), there is an official implementation in the standard library. After reading the implementation (go standard package: src/container/list/list.go), I found it very inspiring.

The Node

Basically, it first defines Node, which is referred to as Element in the standard package:

type Element struct {
    prev, next Element
    list *List
    Value interface{} 
}

It is actually a structure we create a lot when solving linked list problems in websites like LeetCode. The difference is:

1. One single Element simultaneously points to TWO other elements, as it is a double-linked list(or doubly linked list).
2. It has a field pointing to list, which can be very convenient when we want to decide whether an element belongs to a list.

The List

Then the list part:

type List struct {
    root Element
    len int
}

It has only two fields: a root of the list, and the length of the list.

The interesting part: The root is not the most front Element of the list, but an empty element pointing to the beginning element of the list. It is the so-called Sentinel.

The Sentinel Element

Sentinel is a very common practice when dealing with linked-list. Because we usually have to do some operations like remove or insert a head node to the linked list. It can be helpful to have a static node on which we can always rely.

But here, the sentinel is even more helpful, as it is not only pointer to the beginnig Element of the list, but also the ending Element of the list. We can conclude from following code:

// Front returns the first element of list l or nil if the list is empty.
func (l *List) Front() *Element {
	if l.len == 0 {
		return nil
	}
	return l.root.next
}

// Back returns the last element of list l or nil if the list is empty.
func (l *List) Back() *Element {
	if l.len == 0 {
		return nil
	}
	return l.root.prev
}

Therefore considering the existence of the sentinel Element, we are actually having a hypothetical circle. The sentinel Element connects the beginning and the end of the double-linked list.

We do not need to keep two fields to point to the beginning and the end Element of the list anymore -- the root Element can handle all of these.

What Can List Do For Us

Although it's been said at the beginning of this article, list has rarely been used in Go. It can be replaced in most situations simply by Slice. However, I do think up with a certain situation where it can be adopted: The LRU cache.

If you do not have a clue about what an LRU is, please refer to this article.

So what kind of structure do we need to implement an LRU in Go?

Consider when a key got hit in LRU, we often assume that it can be frequently accessed, so we need to move it to the front of our structure.

On the other hand, if the capacity is full and we need to add a new key to the structure, we also need to quickly drop out the oldest key at the end of our structure.

In this situation, a double-linked list can achieve the above two operations very effectively.