go实现排序的链表

mahang · · 3849 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

链表的数据结构比较线性数组,优点是 可以方便的对任意的位置进行插入和删除。

这一特性使得它很适合于应用在排序等场景下,由于golang目前类库还不是很完善,在java中可以很简单的使用api提供的支持完成对list或者map的排序,在使用go时就没有那么幸运了,可能需要自己去实现。

下面的例子就是使用go package 中的LinkedList实现的排序的链表。

  • 有几个功能特性:

1.支持固定的长度

2.可自定义排序的规则

3.组合LinkedList功能

package codeforfun
import (
    "container/list"
)
type SortedLinkedList struct {
    *list.List
    Limit int
    compareFunc func (old, new interface{}) bool
}
func NewSortedLinkedList(limit int, compare func (old, new interface{}) bool) *SortedLinkedList {
    return &SortedLinkedList{list.New(), limit, compare}
}
func (this SortedLinkedList) findInsertPlaceElement(value interface{}) *list.Element {
    for element := this.Front(); element != nil; element = element.Next() {
        tempValue := element.Value
        if this.compareFunc(tempValue, value) {
            return element
        }
    }
    return nil
}
func (this SortedLinkedList) PutOnTop(value interface{}) {
    if this.List.Len() == 0 {
        this.PushFront(value)
        return
    }
    if this.List.Len() < this.Limit && this.compareFunc(value, this.Back().Value) {
        this.PushBack(value)
        return
    }
    if this.compareFunc(this.List.Front().Value, value) {
        this.PushFront(value)
    } else if this.compareFunc(this.List.Back().Value, value) && this.compareFunc(value, this.Front().Value) {
        element := this.findInsertPlaceElement(value)
        if element != nil {
            this.InsertBefore(value, element)
        }
    }
    if this.Len() > this.Limit {
        this.Remove(this.Back())
    }
}
  • 使用方法:
package main
import (
    "fmt"
    "codeforfun"
)
type WordCount struct {
    Word  string
    Count int
}
func compareValue(old, new interface {}) bool {
    if new.(WordCount).Count > old.(WordCount).Count {
        return true
    }
    return false
}
func main() {
    wordCounts := []WordCount{
        WordCount{"kate", 87},
        WordCount{"herry", 92},
        WordCount{"james", 81}}
    var aSortedLinkedList = codeforfun.NewSortedLinkedList(10, compareValue)
    for _, wordCount := range wordCounts {
        aSortedLinkedList.PutOnTop(wordCount)
    }
    for element := aSortedLinkedList.List.Front(); element != nil; element = element.Next() {
        fmt.Println(element.Value.(WordCount))
    }
}

  

还可以访问我树莓派上搭的博客地址:

http://www.codeforfun.info/

 

 


微信扫码关注站长公众号,和站长交流学习

本文来自:博客园

感谢作者:mahang

查看原文:go实现排序的链表

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:731990104

3849 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传