# golang double linked list implementation code example

• 2020-07-21 08:27:52
• OfStack

The realization of double linked list

The basic concept

Each node stores Pointers to the previous and next nodes

Implementation approach

Create 1 node structure

Each node has a pointer to the upper node and a pointer to the lower node Each node has 1 key = > value

Implement the linked list operation method

Add the header node operation AppendHead Add a tail node to operate AppendTail Append the tail node to operate Append Insert any node to operate Insert Remove any node operation Remove Remove the header node operation RemoveHead Remove the tail node operation RemoveTail Gets the node Get at the specified location Search for any node Search Gets the linked list size GetSize Print all node operations Print Reverse all node operations Reverse

conclusion

Learning algorithm well is a process of continuous accumulation When learning, we also need to combine knowledge and practice 1 Implementation requires more use case testing.

Code parsing

Defines the structure of a node

``````
type DoubleNode struct {
Key  int     // key
Value interface{} // value
Prev *DoubleNode // on 1 Node pointer
Next *DoubleNode // Under the 1 Node pointer
Freq int     // Number of frequency . In order to give LFU The use of
}
``````

Defines the structure of a double linked list

``````
// define 1 A double linked list structure
type DoubleList struct {
lock   *sync.RWMutex // The lock
Capacity uint     // The maximum capacity
Size   uint     // Current capacity
Tail   *DoubleNode  // The tail node
}
``````

Make a double linked list at the beginning

``````
// Make a double linked list at the beginning
func New(capacity uint) *DoubleList {
list := new(DoubleList)
list.Capacity = capacity
list.lock = new(sync.RWMutex)
list.Size = 0
list.Tail = nil
return list
}
``````

Implementation approach

Determine the capacity first To determine if the head is empty, If null, add a new node If not null, change the existing node and add
``````
// Determine if the capacity is 0
if list.Capacity == 0 {
return false
}
list.lock.Lock()
defer list.lock.Unlock()
// Determines whether the header node is nil
list.Tail = node
} else { // There are header nodes
list.Head.Prev = node // Put the old header node on 1 Five nodes point to a new node
node.Next = list.Head // Under the new head node 1 Three nodes point to the old header node
list.Head.Prev = nil // Put a new header node on it 1 Node setting NIL
}
list.Size++
return true
}
``````

Implementation approach

Determine the capacity first To determine whether the tail is empty, If null, add a new node If not null, change the existing node and add
``````
func (list *DoubleList) AddTail(node *DoubleNode) bool {
// Determine if there is capacity ,
if list.Capacity == 0 {
return false
}
list.lock.Lock()
defer list.lock.Unlock()
// Determine if the tail is empty
if list.Tail == nil {
list.Tail = node
} else {
// The next node in the old tail points to the new node
list.Tail.Next = node
// When a new node is appended , First the node The previous node points to the old tail node
node.Prev = list.Tail
// Set the new tail node
list.Tail = node
// The next node in the new tail is set to null
list.Tail.Next = nil
}
// Double linked list size +1
list.Size++
return true
}
``````

Implementation approach

Determine capacity size Determine the size of the list Type 1: The tail is added if the inserted position is greater than the current length Type 2: If the insertion position is equal to 0, the header is added Type 3: Intermediate insertion node First extract the node to be inserted, and pretend to be C node One B node is inserted between A and C The lower node of A should be B, that is, the upper node of C should be B The upper node of B is the upper node of C The next node of B is C
``````
func (list *DoubleList) Insert(index uint, node *DoubleNode) bool {
// Capacity is full
if list.Size == list.Capacity {
return false
}
// If there are no nodes
if list.Size == 0 {
return list.Append(node)
}
// The tail is added if the inserted position is greater than the current length
if index > list.Size {
}
// If the insertion position is equal to 0 the , Add the head
if index == 0 {
}
// Fetch the node at the position to be inserted
nextNode := list.Get(index)
list.lock.Lock()
defer list.lock.Unlock()
// The middle insert :
// Assumptions have been A, C node ,  Now I'm gonna insert B node
// nextNode That is C node ,
//A The next node should be B,  namely C The lower node of the upper node of is B
nextNode.Prev.Next = node
//B The last node of theta is theta C On the node
node.Prev = nextNode.Prev
//B The next node is C
node.Next = nextNode
//C The last node of theta is theta B
nextNode.Prev = node
list.Size++
return true
}
``````

Implementation approach

Determine if the head is empty Remove the head node Determines whether the header has the next node If there is no next node, it means there is only one node, so the pointer position need not be moved when deleting itself If there is a next node, the next node under the head is the head node.
``````
func (list *DoubleList) RemoveHead() *DoubleNode {
// Determines whether the header node is empty
return nil
}
list.lock.Lock()
defer list.lock.Unlock()
// Determine if the head is down 1 A node
if node.Next != nil {
} else { // If it doesn't 1 A node ,  That only 1 A node
}
list.Size--
return node
}
``````

Delete tail node

Implementation approach

Determine if the tail node is empty Take out the tail node Determines whether the previous node of the tail node exists If it does not exist, it indicates that there is only 1 node, so it is unnecessary to move the pointer position when deleting itself If the previous node exists, the previous node of the tail is the tail node.
``````
// Delete tail node
func (list *DoubleList) RemoveTail() *DoubleNode {
// Determine if the tail node is empty
if list.Tail == nil {
return nil
}
list.lock.Lock()
defer list.lock.Unlock()
// Take out the tail node
node := list.Tail
// Determine the top of the tail node 1 Whether or not
if node.Prev != nil {
list.Tail = node.Prev
list.Tail.Next = nil
}
list.Size--
return node
}
``````

Delete any element

Implementation approach

Determine if it is a header node Determine if it is a tail node Otherwise, it is an intermediate node, and the pointer position of the upper and lower nodes needs to be moved Points the next node pointer from the previous node to the next node Points the upper node pointer of the next node to the upper node
``````
// Delete any element
func (list *DoubleList) Remove(node *DoubleNode) *DoubleNode {
// Determine if it is a header node
}
// Determine if it is a tail node
if node == list.Tail {
return list.RemoveTail()
}
list.lock.Lock()
defer list.lock.Unlock()
// The nodes are intermediate nodes
// You need to :
// Will be on 1 The bottom of the node 1 The node pointer points to the lower node
// Will the 1 On a node 1 The node pointer points to the upper node
node.Prev.Next = node.Next
node.Next.Prev = node.Prev
list.Size--
return node
}
``````

View the complete source code

Related articles: