: 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()
}