golang double linked list implementation code example

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

Create 1 linked list structure

Linked list size property Linked list size property Linked list lock, to achieve concurrent security Link head node List tail node

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 
  Head   *DoubleNode  // Head node 
  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.Head = nil
  list.Tail = nil
  return list
}

Add header node

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

func (list *DoubleList) AddHead(node *DoubleNode) bool {
  // 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
  if list.Head == nil {
    list.Head = node
    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 = node   // Set a new header node 
    list.Head.Prev = nil // Put a new header node on it 1 Node setting NIL
  }
  list.Size++
  return true
}

Add a tail element

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
    list.Head = 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
}

Add any location element

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

// Add any location element 
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 {
    return list.AddTail(node)
  }
  // If the insertion position is equal to 0 the , Add the head 
  if index == 0 {
    return list.AddHead(node)
  }
  // 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
}

Delete header node

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.

// Delete header node 
func (list *DoubleList) RemoveHead() *DoubleNode {
  // Determines whether the header node is empty 
  if list.Head == nil {
    return nil
  }
  list.lock.Lock()
  defer list.lock.Unlock()
  // Remove the head node 
  node := list.Head
  // Determine if the head is down 1 A node 
  if node.Next != nil {
    list.Head = node.Next
    list.Head.Prev = nil
  } else { // If it doesn't 1 A node ,  That only 1 A node 
    list.Head, list.Tail = nil, nil
  }
  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 
  if node == list.Head {
    return list.RemoveHead()
  }
  // 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