A linked list is like an interlocking chain that links data from each node together

In addition to storing node values, each data node also stores the address pointer of the next node, so that the next node can be searched through this node. Even if the actual storage location of the next node is not continuous with this node, the addressing efficiency will not be affected. Therefore, we usually use linked lists to organize fragmented space.

The insertion and deletion of linked list does not affect most other nodes, and only involves the node operations before and after the target node, so the efficiency is very high: O(1)

The disadvantage is that the query efficiency is low. In order to query a node in the linked list, the linked list must be traversed sequentially, and the time complexity is O(n).

Below is a schematic of a single linked list ​

The following single linked list implementation code

package list

type node struct {
	v int
	p *node
}

var rootNode = new(node)

// addNode Adds a node
func addNode(v int) {
	if rootNode.v == 0 {
		rootNode.v = v
		return
	}
	var newNode = &node{
		v: v,
		p: nil,
	}
	rootNode.findLastNode().p = newNode
}

// findLastNode retrieves the last node in the list
func (n *node) findLastNode(a) *node {
	if n.p == nil {
		return n
	}
	return n.p.findLastNode()
}

// traverse print
func (n *node) traverse(a) {
	println(n.v)
	if n.p == nil {
		return
	}
	n.p.traverse()
}

// find Finds the node where a value is located
func (n *node) find(v int) *node {
	if n.v == v {
		return n
	}
	if n.p == nil {
		return nil
	}
	return n.p.find(v)
}

// delete Deletes a node
func (n *node) delete(v int) {
	if n.v == v {
		ifn.p ! =nil {
			n.v = n.p.v
			n.p = n.p.p
			return
		}
		n = nil
		return
	}
	n.p.findToDelete(v, n)
}

// findToDelete traverses the delete
func(n *node) findToDelete(v int, lastn *node) {
	if n.v == v {
		lastn.p = n.p
		return
	}
	if n.p == nil {
		return
	}
	n.p.findToDelete(v, n)
}
Copy the code
package list

import "testing"

func Test_AddNode(t *testing.T) {
	addNode(1)
	addNode(2)
	addNode(3)
	addNode(4)
	addNode(5)
	addNode(6)
	addNode(7)
	addNode(8)
	addNode(9)
	rootNode.delete(7)
	rootNode.delete(3)
	rootNode.delete(1)
	rootNode.traverse()
	t.Log(rootNode.findLastNode().v)
	t.Log(rootNode.find(7).v)
}
Copy the code