How to implement a double-linked list with a single pointer? Want to solve this problem, we need the matting of a few thinking, cent below 3 steps, from shallow to deep zone you realize!

Normal: Implements a single linked list

There are many implementations of single linked lists on the Internet, and the design is not the same for practicality. So let’s pick the most straightforward one.

show me the code

Gist.github.com/RBowind/156…

//Element lists each node in a single list
type Element struct {
	next  *Element  // Index the next node
	Value interface{}}type List struct {
	root *Element // The entire list
	tail *Element // Index the last node for push
	len  int // The length of a single list
}

Copy the code

Abnormal: implement a single linked list with a single pointer address

Assuming that I feel that the structure above is deeply nested and looks uncomfortable (😊), then I can change the next of the head node to PTR, which points to the address of the pointer to the next node, and then the PTR of the next node points to the address of the pointer to the next node.

next *Element  ==>  ptr uintptr
Copy the code

show me the code

Gist.github.com/RBowind/4d3…


type Element struct { 
	ptr   uintptr  // A pointer to the next node
	Value interface{}}type List struct {
	root *Element
	tail uintptr
	len  int
}

Copy the code

More abnormal: a single pointer implements a double-linked list

First understand the idea of using a single pointer address to implement a single linked list, and then look at it.

Use xOR: a⨁(a⨁b)=ba \bigoplus (a \ Bigoplus b)=ba ⨁(a⨁b)=b

The PTR of each node no longer stores the pointer address of the next node, but rather the xor result of the pointer address of the previous node and the pointer address of the next node.

The PTR of P0 is the xor of the pointer to the previous node 0 and the pointer to the next node P1, as is the logic for P1 and P2. In this way, you can traverse both sequentially and in reverse order.


P 0 ⨁ ( P 0 ⨁ P 2 ) = P 2 P0\bigoplus(P0\bigoplus P2) = P2 
0 ^ ( 0 ^ P1 ) = P1 // where 0 ^ P1 is the PTR stored on P0
P0 ^ (P0 ^ P2) = P2 // where P0 ^ P2 is PTR stored on P1
Copy the code

show me the code

Gist.github.com/RBowind/f7d…


type Element struct {
	ptr   uintptr
	Value interface{}}type List struct {
	root *Element
	tail uintptr
	len  int
}

/ /... Check out the gist above for more details

func (l *List) insert(e *Element, tail uintptr) *Element {
	if l.len= =0 {
		l.root.Value = e.Value
		l.root.ptr = 0
		l.tail = uintptr(unsafe.Pointer(l.root))
	} else {
		tailElement := (*Element)(unsafe.Pointer(tail)) // Get the latest tail node
		tailElement.ptr = tailElement.ptr ^ uintptr(unsafe.Pointer(e)) // change the pointer to the tail node
		e.ptr = tail // The PTR of the inserted node holds the pointer to the last node, which is the next inserted tailelement.ptr
		l.tail = uintptr(unsafe.Pointer(e)) // point tail to the latest node
	}
	l.len++
	return e
}
Copy the code

defects

This structure also has its drawbacks, such as sequential/reverse order, starting from the beginning/end, and simply giving P1 nodes, it is difficult to get P0 and P2. However, this is also a two-way list, which is just a kind of thinking, so it is not practical at present.