淘先锋技术网

首页 1 2 3 4 5 6 7

最后更新日期:2022/07/04

Golang本身自带实现list的基本库:container/list;具体使用方法,可以查看Go基础库文档:https://studygolang.com/pkgdoc

下面是不适用基础库的实现方法,优化方式有很多,实现思路仅供参考:

一、单链表

下文实现了单向链表、循环链表、双向链表,单链表是基础,其他的链表基本都是根据单链表演化的。

1. 节点(node)

  • 指针域:指向下一个节点的指针
  • 数据域:保存数据

2. 链表(Link list)

  • 头指针:指向链表第一个节点的指针(有头节点指向的是头节点,没有头节点指向的是首元节点)
  • 头节点:链表的首个节点,数据域可以是链表长度等信息,也可以什么都不保存;指针域指向第一个首元节点,头节点是为了简化链表操作而存在的,也可以不设头节点。
  • 首元节点:链表的第一个有效数据节点
    在这里插入图片描述

3.代码及解析

3.1 代码:

先把代码贴上,后续分解代码:

package main

import "fmt"

//单向链表 头指针、头节点(方便链表增删的)、首元节点(第一个有效数据节点)
type Node struct {
	data int   //数据域
	next *Node //指针域
}

func ShowNode(p *Node) { //遍历链表值
	for p != nil {
		fmt.Println(*p)
		p = p.next
	}
	fmt.Println()
}

//查找对应值的index
func Find(p *Node, obj int) int { //获取目标值obj的index(0是头节点,找到的第一个值),没找到返回-1
	head := p
	if head == nil {
		return -1
	}
	for i := 0; head != nil; i++ { //head != nil;  操作数据域
		if head.data == obj {
			return i
		}
		head = head.next
	}
	return -1
}

//更新数据
func Update(p *Node, val, index int) bool { //修改目标index对应节点的值
	head := p
	if head == nil {
		return false
	}
	for i := 1; i <= index; i++ {
		head = head.next //略过头节点
		if head == nil {
			return false
		}
	}
	head.data = val

	return true
}

//获取index对应的节点数据   获取失败返回-1
func GetNodeData(p *Node, index int) int {
	head := p
	if head == nil || index < 0 {
		return -1
	}
	for i := 1; i <= index; i++ {
		head = head.next //略过头节点
		if head == nil {
			return -1
		}
	}
	return head.data
}

//获取前驱节点
func GetPreNode(p *Node, index int) *Node {
	head := p
	if head == nil || index < 0 {
		return head
	}
	//找到[前驱节点] 当前链表index位置上的前一个节点
	for ; index-1 > 0; index-- {
		if head.next != nil {
			head = head.next
		} else { //没找到
			return nil
		}
	}

	return head
}

//插入节点 (0是头节点)
func Insert(p *Node, val, index int) bool {
	head := p
	if head == nil || index < 0 {
		return false
	}
	preNode := GetPreNode(head, index)
	if preNode == nil {
		return false
	}
	node := Node{data: val, next: preNode.next} //即使preNode.next=nil也无所谓
	preNode.next = &node

	return true
}

//删除节点 (0是头节点)
func Delete(p *Node, val, index int) bool {
	head := p
	if head == nil || index < 0 {
		return false
	}
	preNode := GetPreNode(head, index)
	if preNode == nil {
		return false
	}
	preNode.next = preNode.next.next //不用判断 head.next.next==nil

	return true
}

func linkList(length int) *Node { // 1.尾插法 插入节点 head>>node1>>node2  <<tail
	//头节点
	head := Node{data: 0}
	var tail *Node
	tail = &head
	//构造单向链表
	for i := 1; i <= length; i++ {
		node := Node{data: i}
		tail.next = &node
		tail = &node
	}

	//返回头节点地址
	return &head
}

const LENGTH = 3

func main() {
	head := linkList(LENGTH)
	//遍历
	ShowNode(head)

	//获取某个值的索引
	fmt.Println("Find0:", Find(head, 0))
	fmt.Println("Find2:", Find(head, 2))
	fmt.Println("Find3:", Find(head, 4))
	//节点插入
	if Insert(head, 10, 4) {
		fmt.Println("插入数据")
		ShowNode(head)
	} else {
		fmt.Println("插入失败")
	}
	//删除节点
	if Delete(head, 10, 4) {
		fmt.Println("删除数据")
		ShowNode(head)
	} else {
		fmt.Println("删除失败")
	}
	//修改节点
	if Update(head, 22, 2) {
		fmt.Println("修改数据")
		ShowNode(head)
	} else {
		fmt.Println("修改失败")
	}
	//获取数据
	if data := GetNodeData(head, 2); data != -1 {
		fmt.Println("获取数据:", data)
	} else {
		fmt.Println("获取数据失败")
	}
	//头插法
	tail := linkList2(10)
	ShowNode(tail)
}

func linkList2(length int) *Node { // 2.头插法 插入节点  tail>> node2<<node1<<head
	head := Node{data: 0}
	var tail *Node
	tail = &head //tail用于记录头节点地址,首先指向头节点
	for i := 1; i < length; i++ {
		var node = Node{data: i}
		node.next = tail //将新创建的node的next指向头节点
		tail = &node     //重新赋值头节点
	}
	return tail
}

3.2 增删改查图示:

  • 链表操作主要分为:增、删、改、查; 根据实现过程,增删操作类似、改查操作类似

    • 增加和删除

      • 增加节点:
        [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-C9mTUGpQ-1656924016415)(photo/8.Golang链表操作 增 .png)]

        步骤:
        ① 创建插入的节点,找到前驱节点(插入位置的前一个节点)
        ​② 新节点的next指向前驱节点的next
        ​③ 前驱节点的next指针指向新的节点

      • 删除节点:
        在这里插入图片描述

      步骤:
      ① 找到删除节点的前驱节点
      ​② 改变前驱节点的next指向(略过删除节点,指向删除节点的下一个节点)
      ③ 删除节点操作,与其他语言不同的是,golang GC可以在②操作后,通过GC自动回收删除节点

      • 通过增加和删除操作流程中可以看出,本质就是一个找到前驱节点后,修改前驱节点的操作
    • 修改和查找

      • 查找 (查找给定值的 index):

      步骤:
      ① 遍历链表,找到需要目标节点
      ​② 返回目标节点的index

      • 修改:

      步骤:
      ① 遍历链表,找到需要目标节点
      ​② 修改目标节点

      • 查找和修改过程基本一样,本质是遍历链表找目标节点本身

3.3 代码解析:

  • 构造节点的结构体:
type Node struct {
	data int   //数据域
	next *Node //指针域
}
  • 生成链表:尾插法(用的比较多)

    • 图示:
      在这里插入图片描述

      • ① 生成头节点,头指针(head)、尾指针(tail)同时指向头节点
      • ② 修改链表指针,指向新的节点
      • ③ 移动指针tail
      • 重复②③,最后返回头指针head
    • 代码:
      在这里插入图片描述

  • 生成链表:头插法

    • 图示:
      在这里插入图片描述

      • ① 生成头节点,头指针(head)、尾指针(tail)同时指向头节点
      • ② 修改节点指针,指向链表头节点
      • ③ 移动指针tail
      • 重复②③,最后返回头指针tail
    • 代码:
      在这里插入图片描述

  • 遍历链表:
    在这里插入图片描述

  • 插入和删除节点

    • 前面说到,插入和删除本质就是一个找到前驱节点后,修改前驱节点的操作

    • GetPreNode是一个获取前驱节点的函数:
      在这里插入图片描述

    • 插入节点

在这里插入图片描述

  • 删除节点
    在这里插入图片描述
  • 更新和查找节点

在这里插入图片描述

  • 通过给定值obj查找对应节点index

在这里插入图片描述

  • main

在这里插入图片描述

  • 结果

在这里插入图片描述

二、循环链表

循环链表和双向链表都是基于单向链表演化来的,所以它们的操作都大同小异。

将单向链表的最后一个节点的指针域指向链表的头节点,便可得到一个单向的循环链表
在这里插入图片描述

package main

import "fmt"

//单向 循环链表  (单向链表首尾相连)

type LNode struct {
	Data int
	next *LNode
}

func LoopList(length int) *LNode { //构造单向循环链表
	head := LNode{Data: 0} //头节点,按理来说循环链表是没有明确的头的   这里添加的头节点纯属为了简化操作
	var tail *LNode
	tail = &head
	for i := 1; i <= length; i++ { //尾插法生成单向链表
		node := LNode{Data: i}
		tail.next = &node
		tail = &node
	}
	//首位相连 生成
	tail.next = &head
	return &head
}

func ShowLoopList(head *LNode) {
	if head == nil { //如果头节点.next==nil  则判断为空链表
		fmt.Println("空链表")
		return
	} else if head.next == nil {
		fmt.Println("空链表")
		return
	}

	tail := head.next
	for tail != head {
		fmt.Println(*tail)
		tail = tail.next
	}

	fmt.Println()
}

const LENGTH = 5

func main() {
	loopList := LoopList(LENGTH)

	ShowLoopList(loopList)
}

三、双向链表

区别于单向链表,双向链表的节点中,指针域多一个之前前节点的指针
在这里插入图片描述

package main

import "fmt"

//双向链表
type DNode struct {
	data int
	pre  *DNode
	next *DNode
}

func doublyList(length int) *DNode { //创建双向链表
	head := DNode{data: 0}
	var tail *DNode
	tail = &head
	for i := 1; i <= length; i++ {
		node := DNode{data: i}
		tail.next = &node
		node.pre = tail

		tail = &node
	}
	return &head
}

func showList(head *DNode) {
	if head == nil { //如果头节点.next==nil  则判断为空链表
		fmt.Println("空链表")
		return
	} else if head.next == nil {
		fmt.Println("空链表")
		return
	}
	//tail := head.next //略过头节点head
	tail := head //不略过头节点head
	for tail != nil {
		fmt.Println(*tail)
		tail = tail.next
	}
}

func main() {
	list := doublyList(1)
	showList(list)
}