Go语言数据结构之单链表的实例详解

2024-04-05 17:32:05

任意类型的数据域

之前的链表定义数据域都是整型int，如果需要不同类型的数据就要用到 interface{}。

空接口 interface{}

对于描述起不到任何的作用(因为它不包含任何的method），但interface{}在需要存储任意类型的数值的时候相当有用，因为它可以存储任意类型的数值。

一个函数把interface{}作为参数，那么它可以接受任意类型的值作为参数；如果一个函数返回interface{}，那么也就可以返回任意类型的值，类似于C语言的void*类型。

package main

import "fmt"

type Node struct {
    data interface{}
    next *Node
}

type List struct {
    head *Node
}

func (list *List) push(value interface{}) {
    node := &Node{data: value}
    p := list.head
    if p != nil {
        for p.next != nil {
            p = p.next
        }
        p.next = node
    } else {
        list.head = node
    }
}

func (list *List) travel() {
    p := list.head
    for p != nil {
        fmt.Print(p.data)
        p = p.next
        if p != nil {
            fmt.Print("->")
        }
    }
    fmt.Println("<nil>")
}

func main() {

    node := new(List)
    node.push("abc")
    node.push(3.142)
    node.push('a')
    node.push(3 + 4i)
    node.push([]int{1, 2, 3})
    node.push([8]byte{'a', 3: 'd'})
    node.push(Node{1, &Node{2, nil}}.data)
    node.push(Node{1, &Node{2, nil}}.next)
    node.travel()

}

/*输出：
abc->3.142->97->(3+4i)->[1 2 3]->[97 0 0 100 0 0 0 0]->1->&{2 <nil>}<nil>
*/

实例01

把字串中汉字除外的所有字符逐个存入链表，且数字以整型保存。

package main

import "fmt"

type Node struct {
    data interface{}
    next *Node
}

type List struct {
    head *Node
}

func (list *List) push(value interface{}) {
    node := &Node{data: value}
    p := list.head
    if p != nil {
        for p.next != nil {
            p = p.next
        }
        p.next = node
    } else {
        list.head = node
    }
}

func (list *List) travel() {
    p := list.head
    for p != nil {
        fmt.Print(p.data)
        p = p.next
        if p != nil {
            fmt.Print("->")
        }
    }
    fmt.Println("<nil>")
}

func main() {

    node := new(List)
    str := "Golang数据结构123:单链表0789"

    for _, s := range str {
        if s >= 48 && s < 58 {
            node.push(s - 48)
        } else if s < 128 {
            node.push(string(s))
        }
    }
    node.travel()

}

/*输出：
G->o->l->a->n->g->1->2->3->:->0->7->8->9<nil>
*/

快慢指针

给单链表设置2个指针，其中一个指针先移动n个节点，然后同时移动这2个指针，那么当先移动的指针到达尾部时，后移动的那个指针就是倒数第 n 个节点。先移动的指针称“快指针”，后出发的指针称“慢指针”，其实一样“快”只是出发有先后。

实例02

删除链表中倒数第 n 个结点

package main

import "fmt"

type Node struct {
    data interface{}
    next *Node
}

type List struct {
    head *Node
}

func (list *List) removNthBack(n int) {
    if n > list.size() {
        panic("range error: n <= List's size")
    }
    var fast, slow *Node
    head := list.head
    fast = head
    slow = head
    for i := 0; i < n; i++ {
        fast = fast.next
    }
    if fast == nil {
        list.head = head.next
        return
    }
    for fast.next != nil {
        fast = fast.next
        slow = slow.next
    }
    slow.next = slow.next.next
}

func removNthBack(list *List, n int) *List {
    if n > list.size() {
        panic("range error: n <= List's size")
    }
    var fast, slow *Node
    head := list.head
    fast = head
    slow = head
    for i := 0; i < n; i++ {
        fast = fast.next
    }
    if fast == nil {
        list.head = head.next
        return list
    }
    for fast.next != nil {
        fast = fast.next
        slow = slow.next
    }
    slow.next = slow.next.next
    return list
}

func (list *List) push(value interface{}) {
    node := &Node{data: value}
    p := list.head
    if p != nil {
        for p.next != nil {
            p = p.next
        }
        p.next = node
    } else {
        list.head = node
    }
}

func (list *List) size() int {
    length := 0
    for p := list.head; p != nil; p = p.next {
        length++
    }
    return length
}

func (list *List) travel() {
    p := list.head
    for p != nil {
        fmt.Print(p.data)
        p = p.next
        if p != nil {
            fmt.Print("->")
        }
    }
    fmt.Println("<nil>")
}

func main() {

    lst := new(List)
    str := "12309"

    for _, s := range str {
        lst.push(s - 48)
    }
    lst.travel()

    lst.removNthBack(3)
    lst.travel()
    lst = removNthBack(lst, 3)
    lst.travel()
    lst.removNthBack(2)
    lst.travel()
    //lst.removNthBack(10) //panic error
    lst.removNthBack(2)
    lst.travel()
    lst.removNthBack(1)
    lst.travel()
    //lst.removNthBack(1) //panic error

}

/*输出：
1->2->3->0->9<nil>
1->2->0->9<nil>
1->0->9<nil>
1->9<nil>
9<nil>
<nil>
*/

反转链表

遍历一个链表，每个结点用头插法相接的新链表就是原链表的反转结果。

实例03

反转整个链表

package main

import "fmt"

type Node struct {
    data interface{}
    next *Node
}

type List struct {
    head *Node
}

func (list *List) reverse() {
    res := &List{}
    for p := list.head; p != nil; p = p.next {
        node := &Node{p.data, nil}
        node.next = res.head
        res.head = node
    }
    list.head = res.head
}

func (list *List) pushHead(value interface{}) {
    node := &Node{data: value}
    node.next = list.head
    list.head = node
}

func (list *List) build(lst []interface{}) {
    for i := len(lst) - 1; i >= 0; i-- {
        node := &Node{data: lst[i]}
        node.next = list.head
        list.head = node
    }
}

func (list *List) clear() {
    list.head = nil
}

func (list *List) travel() {
    p := list.head
    for p != nil {
        fmt.Print(p.data)
        p = p.next
        if p != nil {
            fmt.Print("->")
        }
    }
    fmt.Println("<nil>")
}

func main() {

    lst := new(List)

    for n := 5; n > 0; n-- {
        lst.pushHead(n)
    }
    lst.travel()
    lst.reverse()
    lst.travel()

    lst.clear()
    lst.build([]interface{}{6.13, "/", 100000, "Hann", 1.0e-5})
    lst.travel()
    lst.reverse()
    lst.travel()

}

/*输出：
1->2->3->4->5<nil>
5->4->3->2->1<nil>
6.13->/->100000->Hann->1e-05<nil>
1e-05->Hann->100000->/->6.13<nil>
*/

实例04

反转链表的其中一段，反转从第m个结点到n个结点(其中0<m<=n<=length of List)

Input: 1->2->3->4->5->nil, m = 2, n = 4
Output: 1->4->3->2->5->nil

package main

import "fmt"

type Node struct {
    data interface{}
    next *Node
}

type List struct {
    head *Node
}

func reverseBetween(list *List, m int, n int) *List {
    list = list.Copy()
    head := list.head
    if head == nil || m >= n {
        return list
    }
    if m < 1 { //防止范围左端超限
        m = 1
    }
    node := &Node{0, head}
    p := node
    for i := 0; p.next != nil && i < m-1; i++ {
        p = p.next
    }
    if p.next == nil {
        return list
    }
    cur := p.next
    for i := 0; i < n-m && cur.next != nil; i++ {
        //由cur.next != nil防止范围右端超限
        tmp := p.next
        p.next = cur.next
        cur.next = cur.next.next
        p.next.next = tmp
    }
    list.head = node.next
    return list
}

func (list *List) reverseBetween(m int, n int) {
    head := list.head
    if head == nil || m >= n {
        return
    }
    if m < 1 { //防止范围左端超限
        m = 1
    }
    node := &Node{0, head}
    p := node
    for i := 0; p.next != nil && i < m-1; i++ {
        p = p.next
    }
    if p.next == nil {
        return
    }
    cur := p.next
    for i := 0; i < n-m && cur.next != nil; i++ {
        //由cur.next != nil防止范围右端超限
        tmp := p.next
        p.next = cur.next
        cur.next = cur.next.next
        p.next.next = tmp
    }
    list.head = node.next
}

func (list *List) pushHead(value interface{}) {
    node := &Node{data: value}
    node.next = list.head
    list.head = node
}

func (list *List) build(lst []interface{}) {
    for i := len(lst) - 1; i >= 0; i-- {
        node := &Node{data: lst[i]}
        node.next = list.head
        list.head = node
    }
}

func (list *List) Copy() *List {
    p := list.head
    res := &List{}
    if p != nil {
        node := &Node{p.data, nil}
        q := node
        for p = p.next; p != nil; p = p.next {
            q.next = &Node{p.data, nil}
            q = q.next
        }
        res.head = node
    }
    return res
}

func (list *List) travel() {
    p := list.head
    for p != nil {
        fmt.Print(p.data)
        p = p.next
        if p != nil {
            fmt.Print("->")
        }
    }
    fmt.Println("<nil>")
}

func main() {

    list1 := new(List)
    list2 := new(List)
    for n := 5; n > 0; n-- {
        list1.pushHead(n)
    }
    list1.travel()

    list2 = reverseBetween(list1, 2, 4)
    list2.travel()
    list2 = reverseBetween(list1, 2, 3)
    list2.travel()
    list2 = reverseBetween(list1, 2, 5)
    list2.travel()
    list2 = reverseBetween(list1, 2, 6)
    list2.travel()
    list2 = reverseBetween(list1, 1, 6)
    list2.travel()
    list2 = reverseBetween(list1, 0, 3)
    list2.travel()
    list1.reverseBetween(1, 3)
    list1.travel()

}

/*输出：
1->2->3->4->5<nil>
1->4->3->2->5<nil>
1->3->2->4->5<nil>
1->5->4->3->2<nil>
1->5->4->3->2<nil>
5->4->3->2->1<nil>
3->2->1->4->5<nil>
3->2->1->4->5<nil>
*/

交换节点

实例05

链表的相邻节点两两交换位置

Given 1->2->3->4, you should return the list as 2->1->4->3.

package main

import "fmt"

type Node struct {
    data interface{}
    next *Node
}

type List struct {
    head *Node
}

func (list *List) swapPairs() {
    p := list.head
    if p == nil || p.next == nil {
        return
    }
    head := p.next
    var node, node2 *Node
    for p.next != nil {
        cur := p.next
        if node != nil && node.next != nil {
            node.next = cur
        }
        if p.next.next != nil {
            node2 = p.next.next
        }
        if p.next.next != nil {
            p.next = node2
        } else {
            p.next = nil
        }
        cur.next = p
        node = p
        if p.next != nil {
            p = node2
        }
    }
    list.head = head
}

func swapPairs(list *List) *List {
    list = list.Copy()
    p := list.head
    if p == nil || p.next == nil {
        return list
    }
    head := p.next
    var node, node2 *Node
    for p.next != nil {
        cur := p.next
        if node != nil && node.next != nil {
            node.next = cur
        }
        if p.next.next != nil {
            node2 = p.next.next
        }
        if p.next.next != nil {
            p.next = node2
        } else {
            p.next = nil
        }
        cur.next = p
        node = p
        if p.next != nil {
            p = node2
        }
    }
    list.head = head
    return list
}

func (list *List) Copy() *List {
    p := list.head
    res := &List{}
    if p != nil {
        node := &Node{p.data, nil}
        q := node
        for p = p.next; p != nil; p = p.next {
            q.next = &Node{p.data, nil}
            q = q.next
        }
        res.head = node
    }
    return res
}

func (list *List) build(lst []interface{}) {
    for i := len(lst) - 1; i >= 0; i-- {
        node := &Node{data: lst[i]}
        node.next = list.head
        list.head = node
    }
}

func (list *List) travel() {
    p := list.head
    for p != nil {
        fmt.Print(p.data)
        p = p.next
        if p != nil {
            fmt.Print("->")
        }
    }
    fmt.Println("<nil>")
}

func main() {

    list1 := new(List)
    list2 := new(List)
    list1.build([]interface{}{1, 2, 3, 4, 5, 6})
    list1.travel()

    list2 = swapPairs(list1)
    list2.travel()

    list2 = &List{&Node{0, nil}}
    list2.head.next = list1.Copy().head
    list2.travel()
    list2.swapPairs()
    list2.travel()

}

/*输出：
1->2->3->4->5->6<nil>
2->1->4->3->6->5<nil>
0->1->2->3->4->5->6<nil>
1->0->3->2->5->4->6<nil>
*/

以上就是Go语言数据结构之单链表的实例详解的详细内容，更多关于Go语言单链表的资料请关注我们其它相关文章！

详解Go语言中单链表的使用

目录链表单链表结构创建节点遍历链表头插法尾插法遍历方法链表长度链表转数组数组转链表链表一种物理存储单元上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的.链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成.每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域.使用链表结构可以避免在使用数组时需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理.但是链表失去
Go语言单链表实现方法

本文实例讲述了Go语言单链表实现方法.分享给大家供大家参考.具体如下: 1. singlechain.go代码如下: 复制代码代码如下: ////////// //单链表 -- 线性表 package singlechain //定义节点 type Node struct { Data int Next *Node } /* * 返回第一个节点 * h 头结点 */ func GetFirst(h *Node) *Node { if h.Next == nil {
详解go语言单链表及其常用方法的实现

目的在刷算法题中经常遇到关于链表的操作,在使用go语言去操作链表时不熟悉其实现原理,目的是为了重温链表这一基础且关键的数据结构. 1.链表的特点和初始化 1.1.链表的特点用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的) 1.2.结点结点(node) 数据域 => 存储元素信息指针域 => 存储结点的直接后继,也称作指针或链首元结点是指链表中存储的第一个数据元素的结点头结点是在首元结点之前附设的一个结点,其指针域指向首元结点(非必须) 头指
Go语言数据结构之单链表的实例详解

