189 8069 5689
单向链表
目前创新互联公司已为上千的企业提供了网站建设、域名、虚拟空间、网站改版维护、企业网站设计、泉山网站维护等服务，公司将坚持客户导向、应用为本的策略，正道将秉承"和谐、参与、激情"的文化，与客户和合作伙伴齐心协力一起成长，共同发展。
单向链表(单链表)是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表，因为链表是由一个个结点组装起来的;其中每个结点都有指针成员变量指向列表中的下一个结点;
特点：
(1)单个结点创建非常方便，普通的线性内存通常在创建的时候就需要设定数据的大小
(2)结点的删除非常方便，不需要像线性结构那样移动剩下的数据
(3)结点的访问方便，可以通过循环或者递归的方法访问到任意数据，但是平均的访问效率低于线性表
package main
import (
"fmt"
)
type LinkNode struct {
Data interface{}
Next *LinkNode
}
type SingleLink struct {
head *LinkNode
tail *LinkNode
size int
}
// 初始化链表
func InitSingleLink()(*SingleLink){
return &SingleLink{
head:nil,
tail:nil,
size:0,
}
}
// 获取头部节点
func (sl *SingleLink)GetHead()*LinkNode{
return sl.head
}
// 获取尾部节点
func (sl *SingleLink)GetTail()*LinkNode{
return sl.tail
}
// 打印链表
func (sl *SingleLink) Print(){
fmt.Println("SingleLink size:",sl.Length())
if sl.size == 0{
return
}
ptr := sl.GetHead()
for ptr != nil{
fmt.Println("Data:",ptr.Data)
ptr = ptr.Next
}
}
//链表长度
func (sl *SingleLink) Length() int{
return sl.size
}
//插入数据（头插）
func (sl *SingleLink) InsertByHead(node *LinkNode){
if node == nil{
return
}
// 判断是否第一个节点
if sl.Length() == 0{
sl.head = node
sl.tail = node
node.Next = nil
}else{
oldHeadNode := sl.GetHead()
sl.head = node
sl.head.Next = oldHeadNode
}
sl.size++
}
//插入数据（尾插）
func (sl *SingleLink) InsertByTail(node *LinkNode) {
if node == nil{
return
}
// 插入第一个节点
if sl.size == 0{
sl.head = node
sl.tail = node
node.Next = nil
}else{
sl.tail.Next = node
node.Next = nil
sl.tail = node
}
sl.size ++
}
//插入数据（下标）位置
func (sl *SingleLink) InsertByIndex(index int, node *LinkNode){
if node == nil{
return
}
// 往头部插入
if index == 0 {
sl.InsertByHead(node)
}else{
if index > sl.Length(){
return
}else if index == sl.Length(){
//往尾部添加节点
sl.InsertByTail(node)
}else{
preNode := sl.Search(index-1) // 下标为 index 的上一个节点
currentNode := sl.Search(index) // 下标为 index 的节点
preNode.Next = node
node.Next = currentNode
sl.size++
}
}
}
//删除数据（下标）位置
func (sl *SingleLink) DeleteByIndex(index int) {
if sl.Length() == 0 || index > sl.Length(){
return
}
// 删除第一个节点
if index == 0{
sl.head = sl.head.Next
}else{
preNode := sl.Search(index-1)
if index != sl.Length()-1{
nextNode := sl.Search(index).Next
preNode.Next = nextNode
}else{
sl.tail = preNode
preNode.Next = nil
}
}
sl.size--
}
// 删除数据（数据）
func (sl *SingleLink) DeleteByData(Data interface{}) {
if sl.Length() == 0 || Data == nil{
return
}
node := sl.head
preNode := sl.head
for node.Next != nil{
preNode = node
node = node.Next
if node.Data.(int) == Data.(int){
preNode.Next = node.Next
node.Next = nil
node.Data = nil
node = nil
return
}
}
}
// 查询数据
func (sl *SingleLink) Search(index int)(node *LinkNode) {
if sl.Length() == 0 || index > sl.Length(){
return nil
}
// 是否头部节点
if index == 0{
return sl.GetHead()
}
node = sl.head
for i:=0;i<=index;i++{
node = node.Next
}
return
}
//销毁链表
func (sl *SingleLink) Destroy() {
sl.tail = nil
sl.head = nil
sl.size = 0
}
func main() {
// 初始化链表
sl := InitSingleLink()
// 指定指标插入
for i:=0;i<5;i++{
snode := &LinkNode{
Data:i,
}
sl.InsertByIndex(i,snode)
}
sl.Print()
fmt.Println("===============================")
var snode *LinkNode
// 往头部插入节点
snode = &LinkNode{
Data:6,
}
sl.InsertByHead(snode)
sl.Print()
fmt.Println("===============================")
//往尾部插入节点
snode = &LinkNode{
Data:5,
}
sl.InsertByTail(snode)
sl.Print()
fmt.Println("===============================")
// 查询下标为2的节点
node := sl.Search(2)
fmt.Println("Node2:",node.Data)
fmt.Println("===============================")
// 删除下标为2的节点
sl.DeleteByIndex(2)
sl.Print()
fmt.Println("===============================")
// 删除Data 为3的节点
sl.DeleteByData(3)
sl.Print()
}