Go实现单链表

单链表

NNode: 包含一个数据域，一个指针域（指向下一个节点）
LList : 包含头指针 (指向第一个节点)，链表长度
链表的特点：不能随机访问，只能根据链一个一个查找，查找的时间复杂度是 O (n)

示例代码

// +---------------------------------------------------------------
// | Description: Go实现单链表(goLinkList.go)
// +---------------------------------------------------------------
// | Author: thomas.chen <thomas.chen@huolala.cn>
// +---------------------------------------------------------------
// | CreateTime: 2022/3/10
// +---------------------------------------------------------------

package main

import "fmt"

// NNode 定义节点的结构体
type NNode struct {
	Data interface{} // 数据域
	Next *NNode      // 指针域
}

// LList 定义链表结构体
type LList struct {
	Header *NNode // 指向第一个节点
	Length int    // 链表长度
}

func CreateNode(v interface{}) *NNode {
	return &NNode{v, nil}
}

func CreateList() *LList {
	header := CreateNode(nil)
	return &LList{header, 0}
}

// Add 往链表头增加一个节点
func (l *LList) Add(data interface{}) {
	newNode := CreateNode(data)
	defer func() {
		l.Length++
	}()

	if l.Length == 0 {
		l.Header = newNode
	} else {
		newNode.Next = l.Header
		l.Header = newNode // 头指针指向新加的节点
	}
}

// Append 往链表尾加一个节点
func (l *LList) Append(data interface{}) {
	newNode := CreateNode(data)
	defer func() {
		l.Length++
	}()

	if l.Length == 0 {
		l.Header = newNode
	}

	if l.Length > 0 {
		current := l.Header
		for current.Next != nil { // 循环找到最后一个节点
			current = current.Next
		}
		current.Next = newNode // 把新节点地址给最后一个节点的Next
	}
}

// Insert 往i插入一个节点，后插
func (l *LList) Insert(i int, data interface{}) {
	defer func() {
		l.Length++
	}()

	if i >= l.Length {
		l.Append(data)
		return
	}
	newNode := CreateNode(data)
	// 找到第i个节点pre和第i+1个after
	j := 1
	pre := l.Header
	for j != i {
		pre = pre.Next
		j++
	}
	newNode.Next = pre.Next // 获取到i+1个节点
	// 修改i节点，新节点的指针
	pre.Next = newNode
}

// Delete 删除第i个节点
func (l *LList) Delete(i int) {
	defer func() {
		l.Length--
	}()

	if i == 1 { // 删除第一个节点，把header指向第二个节点即可
		l.Header = l.Header.Next
		return
	}
	// 找到第i-1个节点的next指向第i+1个节点即可
	j := 1
	current := l.Header
	for ; j < i-1; j++ {
		current = current.Next
	}
	current.Next = current.Next.Next
}

// Remove 删除指定值节点
func (l *LList) Remove(data interface{}) {
	defer func() {
		l.Length--
	}()
	current := l.Header
	if current.Data == data { // 删除值恰好为第一个节点，把header指向第二个节点即可
		l.Header = l.Header.Next
		return
	}
	for current.Next != nil {
		if current.Next.Data == data {
			current.Next = current.Next.Next
		}
		current = current.Next
	}
	return
}

// GetListLength 获取链表长度
func (l *LList) GetListLength() int {
	fmt.Printf("当前链表长度：%d\n", l.Length)
	return l.Length
}

// Scan 遍历链表，显示出来
func (l *LList) Scan() {
	current := l.Header
	i := 1
	for current.Next != nil {
		fmt.Printf("第%d的节点是%d\n", i, current.Data)
		current = current.Next
		i++
	}
	fmt.Printf("第%d的节点是%d\n", i, current.Data)
}

// ShowList 打印链表
func (l *LList) ShowList() {
	//打印链表
	if l.Length == 0 {
		fmt.Println("-> 空链表!")
		return
	}

	current := l.Header
	i := 1
	for current.Next != nil {
		fmt.Printf("%d -> ", current.Data)
		current = current.Next
		i++
	}
	fmt.Printf("%d -> ", current.Data)
	fmt.Println("")
}

func main() {
	list := CreateList()
	list.Add(100)
	list.Add(200)
	list.Add(400)
	list.Append(99)
	list.Insert(1, 300)
	list.Insert(5, 88)
	list.Insert(5, 90)
	list.ShowList()
	list.GetListLength()
	//list.Scan()
	//list.Delete(6)
	list.Remove(400)
	//list.Scan()
	list.ShowList()
	list.GetListLength()
}

打印结果

400 -> 300 -> 200 -> 100 -> 99 -> 90 -> 88 ->
当前链表长度：8
300 -> 200 -> 100 -> 99 -> 90 -> 88 ->
当前链表长度：7