目录任意类型的数据域实例01 快慢指针实例02 反转链表实例03 实例04 交换节点实例05 任意类型的数据域之前的链表定义数据域都是整型int,如果需要不同类型的数据就要用到 interface{}. 空接口 interface{} 对于描述起不到任何的作用(因为它不包含任何的method),但interface{}在需要存储任意类型的数值的时候相当有用,因为它可以存储任意类型的数值. 一个函数把interface{}作为参数,那么它可以接受任意类型的值作为参数:如果一个函数返回i
C#数据结构之单链表(LinkList)实例详解

本文实例讲述了C#数据结构之单链表(LinkList)实现方法.分享给大家供大家参考,具体如下: 这里我们来看下"单链表(LinkList)".在上一篇<C#数据结构之顺序表(SeqList)实例详解>的最后,我们指出了:顺序表要求开辟一组连续的内存空间,而且插入/删除元素时,为了保证元素的顺序性,必须对后面的元素进行移动.如果你的应用中需要频繁对元素进行插入/删除,那么开销会很大. 而链表结构正好相反,先来看下结构: 每个元素至少具有二个属性:data和next.data
C语言数据结构之图的遍历实例详解

C语言数据结构之图的遍历实例详解输入一组顶点,建立无向图的邻接矩阵.输入一组顶点,建立有向图的邻接表.分别对无向图和有向图进行DFS(深度优先遍历)和BFS(广度优先遍历).写出深度优先遍历的递归和非递归算法.根据建立的有向图,判断该图是否是有向无环图,若是,则输出其一种拓扑有序序列. 实现代码: #include <stdio.h> #include <stdlib.h> #define MAX 20 typedef struct ArcNode{ int adjvex; st
javascript数据结构之双链表插入排序实例详解

