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.