欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

单向链表实现原理

程序员文章站 2023-09-29 08:29:43
package main import ( "fmt" "reflect" ) //通过结构体嵌套本结构体指针来实现链表 //结构体可以嵌套本结构体指针, 但不能嵌套本结构体本身, 长度不能超过 1024 type LinkNode struct { Data interface{} Next *L... ......
package main

import (
	"fmt"
	"reflect"
)

//通过结构体嵌套本结构体指针来实现链表
//结构体可以嵌套本结构体指针, 但不能嵌套本结构体本身, 长度不能超过 1024
type linknode struct {
	data interface{}
	next *linknode // right , 可以嵌套本结构体指针
	//next linknode // error, 不能嵌套本结构体本身
}

//创建链表 create(数据)
func (node *linknode) create(data ...interface{}) { //1,2
	if node == nil {
		return
	}
	//头节点
	head := node

	for i := 0; i < len(data); i++ {
		//创建一个新的节点
		newnode := new(linknode)
		newnode.data = data[i]
		newnode.next = nil
		//将新节点作为当前节点的下一个节点
		node.next = newnode
		node = node.next
	}
	node = head

}

//打印链表
func (node *linknode) print() {
	if node == nil {
		return
	}

	//打印数据
	if node.data != nil {
		fmt.println(node.data, " ")
	}
	//使用递归遍历下一个数据
	node.next.print()
}

//链表长度
func (node *linknode) length() int {
	if node == nil {
		return -1
	}

	i := 0
	//一次查找下一个节点是否为nil
	for node.next != nil {
		i++
		node = node.next
	}
	return i
}

//插入数据(头插)
func (node *linknode) insertbyhead(data interface{}) {
	if node == nil {
		return
	}
	if data == nil {
		return
	}

	//head:=node

	//创建新节点
	newnode := new(linknode)
	//新节点赋值
	newnode.data = data
	newnode.next = node.next
	//将新节点放在当前节点后面
	node.next = newnode
}

//插入数据(尾插)
func (node *linknode) insertbytail(data interface{}) {
	if node == nil {
		return
	}

	//查找链表的末尾位置
	for node.next != nil {
		node = node.next
	}
	//创建新节点  赋值
	newnode := new(linknode)
	newnode.data = data
	newnode.next = nil
	//将新节点放在链表末尾
	node.next = newnode
}

//插入数据(下标)位置
func (node *linknode) inserrbyindex(index int, data interface{}) {
	if node == nil {
		return
	}
	if index < 0 {
		return
	}
	/*
	if node.length() < index{
		return
	}
	*/

	//记录上一个节点
	prenode := node
	for i := 0; i < index; i++ {
		prenode = node
		//如果超出链表个数 直接返回
		if node == nil {
			return
		}
		node = node.next
	}

	//创建一个新节点
	newnode := new(linknode)
	newnode.data = data
	newnode.next = node

	//上一个节点链接当前节点
	prenode.next = newnode

}

//删除数据(下标)位置
func (node *linknode) deletebyindex(index int) {
	if node == nil {
		return
	}

	if index < 0 {
		return
	}
	//记录上一个链表节点
	prenode := node
	for i := 0; i < index; i++ {
		prenode = node
		if node == nil {
			return
		}
		node = node.next
	}

	//将上一个指针域结点指向node的下一个节点
	prenode.next = node.next

	//销毁当前节点
	node.data = nil
	node.next = nil
	node = nil
}

//删除数据(数据)
func (node *linknode) deletebydata(data interface{}) {
	if node == nil {
		return
	}
	if data == nil {
		return
	}

	prenode := node
	for node.next != nil {
		prenode = node
		node = node.next

		//判断interface存储的数据类型是否相同
		//reflect.deepequal()
		if reflect.typeof(node.data) == reflect.typeof(data) && node.data == data {
			prenode.next = node.next

			//销毁数据
			node.data = nil
			node.next = nil
			node = nil

			//如果添加return 表示删除第一个相同的数据
			//如果不添加return 表示删除所有相同的数据
			return
		}

	}
}

//查找数据 (数据)
func (node *linknode) search(data interface{}) int {
	if node == nil {
		return -1
	}
	if data == nil {
		return -1
	}

	i := 0
	for node.next != nil {
		i++
		//比较两个接口中的内容是否相同
		//reflect.deepequal()
		if reflect.typeof(node.data) == reflect.typeof(data) && node.data == data {
			return i - 1
		}
		node = node.next
	}
	return -1
}

//销毁链表
func (node *linknode) destroy() {
	if node == nil {
		return
	}
	//通过递归毁销毁链表
	node.next.destroy()

	node.data = nil
	node.next = nil
	node = nil
}