本文实例讲述了javascript数据结构之双链表插入排序实现方法.分享给大家供大家参考,具体如下: 数组存储前提下,插入排序算法,在最坏情况下,前面的元素需要不断向后移,以便在插入点留出空位,让目标元素插入. 换成链表时,显然无需做这种大量移动,根据每个节点的前驱节点"指针",向前找到插入点后,直接把目标值从原链表上摘下,然后在插入点把链表断成二截,然后跟目标点重新接起来即可. <!doctype html> <html> <head> <t
数据结构 C语言实现循环单链表的实例

数据结构 C语言实现循环单链表的实例实例代码: //=========杨鑫========================// //循环单链表的实现 #include <stdio.h> #include <stdlib.h> typedef int ElemType; //定义结点类型 typedef struct Node { ElemType data; struct Node *next; }Node,*LinkedList; int count = 0; //1.单循环
C语言数据结构之单链表的实现

目录一.为什么使用链表二.链表的概念三.链表的实现 3.1 创建链表前须知 3.2 定义结构体 3.3 申请一个节点 3.4 链表的头插 3.5 链表的尾插 3.6 链表的尾删 3.7 链表的头删 3.8 寻找某节点 3.9 在指定节点前插入节点 3.10 删除指定节点前的节点 3.11 链表的销毁一.为什么使用链表在学习链表以前,我们存储数据用的方式就是数组.使用数组的好处就是便于查找数据,但缺点也很明显. 使用前需声明数组的长度,一旦声明长度就不能更改插入和删除操作需要移动大量的
C语言数据结构之单链表与双链表的增删改查操作实现

目录前言单链表的增删改查定义结构体以及初始化增加结点删除结点查找修改结点移除结点最终效果双链表的基本操作初始化建表遍历双链表指定位置插入结点指定位置删除结点查找结点位置最终效果结语前言上篇博客分享了创建链表传入二级指针的细节,那么今天就分享几个c语言课程实践设计吧.这些程序设计搞懂了的话相当于链表的基础知识牢牢掌握了,那么再应对复杂的链表类的题也就能慢慢钻研了.学习是一个积累的过程,想要游刃有余就得勤学苦练! 单链表的增删改查 (1)项目需求构造带有头结点的
C语言数据结构之单链表存储详解

目录 1.定义一个链表结点 2.初始化单链表 3.输出链表数据 4.完整代码如果说,顺序表的所占用的内存空间是连续的,那么链表则是随机分配的不连续的,那么为了使随机分散的内存空间串联在一起形成一种前后相连的关系,指针则起到了关键性作用. 单链表的基本结构: 头指针:永远指向链表第一个节点的位置. 头结点:不存任何数据的空节点,通常作为链表的第一个节点.对于链表来说,头节点不是必须的,它的作用只是为了方便解决某些实际问题. 首元结点:首个带有元素的结点. 其他结点:链表中其他的节点. 1.定义一
C语言数据结构之单链表操作详解

目录 1.插入操作 2.删除操作 3.查找操作 4.修改操作 5.完整代码 1.插入操作 (1)创建一个新的要插入的结点 (2)将新结点的 next 指针指向插入位置后的结点 (3)将插入位置前的节点指针 next 指向新的结点注意:步骤(2)(3)的顺序不能颠倒,否则会导致插入位置后的部分链表丢失. 插入位置一共分三种,分别是头部插入.中间插入和尾部插入. 如图: 代码: link* insertElem(link* p,int elem,int pos){ link* temp = p;/
C语言数据结构之单链表的查找和建立

目录单链表的查找按位查找按值查找单链表的建立尾插法头插法建立单链表单链表的查找其实在单链表的插入和删除中,我们已经使用过单链表的查找方法,因为插入和删除的前提都是先找到对应的结点,所以这里就不再多解释按位查找 GetElem(L, i):按位查找操作.获取表 L 中第 i 个位置的元素的值 //按位查找 LNode * GetElem(LinkList L, int i) { if (i < 0) return false; LNode *p; //指针p指向当前扫描到的结点