伏龙阁资源网

详解go语言单链表及其常用方法的实现
站长资源 2024/11/22 佚名
2 0

目的

在刷算法题中经常遇到关于链表的操作，在使用go语言去操作链表时不熟悉其实现原理，目的是为了重温链表这一基础且关键的数据结构。

1、链表的特点和初始化

1.1、链表的特点
用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的)

1.2、结点

结点(node)

  • 数据域 => 存储元素信息
  • 指针域 => 存储结点的直接后继，也称作指针或链

首元结点 是指链表中存储的第一个数据元素的结点
头结点 是在首元结点之前附设的一个结点，其指针域指向首元结点(非必须)
头指针 是指向链表中第一个结点的指针

详解go语言单链表及其常用方法的实现

1.3、单链表
特点

  • 每个结点中只包含一个指针域
  • 单链表是非随机存取的存储结构，要取得第i个数据元素必须从头指针出发，顺链进行寻找，也称为顺序存取的存取结构

1.4、单链表的常用操作

本文主要实现了单链表的以下操作

  • 判断是否为空
  • 获取链表长度
  • 在头部插入元素
  • 在尾部插入元素
  • 删除指定位置元素
  • 删除指定值的元素
  • 查找是否包含指定值
  • 查找指定位置元素的值
  • 遍历链表所有结点

1.5、单链表的初始化

//定义单链表结构体
type Node struct {
  data interface{} //数据域
  next *Node    //指针域
}
type List struct {
  length  int //储存链表的长度
  headNode *Node
}

/*单链表的初始化
1、生成新结点作为头结点，用头指针指向头结点
2、头结点的指针域置空
*/
func InitList() *List {
  //即构造一个空的单链表L(包含头指针)
  node := new(Node)
  L := new(List)
  L.headNode = node
  return L
}

2、单链表的插入

先讲单链表的插入有利于后续相关操作的实现

2.1、在指定位置插入元素

/*单链表的插入=>将值为e的新结点插入到表的第i个结点的位置上，即插入到结点a(i-1)与a(i)之间
1、查找结点a(i-1)并由指针p指向该结点
2、生成一个新结点*s
3、将新结点*s的数据域置为e
4、将新结点*s的指针域指向结点a(i)
5、将结点*p的指针域指向新结点*s
*/
func (list *List) InsertElem(index int, v interface{}) {
  if index <= 0 || index > list.length {
    fmt.Println("err")
  } else {
    pre := list.headNode
    node := &Node{data: v}
    if index == 1 {
      node.next = pre
      list.headNode = node
    } else {
      for count := 1; count < index-1; count++ {
        pre = pre.next
      }
      node.next = pre.next
      pre.next = node
    }
    list.length--
  }
}

2.2、在头部插入元素

func (list *List) AddElem(v interface{}) {
  node := &Node{data: v}
  if list.IsNull() { //处理空表的插入，否则会导致一个空的头结点后移
    list.headNode = node
    list.length++
    return
  }
  node.next = list.headNode
  list.headNode = node
  list.length++
  return
}

2.3、在尾部插入元素

func (list *List) AppendElem(v interface{}) {
  node := &Node{data: v}
  if list.IsNull() {
    list.headNode.next = node
  } else {
    cur := list.headNode
    for cur.next != nil {
      cur = cur.next
    }
    cur.next = node
  }
  list.length++
  return
}

3、单链表的删除

3.1、删除指定值的元素

/*单链表的删除
1、查找结点a(i-1)并由指针p指向该结点
2、临时保存待删除结点a(i)的地址在q中，以备释放
3、将结点*p的指针域指向a(i)的直接后继结点
4、释放结点a(i)的空间
*/
func (list *List) DeleteElem(index int) {
  if index <= 0 || index > list.length {
    fmt.Println("删除位置不合理")
    return
  } else {
    pre := list.headNode
    if index == 1 {
      list.headNode = pre.next
    } else {
      pre := list.headNode
      for count := 1; count < index-1; count++ {
        pre = pre.next
      }
      pre.next = pre.next.next
    }
    list.length--
  }
}

3.2、删除指定位置的元素

func (list *List) RemoveElem(v interface{}) {
  pre := list.headNode
  if pre.data == v {
    list.headNode = pre.next
    fmt.Println("ok")
  } else {
    for pre.next != nil {
      if pre.next.data == v {
        pre.next = pre.next.next
        fmt.Println("ok")
        return
      } else {
        pre = pre.next
      }
    }
    fmt.Println("fail")
    return
  }
}

4、单链表的查询

4.1、查找是否包含指定值

/*单链表的按值查找
1、用指针p指向首元结点
2、从首元结点开始以此顺着链域next向下查找，只要指向当前结点的指针p不为空，
并且p所指结点的数据域不等于给定值e，则执行以下操作：p指向下一个结点
3、返回p。若查找成功，p此时即为结点的地址值，若查找失败，p的值即为NULL。
*/
func (list *List) LocateElem(v interface{}) bool {
  if IsNull() {
    fmt.Println("err")
  } else {
    pre := list.headNode
    for pre != nil {
      if pre.data == v {
        return true
      }
      pre = pre.next
    }
    return false
  }
}

4.2、查找指定位置的值

/*单链表的取值
1、用指针P指向首元结点，用j做计数器初值赋为1
2、从首元结点开始依次顺着链域(指针域)next向下访问，
只要指向当前结点的指针P不为空，并且没有达到序号为i的结点，则循环执行以下操作：
  2.1、P指向下一个结点
  2.2、计数器j相应加1
3、退出循环时，如果指针P为空，或者计数器j大于i，说明指定的序号i值不合法(i大于表长n或i小于等于0)，
取值失败返回ERROR；否则取值成功，
此时j==i时，P所指的结点就是要找的第i个结点，用参数e保存当前结点的数据域，返回OK
*/
func (list *List) GetElem(index int) int {
  if index <= 0 || index > list.length {
    fmt.Println("err")
    return
  } else {
    pre := list.headNode
    for j := 0; j < index; j++ {
      if pre != nil {
        pre = pre.next
      }
    }
    return pre.data
  }
}

4.3、遍历单链表

func (list *List) ShowList() {
  if !list.IsNull() {
    cur := list.headNode
    for {
      fmt.Printf("\t%v", cur.data)
      if cur.next != nil {
        cur = cur.next
      } else {
        break
      }
    }
  }
}

5、完整代码及结果展示

package main

import "fmt"

//定义单链表结构体

type Node struct {
  data interface{} //数据域
  next *Node    //指针域
}
type List struct {
  length  int //储存链表的长度
  headNode *Node
}

/*
type Method interface {
  IsNull() bool          //1、判断是否为空
  GetLength() int         //2、获取链表长度
  InsertElem(i int, v interface{}) //3、在指定位置添加元素
  AddElem(v interface{})      //4、在头部插入元素
  AppendElem(v interface{})    //5、在尾部插入元素
  DeleteElem(i int)        //6、删除指定位置元素
  RemoveElem(v interface{})    //7、删除指定值的元素
  ContaineElem(v interface{}) bool //8、是否包含指定值的元素
  LocateElem(i int) interface{}  //9、查找指定位置元素的值
  ShowList()            //10、遍历链表所有结点
}
*/
/*单链表的初始化
1、生成新结点作为头结点，用头指针指向头结点
2、头结点的指针域置空
*/
func InitList() *List {
  //即构造一个空的单链表L(包含头指针)
  node := new(Node)
  L := new(List)
  L.headNode = node
  return L
}

/*单链表的取值
1、用指针P指向首元结点，用j做计数器初值赋为1
2、从首元结点开始依次顺着链域(指针域)next向下访问，只要指向当前结点的指针P不为空，
并且没有达到序号为i的结点，则循环执行以下操作：
  2.1、P指向下一个结点
  2.2、计数器j相应加1
3、退出循环时，如果指针P为空，或者计数器j大于i，说明指定的序号i值
不合法(i大于表长n或i小于等于0)，取值失败返回ERROR；否则取值成功，
此时j==i时，P所指的结点就是要找的第i个结点，用参数e保存当前结点的数据域，返回OK
*/
func (list *List) GetElem(index int) int {
  if index <= 0 || index > list.length {
    return 0
  } else {
    pre := list.headNode
    for j := 0; j < index-1; j++ {
      if pre != nil {
        pre = pre.next
      }
    }
    return pre.data.(int)
  }
}

/*单链表的按值查找
1、用指针p指向首元结点
2、从首元结点开始以此顺着链域next向下查找，只要指向当前结点的
指针p不为空，并且p所指结点的数据域不等于给定值e，则执行以下操作：
  2.1、p指向下一个结点
3、返回p。若查找成功，p此时即为结点的地址值，若查找失败，p的值即为NULL。
*/
func (list *List) LocateElem(v interface{}) bool {
  if list.IsNull() {
    fmt.Println("err")
    return false
  } else {
    pre := list.headNode
    for pre != nil {
      if pre.data == v {
        return true
      }
      pre = pre.next
    }
    return false
  }
}

/*单链表的插入=>将值为e的新结点插入到表的第i个结点的位置上，即插入到结点a(i-1)与a(i)之间
1、查找结点a(i-1)并由指针p指向该结点
2、生成一个新结点*s
3、将新结点*s的数据域置为e
4、将新结点*s的指针域指向结点a(i)
5、将结点*p的指针域指向新结点*s
*/
func (list *List) InsertElem(index int, v interface{}) {
  if index <= 0 || index > list.length {
    fmt.Println("err")
  } else {
    pre := list.headNode
    node := &Node{data: v}
    if index == 1 {
      node.next = pre
      list.headNode = node
    } else {
      for count := 1; count < index-1; count++ {
        pre = pre.next
      }
      node.next = pre.next
      pre.next = node
    }
    list.length--
  }
}

