1. 首页
  2. 文章

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

Zppj · · 311 次点击 · · 开始浏览    
这是一个创建于 的文章，其中的信息可能已经有所发展或是发生改变。
第一次，站长亲自招 Gopher 了>>>

目的

  • 完善链表相关的概念，实现双向链表的常用方法。

1、双向链表的特点和初始化

1.1 双向链表的存储结构

存储结构

1.2 双向链表的特性

  • 我觉得用下面这行代码最能够展示双向链表的特性
p->next->prior = p->prior->next = p

1.3 双向链表的结点

  • 本文实现的双向链表结构如下


    结点

1.4 双向链表的基本操作

  • 本文主要实现了双向链表的以下操作
    • 判断是否为空
    • 获取链表长度
    • 在头部插入元素
    • 在尾部插入元素
    • 删除指定位置元素
    • 删除指定值的元素
    • 查找是否包含指定值
    • 查找指定位置元素的值
    • 遍历链表所有结点

1.5 双向链表的初始化

//定义双向链表结构体

type DuLNode struct {
    data  interface{} //数据域
    prior *DuLNode    //指针域 -> 指向直接前驱
    next  *DuLNode    //指针域 -> 指向直接后继
}

type DuList struct {
    length   int //储存链表的长度
    headNode *DuLNode
}

func InitDuList() *DuList {
    //即构造一个空的双向链表L(包含空的头结点)
    node := new(DuLNode)
    L := new(DuList)
    L.headNode = node
    return L
}

//这个非空判断也可以判断list.headNode.next == nil来完成
func (list *DuList) IsNull() bool {
    if list.length == 0 {
        return true
    } else {
        return false
    }
}

2、双向链表的插入

  • 同样，首先来实现双向链表的插入操作

2.1、在指定位置插入元素

//双向链表的插入(均为前插)
func (list *DuList) InsertElem(index int, v interface{}) {
    if index <= 0 || index > list.length {
        fmt.Println("err")
    } else {
        head := list.headNode
        fnode := head.next
        node := &DuLNode{data: v}
        if index == 1 { //处理向第一位插入
            node.next = head.next
            node.prior = head
            head.next = node
        } else {
            for count := 1; count < index; count++ {
                fnode = fnode.next
            }
            fnode.prior.next = node
            node.prior = fnode.prior
            node.next = fnode
        }
        list.length++
    }
}

2.2、在头部插入元素

//从头部添加元素
func (list *DuList) AddElem(v interface{}) {
    node := &DuLNode{data: v}
    head := list.headNode
    if list.IsNull() { //处理空表的插入
        head.next = node
        node.prior = head
    } else {
        fnode := head.next
        head.next = node
        node.prior = head
        node.next = fnode
        fnode.prior = node
    }
    list.length++
    return
}

2.3、在尾部插入元素

//从尾部插入元素
func (list *DuList) AppendElem(v interface{}) {
    node := &DuLNode{data: v}
    head := list.headNode
    if list.IsNull() {  //处理空表
        head.next = node
        node.prior = head
    } else {
        lnode := head.next
        for lnode.next != nil {
            lnode = lnode.next
        }
        lnode.next = node
        node.prior = lnode
    }
    list.length++
    return
}

3、双向链表的删除------总结go如何实现while

3.1、删除指定值的元素

//按值移除元素
func (list *DuList) RemoveElem(v interface{}) {
    head := list.headNode
    fnode := head.next
    if fnode.data == v { //处理移除的元素是第一个
        fnode.next.prior = head
        head.next = fnode.next
        list.length--
        return
    } else {
        for fnode.next != nil { //处理中段
            if fnode.data == v {
                fnode.prior.next = fnode.next
                fnode.next.prior = fnode.prior
                list.length--
                return
            } else {
                fnode = fnode.next
            }
        }
        if fnode.next == nil && fnode.data == v {
           //处理最后一个元素，由于go语言不含while语句，且此时已经到达链尾，需要对链尾元素做以此判断
            fnode.prior.next = nil
            fnode.prior = nil
            list.length--
            return
        }
        fmt.Println("fail")
        return
    }
}

3.2 删除指定位置的元素

