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

目的

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

1、链表的特点和初始化

1.1、链表的特点

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

1.2、结点

• 结点(node)
  • 数据域 => 存储元素信息
  • 指针域 => 存储结点的直接后继，也称作指针或链
• 首元结点 是指链表中存储的第一个数据元素的结点
• 头结点 是在首元结点之前附设的一个结点，其指针域指向首元结点(非必须)
• 头指针 是指向链表中第一个结点的指针
  
  

  结点

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语言实现单链表