/*单链表的删除
1、查找结点a(i-1)并由指针p指向该结点
2、临时保存待删除结点a(i)的地址在q中，以备释放
3、将结点*p的指针域指向a(i)的直接后继结点
4、释放结点a(i)的空间
*/
func (list *List) DeleteElem(index int) {
  if index <= 0 || index > list.length {
    fmt.Println("删除位置不合理")
    return
  } else {
    pre := list.headNode
    if index == 1 {
      list.headNode = pre.next
    } else {
      pre := list.headNode
      for count := 1; count < index-1; count++ {
        pre = pre.next
      }
      pre.next = pre.next.next
    }
    list.length--
  }
}

func (list *List) RemoveElem(v interface{}) {
  pre := list.headNode
  if pre.data == v {
    list.headNode = pre.next
  } else {
    for pre.next != nil {
      if pre.next.data == v {
        pre.next = pre.next.next
        return
      } else {
        pre = pre.next
      }
    }
    fmt.Println("fail")
    return
  }
}

func (list *List) IsNull() bool {
  if list.length == 0 {
    return true
  } else {
    return false
  }
}

func (list *List) AddElem(v interface{}) {
  node := &Node{data: v}
  if list.IsNull() { //处理空表的插入，否则会导致一个空的头结点后移
    list.headNode = node
    list.length++
    return
  }
  node.next = list.headNode
  list.headNode = node
  list.length++
  return
}

func (list *List) AppendElem(v interface{}) {
  node := &Node{data: v}
  if list.IsNull() {
    list.headNode.next = node
  } else {
    cur := list.headNode
    for cur.next != nil {
      cur = cur.next
    }
    cur.next = node
  }
  list.length++
  return
}

func (list *List) ShowList() {
  if !list.IsNull() {
    cur := list.headNode
    for {
      fmt.Printf("\t%v", cur.data)
      if cur.next != nil {
        cur = cur.next
      } else {
        break
      }
    }
    fmt.Printf("\n")
  }
}

func main() {
  L := InitList()
  msg := []int{12, 5, 3, 8, 55, 13}
  for i := range msg {
    L.AddElem(msg[i])
  }
  fmt.Println("---- 添加元素 ----")
  L.AppendElem(66)
  L.ShowList()
  fmt.Println("---- 按位删除元素 ----")
  L.DeleteElem(3)
  L.ShowList()
  fmt.Println("---- 按值删除元素 ----")
  L.RemoveElem(13)
  L.ShowList()
  fmt.Println("---- 插入元素 ----")
  L.InsertElem(1, 88)
  L.ShowList()
  fmt.Println("---- 按值寻找元素 ----")
  fmt.Println(L.LocateElem(88))
  fmt.Println("---- 按位寻找元素 ----")
  fmt.Println(L.GetElem(4))
}

结果
---- 添加元素 ----
        13      55      8       3       5       12      66
---- 按位删除元素 ----
        13      55      3       5       12      66
---- 按值删除元素 ----
        55      3       5       12      66
---- 插入元素 ----
        88      55      3       5       12      66
---- 按值寻找元素 ----
true
---- 按位寻找元素 ----
5

6、总结

本文中除了初始化时为链表添加了一个空的头结点，其他情况下均无头结点，正如书中所说，为单链表添加头结点会方便很多，对链表进行相关操作时，不需要对首元结点做额外的处理，也便于对空表和非空表做统一处理
关于删除时释放结点空间及指针回收，我们交由go强大的垃圾回收来完成

参考博客
Golang之单链表实现
go语言实现单链表

广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！
www.wwsws.com 伏龙阁资源网
39,976影音资源
44,792技术资源
21,817软件资源
651,128站长资源

更新日志

友情链接

杰晶网络 DDR爱好者之家 桃源资源网 杰网资源 富贵资源网 南强小屋 铁雪资源网 幽灵资源网 万梅资源网 狼山资源网 白云岛资源网 昆仑资源网 相思资源网 明霞山资源网 内蒙古资源网 黑松山资源网 茶园资源网 饿虎岗资源网 大旗谷资源网 常春岛资源网 岱庙资源网 兴国资源网 快活林资源网 蝙蝠岛资源网 帝王谷资源网 白云城资源网 伏龙阁资源网 清风细雨楼 天枫庄资源网 圆月山庄资源网 无争山庄资源网 神水资源网 移花宫资源网 神剑山庄资源网 无为清净楼资源网 金钱帮资源网 丐帮资源网 华山资源网 极乐门资源网 小李飞刀资源网 凤求凰客栈 风云阁资源网 金狮镖局 鸳鸯亭资源网 千金楼资源网 更多链接