美文网首页
Golang数据结构 - 4 - 链表

Golang数据结构 - 4 - 链表

作者: vouv | 来源:发表于2020-02-07 13:44 被阅读0次
     __       __  .__   __.  __  ___  _______  _______      __       __       _______.___________.
    |  |     |  | |  \ |  | |  |/  / |   ____||       \    |  |     |  |     /       |           |
    |  |     |  | |   \|  | |  '  /  |  |__   |  .--.  |   |  |     |  |    |   (----`---|  |----`
    |  |     |  | |  . `  | |    <   |   __|  |  |  |  |   |  |     |  |     \   \       |  |     
    |  `----.|  | |  |\   | |  .  \  |  |____ |  '--'  |   |  `----.|  | .----)   |      |  |     
    |_______||__| |__| \__| |__|\__\ |_______||_______/    |_______||__| |_______/       |__|     
    

    上一章中我们学习了队列以及相关的基本操作,并有数组切片和链表两种不同的实现方式,本章我们将对链表进行单独介绍。

    如果我们需要存储操作一系列的数据,使用数组(或列表)是最常用的数据结构。但是在大多数编程语言中数组的长度是固定的(虽然Go有切片),如果我们使用数组存取数据,遇到需要移动数据的操作其实成本是很高的,有时候也会碰到浪费大量内存的情况。使用链表可以解决这些问题。

    本章内容包括:

    • 链表数据结构
    • 向链表添加元素
    • 从链表移除元素
    • 双向链表
    • 循环链表
    • 排序链表
    • 通过链表实现栈

    链表定义

    链表主要包含以下接口:

    • Push(e ...Element):向链表尾部添加若干新元素
    • Insert(element Element, position int):在指定位置插入元素
    • GetElementAt(index int) Element:获取特定位置元素
    • Remove(element Element):删除特定元素
    • RemoveAt(position int):删除特定位置元素
    • IndexOf(element Element) int:返回特定元素索引
    • Size() int:返回链表包含元素个数
    • IsEmpty() bool:若链表为空返回 true
    type Element interface {
    }
    
    type List interface {
    
        // 向链表尾部添加若干新元素
        Push(e ...Element)
    
        // 在指定位置插入元素
        Insert(element Element, position int)
    
        // 获取特定位置元素
        GetElementAt(index int) Element
    
        // 删除特定元素
        Remove(element Element)
        RemoveAt(position int)
    
        // 返回特定元素索引
        IndexOf(element Element) int
    
        // 返回链表包含元素个数
        Size() int
    
        // 若链表为空返回 true
        IsEmpty() bool
    }
    
    type Node struct {
        Value Element
        Next  *Node
    }
    
    type LinkedList struct {
        Head *Node
        size int
    }
    

    向链表尾部添加元素

    // 在末端插入若干新元素
    func (s *LinkedList) Push(e ...Element) {
        iter := s.Head
        for _, v := range e {
            node := &Node{
                Value: v,
                Next:  nil,
            }
            for iter.Next != nil {
                iter = iter.Next
            }
            // 此时iter为最后一项
            iter.Next = node
            s.size++
        }
    }
    

    向链表指定位置插入元素

    // 在指定位置插入新元素
    func (s *LinkedList) Insert(element Element, position int) {
        if position > s.Size()-1 {
            return
        }
        iter := s.Head
        for step := position; step > 0; step-- {
            iter = iter.Next
        }
        node := &Node{
            Value: element,
            Next:  iter.Next,
        }
        iter.Next = node
        s.size++
    }
    

    从链表中移除元素

    // 删除指定元素
    func (s *LinkedList) Remove(element Element) {
        last := s.Head
        for iter := s.Head; iter.Next != nil; iter = iter.Next {
            if iter.Value == element {
                last.Next = iter.Next
                return
            }
            last = iter
        }
    }
    
    // 删除指定位置的元素
    func (s *LinkedList) RemoveAt(position int) {
        if position > s.Size()-1 {
            return
        }
        iter := s.Head
        last := s.Head
        for step := position; step > 0; step-- {
            last = iter
            iter = iter.Next
        }
        last.Next = iter.Next
        s.size--
    }
    

    IsEmpty方法和Size方法

    // 链表大小
    func (s *LinkedList) Size() int {
        return s.size
    }
    
    // 链表是否为空
    func (s *LinkedList) IsEmpty() bool {
        return s.Size() == 0
    }
    

    完整实现

    package main
    
    import "fmt"
    
    type Element interface {
    }
    
    type List interface {
    
        // 向链表尾部添加若干新元素
        Push(e ...Element)
    
        // 在指定位置插入元素
        Insert(element Element, position int)
    
        // 获取特定位置元素
        GetElementAt(index int) Element
    
        // 删除特定元素
        Remove(element Element)
        RemoveAt(position int)
    
        // 返回特定元素索引
        IndexOf(element Element) int
    
        // 返回链表包含元素个数
        Size() int
    
        // 若链表为空返回 true
        IsEmpty() bool
    }
    
    type Node struct {
        Value Element
        Next  *Node
    }
    
    type LinkedList struct {
        Head *Node
        size int
    }
    
    // 在末端插入若干新元素
    func (s *LinkedList) Push(e ...Element) {
        iter := s.Head
        for _, v := range e {
            node := &Node{
                Value: v,
                Next:  nil,
            }
            for iter.Next != nil {
                iter = iter.Next
            }
            // 此时iter为最后一项
            iter.Next = node
            s.size++
        }
    }
    
    // 在指定位置插入新元素
    func (s *LinkedList) Insert(element Element, position int) {
        if position > s.Size()-1 {
            return
        }
        iter := s.Head
        for step := position; step > 0; step-- {
            iter = iter.Next
        }
        node := &Node{
            Value: element,
            Next:  iter.Next,
        }
        iter.Next = node
        s.size++
    }
    
    // 返回指定位置的元素
    func (s *LinkedList) GetElementAt(index int) Element {
        if index > s.Size()-1 {
            return nil
        }
        iter := s.Head
        for step := index; step > -1; step-- {
            iter = iter.Next
        }
        return iter.Value
    }
    
    // 删除指定元素
    func (s *LinkedList) Remove(element Element) {
        last := s.Head
        for iter := s.Head; iter.Next != nil; iter = iter.Next {
            if iter.Value == element {
                last.Next = iter.Next
                return
            }
            last = iter
        }
    }
    
    // 删除指定位置的元素
    func (s *LinkedList) RemoveAt(position int) {
        if position > s.Size()-1 {
            return
        }
        iter := s.Head
        last := s.Head
        for step := position; step > 0; step-- {
            last = iter
            iter = iter.Next
        }
        last.Next = iter.Next
        s.size--
    }
    
    // 获取指定元素位置
    func (s *LinkedList) IndexOf(element Element) int {
        idx := -1
        iter := s.Head
        for iter.Next != nil {
            idx++
            iter = iter.Next
            if iter.Value == element {
                return idx
            }
        }
        return -1
    }
    
    // 链表大小
    func (s *LinkedList) Size() int {
        return s.size
    }
    
    // 链表是否为空
    func (s *LinkedList) IsEmpty() bool {
        return s.Size() == 0
    }
    
    func NewLinkedList() List {
        return &LinkedList{
            Head: &Node{},
            size: 0,
        }
    }
    
    func main() {
        list := NewLinkedList()
    
        fmt.Println("Push:1,2,3,4,5,6,7,8,9")
        list.Push(1, 2, 3, 4, 5, 6, 7, 8, 9)
        fmt.Println("Size:", list.Size())
    
        fmt.Println("Get idx=8:", list.GetElementAt(8))
    
        fmt.Println("Index of 9:", list.IndexOf(1))
    
        fmt.Println("Insert 20 at 3")
        list.Insert(20, 3)
        fmt.Println("Get idx=3:", list.GetElementAt(3))
    
        fmt.Println("Remove idx=3: done")
        list.RemoveAt(3)
        fmt.Println("Get idx=3:", list.GetElementAt(3))
    
        list.Remove(4)
        fmt.Println("Remove element=4: done")
    
        fmt.Println("Get idx=3:", list.GetElementAt(3))
    
    }
    

    运行结果

    Push:1,2,3,4,5,6,7,8,9
    Size: 9
    Get idx=8: 9
    Index of 9: 0
    Insert 20 at 3
    Get idx=3: 20
    Remove idx=3: done
    Get idx=3: 4
    Remove element=4: done
    Get idx=3: 5
    
    Process finished with exit code 0
    

    双向链表

    循环链表

    相关文章

      网友评论

          本文标题:Golang数据结构 - 4 - 链表

          本文链接:https://www.haomeiwen.com/subject/uvauqctx.html