//按位移除元素
func (list *DuList) DeleteElem(index int) {
    if index <= 0 || index > list.length {
        fmt.Println("删除位置不合理")
        return
    } else {
        head := list.headNode
        fnode := head.next
        if index == 1 {
            fnode.next.prior = head
            head.next = fnode.next
        } else {
            for count := 0; count < index-1; count++ {
                fnode = fnode.next
            }
            if index == list.length { //处理最后一位元素，与删除指定值遇到的问题相同
                fnode.prior.next = nil
                fnode.prior = nil
                list.length--
                return
            }
            fnode.prior.next = fnode.next
            fnode.next.prior = fnode.prior
        }
        list.length--
        return
    }
}

4、双向链表的查询

4.1、查询是否包含指定值(按值查询)

//双向链表的按值查找
func (list *DuList) LocateElem(v interface{}) bool {
    if list.IsNull() {
        fmt.Println("err")
        return false
    } else {
        head := list.headNode
        fnode := head.next
        for fnode.next != nil {
            if fnode.data == v {
                return true
            }
            fnode = fnode.next
        }
        if fnode.data == v { //由于go语言不含while语句，且此时已经到达链尾，需要对链尾元素做以此判断
            return true
        }
        return false
    }
}

4.2、查询指定位置的值

//双向链表的取值
func (list *DuList) GetElem(index int) int {
    if index <= 0 || index > list.length {
        return 0
    } else {
        head := list.headNode
        fnode := head.next
        for j := 1; j < index; j++ {
            if fnode.next != nil {
                fnode = fnode.next
            }
        }
        return fnode.data.(int)
    }
}

4.3、遍历双向链表

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

5、完整代码及结果展示

package main

import "fmt"

//定义单链表结构体

type DuLNode struct {
    data  interface{} //数据域
    prior *DuLNode    //指针域 -> 指向直接前驱
    next  *DuLNode    //指针域 -> 指向直接后继
}

type DuList struct {
    length   int //储存链表的长度
    headNode *DuLNode
}

// 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、遍历链表所有结点
// }
func InitDuList() *DuList {
    //即构造一个空的双向链表L(包含头指针)
    node := new(DuLNode)
    L := new(DuList)
    L.headNode = node
    return L
}

//双向链表的取值
func (list *DuList) GetElem(index int) int {
    if index <= 0 || index > list.length {
        return 0
    } else {
        head := list.headNode
        fnode := head.next
        for j := 1; j < index; j++ {
            if fnode.next != nil {
                fnode = fnode.next
            }
        }
        return fnode.data.(int)
    }
}

//双向链表的按值查找
func (list *DuList) LocateElem(v interface{}) bool {
    if list.IsNull() {
        fmt.Println("err")
        return false
    } else {
        head := list.headNode
        fnode := head.next
        for fnode.next != nil {
            if fnode.data == v {
                return true
            }
            fnode = fnode.next
        }
        if fnode.data == v { //由于go语言不含while语句，且此时已经到达链尾，需要对链尾元素做以此判断
            return true
        }
        return false
    }
}

//双向链表的插入(均为前插)
func (list *DuList) InsertElem(index int, v interface{}) {
    if index <= 0 || index > list.length {
        fmt.Println("err")
    } else {
        head := list.headNode
        fnode := head.next
        node := &DuLNode{data: v}
        if index == 1 { //处理向第一位插入
            node.next = head.next
            node.prior = head
            head.next = node
        } else {
            for count := 1; count < index; count++ {
                fnode = fnode.next
            }
            fnode.prior.next = node
            node.prior = fnode.prior
            node.next = fnode
        }
        list.length++
    }
}

//按位移除元素
func (list *DuList) DeleteElem(index int) {
    if index <= 0 || index > list.length {
        fmt.Println("删除位置不合理")
        return
    } else {
        head := list.headNode
        fnode := head.next
        if index == 1 {
            fnode.next.prior = head
            head.next = fnode.next
        } else {
            for count := 0; count < index-1; count++ {
                fnode = fnode.next
            }
            if index == list.length { //处理最后一位元素
                fnode.prior.next = nil
                fnode.prior = nil
                list.length--
                return
            }
            fnode.prior.next = fnode.next
            fnode.next.prior = fnode.prior
        }
        list.length--
        return
    }
}

