28

数据结构——Golang实现单链表

 5 years ago
source link: https://studygolang.com/articles/17806?amp%3Butm_medium=referral
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

转载请注明出处： 数据结构——Golang实现单链表

aqeYBrY.png!web

Golang

1. 单链表

1.1. 定义

单向链表 （单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表；又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点；

列表是由结点构成，head指针指向第一个成为表头结点，而终止于最后一个指向nuLL的指针。

1.2. 优点

  1. 单个结点创建非常方便，普通的线性内存通常在创建的时候就需要设定数据的大小
  2. 结点的删除非常方便，不需要像线性结构那样移动剩下的数据
  3. 结点的访问方便，可以通过循环或者递归的方法访问到任意数据，但是平均的访问效率低于线性表。

2. Golang 实现

2.1. 相关结构体

首先需要先定义一下链表相关的结果， SingleObject 用于每个节点的数据，为interface{}结构， SingleNode 为链表中的节点， SingleList 单链表，为了多协程读写安全，所以在链表中加了读写锁。

具体定义如下：

// 节点数据
type SingleObject interface{}

// 单链表节点
type SingleNode struct {
    Data SingleObject
    Next *SingleNode
}

// 单链表
type SingleList struct{
    mutex *sync.RWMutex
    Head *SingleNode
    Tail *SingleNode
    Size uint
}

2.2. 链表初始化

定义完结构，接下来就需要对单链表进行初始化了。代码如下：

// 初始化
func (list *SingleList) Init()  {
    list.Size = 0
    list.Head = nil
    list.Tail = nil
    list.mutex = new(sync.RWMutex)
}

2.3. 新增节点

链表节点的新增分为两种，一种是在链表后面追加节点，该方式，我们称为append；另外一种方式是在指定位置插入节点，我们叫做insert。

另外新增时，若为第一个节点需特殊处理一下。下面请看代码：

// 添加节点到链表尾部
func (list *SingleList)Append(node *SingleNode) bool {
    if node == nil{
        return false
    }
    list.mutex.Lock()
    defer list.mutex.Unlock()
    if list.Size == 0{
        list.Head = node
        list.Tail = node
        list.Size = 1
        return true
    }

    tail := list.Tail
    tail.Next = node
    list.Tail = node
    list.Size += 1
    return true
}

// 插入节点到指定位置
func (list *SingleList)Insert(index uint, node *SingleNode) bool {
    if node == nil {
        return false
    }

    if index > list.Size{
        return false
    }

    list.mutex.Lock()
    defer list.mutex.Unlock()

    if index == 0{
        node.Next = list.Head
        list.Head = node
        list.Size += 1
        return true
    }
    var i uint
    ptr := list.Head
    for i = 1; i < index; i ++ {
        ptr = ptr.Next
    }
    next := ptr.Next
    ptr.Next = node
    node.Next = next
    list.Size += 1
    return true
}

2.4. 删除节点

有了新增功能自然就少不了删除，此外，删除节点时，如果指定的位置是链表的头部或尾部，都需要特殊处理下。看代码：

// 删除指定位置的节点
func (list *SingleList)Delete(index uint) bool {
    if list == nil || list.Size == 0 || index > list.Size - 1 {
        return false
    }

    list.mutex.Lock()
    defer list.mutex.Unlock()

    if index == 0 {
        head := list.Head.Next
        list.Head = head
        if list.Size == 1{
            list.Tail = nil
        }
        list.Size -= 1
        return true
    }

    ptr := list.Head
    var i uint
    for i = 1; i < index; i++{
        ptr = ptr.Next
    }
    next := ptr.Next
    
    ptr.Next = next.Next
    if index == list.Size - 1 {
        list.Tail = ptr
    }
    list.Size -= 1
    return true
}

2.6. 查询节点

根据指定的位置索引，查询出节点内容。

// 获取指定位置的节点，不存在则返回nil
func (list *SingleList)Get(index uint) *SingleNode{
    if list == nil || list.Size == 0 || index > list.Size - 1 {
        return nil
    }

    list.mutex.RLock()
    defer list.mutex.RUnlock()
    
    if index == 0{
        return list.Head
    }
    node := list.Head
    var i uint
    for i = 0; i < index; i ++ {
        node = node.Next
    }
    return node
}

2.7. 打印链表

最后，我们增加一个打印链表的功能，方便我们看整个链表的内容：

// 输出链表
func (list *SingleList)Display(){
    if list == nil {
        fmt.Println("this single list is nil")
        return
    }
    list.mutex.RLock()
    defer list.mutex.RUnlock()
    fmt.Printf("this single list size is %d \n", list.Size)
    ptr := list.Head
    var i uint
    for i = 0; i < list.Size; i++{
        fmt.Printf("No%3d data is %v\n", i + 1, ptr.Data)
        ptr = ptr.Next
    }
}

完

转载请注明出处: 数据结构——Golang实现单链表


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK