: jank : : 4688 : 2018-02-27 19:57 数据结构和算法
双向链表结构:双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。
下面使用golang实现了双向链表的添加,元素前插入,元素后插入,序号前插入,序号后插入,顺序查询某个序号的元素,倒序查询某个序号的元素, 查询链表全部元素,删除某个序号的元素, 以及删除整个链表等功能。
package main import ( "errors" "fmt" ) var ( NUMERROR = errors.New("num large this list size") ) //双链表元素 type Data struct { data interface{} pre *Data next *Data } //双链表结构 type List struct { size int head *Data tail *Data } //链尾添加数据 func (this *List) Append(data *Data) bool { if data == nil { return false } data.next = nil //链尾的后面为nil if this.size == 0 { //判断链表是否为空 data.pre = nil this.head = data } else { data.pre = this.tail this.tail.next = data } this.tail = data this.size++ return true } //在链表某个Data后插入数据 func (this *List) InsertNext(obj *Data, data *Data) bool { if data == nil || obj == nil { return false } if obj == this.tail { this.Append(data) } else { data.next = obj.next data.pre = obj obj.next = data data.next.pre = data this.size++ } return true } //在链表具体某个Data前插入数据 func (this *List) InsertPre(obj *Data, data *Data) bool { if data == nil || obj == nil { return false } if obj != this.head { this.InsertNext(obj.pre, data) } else { //判断如果指定插入的数据为头 data.pre = nil data.next = obj obj.pre = data this.head = data this.size++ } return true } //在链表某个序号后插入数据 func (this *List) InsertNextInt(num int, data *Data) bool { if data == nil || num > this.size-1 || num < 0 { return false } if this.size == 0 || num == this.size-1 { this.Append(data) } else { predata, err := this.GetOrder(num) if err != nil { fmt.Println(err) return false } data.next = predata.next data.pre = predata predata.next = data data.next.pre = data this.size++ } return true } //在链表某个序号前插入数据 func (this *List) InsertPreInt(num int, data *Data) bool { if data == nil || num < 0 { return false } if num == 0 { data.pre = nil nextdata := this.head data.next = nextdata nextdata.pre = data this.head = data this.size++ } else { return this.InsertNextInt(num-1, data) } return true } //顺序查询某个序号数据 func (this *List) GetOrder(num int) (data *Data, err error) { switch { case this.size == 0: data = nil case num == 0: data = this.head case num > this.size-1: fmt.Println("size: ", this.size-1, "num: ", num) err = NUMERROR case num == this.size-1: data = this.tail default: data = this.head for i := 0; i < num; i++ { data = data.next } } return } //倒序查询某个序号数据 func (this *List) GetReverse(num int) (data *Data, err error) { switch { case num == 0: data = this.tail case num > this.size-1: err = NUMERROR case num == this.size-1: data = this.head default: data = this.tail for i := 0; i < num; i++ { data = data.pre } } return } //遍历查询链表全部数据并赋值给切片 func (this *List) GetAll() (datas []*Data) { if this.size == 0 { return nil } item := this.head for i := 0; i < this.size; i++ { fmt.Printf("[%d : %v] -> ", i, item.data) datas = append(datas, item) item = item.next } fmt.Println("nil") return } //删除某个序号的数据 func (this *List) Remove(num int) (err error) { if this.size == 0 { err = errors.New("this list is nil") return } var rem *Data if rem, err = this.GetOrder(num); err != nil { fmt.Println(err) return } if num == 0 { rem.next.pre = nil this.head = rem.next } else if num == this.size-1 { rem.pre.next = nil this.tail = rem.pre } else { rem.pre.next = rem.next rem.next.pre = rem.pre } rem.pre = nil //避免内存泄漏 rem.next = nil this.size-- return } //删除链表全部数据 func (this *List) RemoveAll() bool { for i := 0; i < this.size; i++ { rem := this.head this.head = rem.next rem.next = nil rem.pre = nil } this.tail = nil this.size = 0 return true } func NewList() (list *List) { list = new(List) list.size = 0 list.head = nil list.tail = nil return } func main() { list := NewList() a := list.Append(&Data{data: "jank"}) b := list.Append(&Data{data: "满城烟花"}) c := list.InsertPreInt(0, &Data{data: 34}) d := list.InsertNextInt(2, &Data{data: "jason"}) e := list.InsertPre(list.tail, &Data{data: 12}) f := list.InsertNext(list.head, &Data{data: 56}) dd, _ := list.GetReverse(1) list.InsertPre(dd, &Data{data: 112}) ee, _ := list.GetOrder(1) list.InsertPre(ee, &Data{data: 1}) fmt.Println("a: ", a, ", b: ", b, ", c: ", c, ", d: ", d, ", e: ", e, ", f: ", f) fmt.Println("size:", list.size, " head: ", list.head.data, " tail: ", list.tail.data) list.GetAll() //remove //fmt.Println(list.Remove(1)) //fmt.Println("size:", list.size, " head: ", list.head.data, " tail: ", list.tail.data) //list.GetAll() //removeall list.RemoveAll() fmt.Println("size:", list.size, " head: ", list.head, " tail: ", list.tail) list.GetAll() }