Golang double-linked list implementation code example

Implementation of double-linked lists

Basic concepts

Each node stores pointers to the previous and next nodes

Implementation ideas

Create a node structure

Each node has an upper node pointer and a lower node pointer
Each node has a key => value

Create a linked list structure

Linked list capacity size attribute
Linked list size attribute
Linked list locks to achieve concurrency security
Linked list header node
The node at the end of the linked list

Implement linked list operation method

Add header node operation AppendHead
Add tail node operation AppendTail
Append the tail node operation Append
Insert any node operation
Remove any node operation
RemoveHead operation
Remove Tail node operation RemoveTail
Get the node at the specified location
Search any node
GetSize
Print all node operations Print
Reverse all node operations

Summarize

Learning algorithms is a process of continuous accumulation
When learning, you need to be united in knowledge and action
More use case testing is required during implementation.

Code parsing

Define the structure of the node

type DoubleNode struct {
  Key  int     //key  Value interface{} //value  Prev *DoubleNode //Previous node pointer  Next *DoubleNode //Next node pointer  Freq int     //Frequency times. For use by LFU}

Define a double-linked list structure

//Define the structure of a double-linked listtype DoubleList struct {
  lock   * //Lock  Capacity uint     //Maximum capacity  Size   uint     //Current capacity  Head   *DoubleNode  //Head node  Tail   *DoubleNode  //Tail node}

First double-linked table

//First double-linked tablefunc New(capacity uint) *DoubleList {
  list := new(DoubleList)
   = capacity
   = new()
   = 0
   = nil
   = nil
  return list
}

Add header nodes

Implementation ideas

First determine the capacity
Determine whether the head is empty,
1. If empty, add a new node
2. If not empty, change the existing node and add

func (list *DoubleList) AddHead(node *DoubleNode) bool {
  //Judge whether the capacity is 0  if  == 0 {
    return false
  }
  ()
  defer ()
  //Judge whether the head node is nil  if  == nil {
     = node
     = node
  } else { //There is a header node     = node //Point a node on the old head node to the new node     =  //The next node of the new head node points to the old head node     = node   //Set new header node     = nil //Set NIL on the previous node of the new head node  }
  ++
  return true
}

Add tail element

Implementation ideas

First determine the capacity
Determine whether the tail is empty,
- If empty, add a new node
- If not empty, change the existing node and add

func (list *DoubleList) AddTail(node *DoubleNode) bool {
  //Judge whether there is capacity,  if  == 0 {
    return false
  }
  ()
  defer ()
  //Judge whether the tail is empty  if  == nil {
     = node
     = node
  } else {
    //The next node in the old tail points to the new node     = node
    // When adding a new node, first point the upper node of the node to the old tail node     = 
    //Set new tail node     = node
    //The next node in the new tail is set to empty     = nil
  }
  //Double-linked list size +1  ++
  return true
}

Add elements anywhere

Implementation ideas

Determine capacity size
Determine the size of the linked list
First: If the insertion position is greater than the current length, the tail will be added
The second type: If the insertion position is equal to 0, add the header
The third type: Insert node
- First take out the node to be inserted, and falsely adjust it to node C
- Between A and C, insert a node B
- The lower node of A should be B, that is, the lower node of C is B
- The upper node of B is the upper node of C
- The next node of B is C

//Add elements anywherefunc (list *DoubleList) Insert(index uint, node *DoubleNode) bool {
  //The capacity is full  if  ==  {
    return false
  }
  //If there is no node  if  == 0 {
    return (node)
  }
  //If the insertion position is greater than the current length, the tail will be added  if index &gt;  {
    return (node)
  }
  //If the insertion position is equal to 0, add the header  if index == 0 {
    return (node)
  }
  //Retrieve the node to be inserted at the position  nextNode := (index)
  ()
  defer ()
  //Insert in the middle:  //Suppose there are already nodes A and C, and now you need to insert node B  // nextNode is the C node,  //The lower node of A should be B, that is, the lower node of C is B   = node
  //The upper node of B is the upper node of C   = 
  //The next node of B is C   = nextNode
  //The upper node of C is B   = node
  ++
  return true
}

Delete the head node

Implementation ideas

Determine whether the head is empty
Take out the head node
Determine whether there is a next node in the head
1. There is no next node, which means there is only one node. If you delete it, you don't need to move the pointer position.
2. If there is a next node, the next node in the head is the head node.

//Delete the head nodefunc (list *DoubleList) RemoveHead() *DoubleNode {
  //Judge whether the head node is empty  if  == nil {
    return nil
  }
  ()
  defer ()
  //Take the head node out  node := 
  //Judge whether there is a next node in the head  if  != nil {
     = 
     = nil
  } else { //If there is no next node, there is only one node    ,  = nil, nil
  }
  --
  return node
}

Delete the tail node

Implementation ideas

Determine whether the tail node is empty
Remove the tail node
Determine whether the previous node of the tail node exists
1. Does not exist: It means there is only one node, and you need to delete it, and there is no need to move the pointer position.
2. If there is a previous node, the last node at the tail is the tail node.

//Delete the tail nodefunc (list *DoubleList) RemoveTail() *DoubleNode {
  //Judge whether the tail node is empty  if  == nil {
    return nil
  }
  ()
  defer ()
  //Retrieve the tail node  node := 
  //Judge whether the previous one of the tail node exists  if  != nil {
     = 
     = nil
  }
  --
  return node
}

Delete any element

Implementation ideas

Determine whether it is a head node
Determine whether 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. Element deletion is implemented.
1. Point the next node pointer of the previous node to the next node
2. Point the previous node pointer of the next node to the upper node

//Delete any elementfunc (list *DoubleList) Remove(node *DoubleNode) *DoubleNode {
  //Judge whether it is a head node  if node ==  {
    return ()
  }
  //Discern whether it is a tail node  if node ==  {
    return ()
  }
  ()
  defer ()
  //The node is an intermediate node  //There is required:  //Point the next node pointer of the previous node to the next node  //Point the previous node pointer of the next node to the upper node   = 
   = 
  --
  return node
}

View the full source code

The above is all the content of this article. I hope it will be helpful to everyone's study and I hope everyone will support me more.