This is the fourth time I have participated in the August Challenge
review
The previous article implemented a stack using dynamic arrays. An obvious disadvantage of dynamic array is that it will cause obvious waste of memory space. For example, when slicing the underlying array in Golang, the memory space occupied by the original array will be expanded by 1.25 times when the array capacity is insufficient. Sometimes I add just one element, and that element takes up a quarter of the memory of the original array.
The list
In order to solve the memory waste of dynamic arrays, linked lists can stand out, as much memory can be allocated. A linked list is a chained storage structure in which the memory addresses of all elements are not necessarily contiguous. But there are three types of lists: unidirectional, bidirectional, and circular. Let’s start with simple one-way lists, because one-way lists are the most common.
One-way linked list method
Singly linked list is some of the ways and the dynamic array is the same, singly linked list node structure basically has two parts, namely the data fields and a pointer, the pointer to the position of the next element in the memory is, the list is also a sequential storage structure, but the memory address is not necessarily the order of the elements, Let’s also implement a linked list structure with Golang:
package main
import (
"errors"
"fmt"
)
// Define a node
type Node struct {
Data string // The storage type of the node is string
NextData *Node // Store the pointer to the next node
}
// Define a one-way list structure
type LinkedList struct {
Head *Node // The head node points to the actual top of the stack
}
func makeLinkedList(a) *LinkedList {
return &LinkedList{}
}
// Check whether the list is empty
func (l *LinkedList) isEmpty(a) bool {
return l.Head == nil
}
// Return the top element of the stack
func (l *LinkedList) top(a) interface{} {
if l.isEmpty() { // Indicates that the stack is empty
return errors.New("Stack empty")}return l.Head.Data // Top of stack element
}
/ / into the stack
func (l *LinkedList) push(value string) {
newNode := &Node{Data: value} // The value is pushed to create a new node
if l.isEmpty() {
l.Head = newNode // empty the head to point to the latest
} else {
/ / not be empty
cur := l.Head
// Iterate over the node until it reaches the last node. When the pointer to the next node is empty, the pointer points to the newly added node
forcur.NextData ! =nil {
cur = cur.NextData
}
// Update the new node
cur.NextData = newNode
}
}
// remove the tail element
func (l *LinkedList) pop(a) interface{} {
cur := l.Head // Get the head node
if cur.NextData == nil {
return nil
} else {
for cur.NextData == nil { // If the next node is empty, then the value of the current node is the value of the next node
cur = cur.NextData.NextData
}
cur.NextData.NextData = nil // Delete the pointer to the last node
}
return nil
}
func main(a) {
list := makeLinkedList()
list.push("hello~")
list.push("world~")
list.push("I'm a dirt digger.")
// iterate over a few points
cur := list.Head
forcur ! =nil {
fmt.Println(cur.Data)
cur = cur.NextData
}
fmt.Printf("Current head value: %s\n", list.top())
list.pop()
cur = list.Head
forcur ! =nil {
fmt.Println(cur.Data)
cur = cur.NextData
}
}
Copy the code
conclusion
Their implements a linked list to delete the last node example, actually list and there are many methods, such as delete specified value node, specify the location of the node, and determine whether a value in the list, is often used to the interview, we slowly to, the beginning of the first simple, below to compare the difference between linked list and array.