go 语言实现通用单链表

## 链表定义 ### 定义错误 ```go import "errors" var ( //ErrIndex 超出列表索引 ErrIndex = errors.New("out of list index") //ErrNotFound 没有找到该元素 ErrNotFound = errors.New("not found this element") ) ``` ### 定义接口 ```go // Comparer 数据接口 type Comparer interface { compare(data interface{}) bool } ``` ### 定义链表结点 ```go // SingleElement 列表结点 type SingleElement struct { Data Comparer next *SingleElement } // SingleLink 列表 type SingleLink struct { head *SingleElement lenght int } ``` ### 链表初始化 ```go // Single 新建一个空列表 func Single() *SingleLink { return &SingleLink{ head: &SingleElement{}, } } ``` ### 链表插入 ```go // Insert 在列表的第几个位置插入元素 func (l *SingleLink) Insert(i int, data Comparer) error { maxLen := l.Length() + 1 if i <= 0 || i > maxLen { return ErrIndex } p := l.head for j := 1; j < i; j++ { p = p.next } p.next = &SingleElement{ Data: data, next: p.next, } l.lenght++ return nil } ``` ### 链表删除 ```go // Delete 删除制定位置的元素 func (l *SingleLink) Delete(i int) (data Comparer, err error) { if i <= 0 || i > l.Length() { return nil, ErrIndex } p := l.head for j := 1; j < i; j++ { p = p.next } data = p.next.Data p.next = p.next.next l.lenght-- return data, nil } ``` ### 链表长度 ```go // Length 获取列表的长度 func (l *SingleLink) Length() int { return l.lenght } ``` ### 获取指定位置的元素 ```go // GetElem 获取指定位置元素 func (l *SingleLink) GetElem(i int) (e *SingleElement, err error) { if i <= 0 || i > l.Length() { return nil, ErrIndex } p := l.head for j := 1; j <= i; j++ { p = p.next } e = p return } ``` ### 查找元素位置 ```go // LocateElem 获取指定值的索引 func (l *SingleLink) LocateElem(data Comparer) (i int, err error) { p := l.head.next for p != nil { i++ if p.Data.compare(data) { return i, nil } p = p.next } i = 0 err = ErrNotFound return } ``` ### 实现Stringer接口 ```go // String 实现Stringer接口 func (l *SingleLink) String() string { lstr := "\nlist:\n" for p := l.head.next; p != nil; { lstr += fmt.Sprintln("\t", p.Data) p = p.next } return lstr } ``` ### 链表反转 ```go // Reverse 反转列表 func (l *SingleLink) Reverse() error { if l.Length() == 0 { return nil } p := l.head.next pre := p.next p.next = nil for pre != nil { t := pre.next pre.next = p p, pre = pre, t } l.head.next = p return nil } ``` ### 链表合并 ```go // Union 两个链表合并 func (l *SingleLink) Union(sl *SingleLink) error { p := l.head for p.next != nil { p = p.next } p.next = sl.head.next l.lenght += sl.lenght return nil } ``` ## 链表使用 ```go type Age int func (a Age) compare(data interface{}) bool { if a == data { return true } return false } l := Single() l.Insert(1, Age(1)) l.Insert(2, Age(2)) l.Insert(3, Age(3)) fmt.Println(l) ``` github: https://github.com/daymenu/gods.git