//按值移除元素
func (list *DuList) RemoveElem(v interface{}) {
    head := list.headNode
    fnode := head.next
    if fnode.data == v { //处理移除的元素是第一个
        fnode.next.prior = head
        head.next = fnode.next
        list.length--
        return
    } else {
        for fnode.next != nil { //处理中段
            if fnode.data == v {
                fnode.prior.next = fnode.next
                fnode.next.prior = fnode.prior
                list.length--
                return
            } else {
                fnode = fnode.next
            }
        }
        if fnode.next == nil && fnode.data == v { //处理最后一个元素，
由于go语言不含while语句，且此时已经到达链尾，需要对链尾元素做以此判断
            fnode.prior.next = nil
            fnode.prior = nil
            list.length--
            return
        }
        fmt.Println("fail")
        return
    }
}

//这个非空判断也可以判断list.headNode.next == nil
func (list *DuList) IsNull() bool {
    if list.length == 0 {
        return true
    } else {
        return false
    }
}

//从头部添加元素
func (list *DuList) AddElem(v interface{}) {
    node := &DuLNode{data: v}
    head := list.headNode
    if list.IsNull() { //处理空表的插入
        head.next = node
        node.prior = head
    } else {
        fnode := head.next
        head.next = node
        node.prior = head
        node.next = fnode
        fnode.prior = node
    }
    list.length++
    return
}

func (list *DuList) AppendElem(v interface{}) {
    node := &DuLNode{data: v}
    head := list.headNode
    if list.IsNull() {
        head.next = node
        node.prior = head
    } else {
        lnode := head.next
        for lnode.next != nil {
            lnode = lnode.next
        }
        lnode.next = node
        node.prior = lnode
    }
    list.length++
    return
}

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

func main() {
    L := InitDuList()
    msg := []int{12, 5, 3, 8, 55, 13}
    for i := range msg {
        L.AppendElem(msg[i])
    }
    L.ShowList()
    L.RemoveElem(13)
    L.ShowList()
    L.DeleteElem(5)
    L.ShowList()
    L.InsertElem(2, 10)
    L.ShowList()
    fmt.Println(L.LocateElem(8))
    fmt.Println(L.GetElem(5))
}

//结果展示
        12      5       3       8       55      13
        12      5       3       8       55
        12      5       3       8
        12      10      5       3       8
true
8

6、总结

  • 在实现单链表时没有为链表设置一个空的头结点，本次为其添加了一个空的头结点，确实是会方便很多，对线性表有了更加清晰的了解。
  • go语言的循环语句只有if-else和for循环语句，导致在进行迭代时无法对最后一位元素进行操作，目前的解决办法是在进行最后一次循环结束后，再进行一次单独的判断。在学习go的do-while循环后，更新博客。
  • 参考博客

有疑问加站长微信联系（非本文作者）

本文来自：简书

感谢作者：Zppj

查看原文：go语言双向链表及其常用方法的实现

入群交流（和以上内容无关）：加入Go大咖交流群，或添加微信：liuxiaoyan-s 备注：入群；或加QQ群：692541889

311 次点击  
加入收藏 微博
赞
收入我的专栏
上一篇：Golang数据结构与算法系列：Skiplist跳跃表实现
下一篇：3. Go依赖管理及go module使用
  • 链表
  • 移除
  • 代码
  • 线性表
    0 回复
    暂无回复
    添加一条新回复 （您需要 登录 后才能回复 没有账号 ？）
    • 请尽量让自己的回复能够对别人有帮助
    • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
    • 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
    • 图片支持拖拽、截图粘贴等方式上传

    用户登录

    Go今日面试题

     今日阅读排行

      加载中

     一周阅读排行

      加载中

      关注我

    • 扫码关注领全套学习资料 关注微信公众号
    • 加入 QQ 群：
      • 192706294（已满）
      • 731990104（已满）
      • 798786647（已满）
      • 729884609（已满）
      • 977810755（已满）
      • 815126783（已满）
      • 812540095（已满）
      • 1006366459（已满）
      • 692541889

    • 关注微信公众号
    • 加入微信群：liuxiaoyan-s，备注入群
    • 也欢迎加入知识星球 Go粉丝们（免费）