01 基本数据结构：数组与链表

线性表是最基本、最简单、最常用的一种数据结构之一。在实际应用中，线性表都是以数组、字符串、链表、栈、队列、位图等特殊线性表的形式来使用的。因为这些特殊线性表都具有自己的特性，所以掌握这些特殊线性表的特性，对于数据运算的可靠性和提高操作效率是至关重要的。

线性表是一个线性结构，它是一个含有n≥0个节点的有限序列。在节点中，有且仅有一个开始节点没有前驱并有一个后继节点，有且仅有一个终端节点没有后继并有一个前驱节点。 其他的节点都有且仅有一个前驱和一个后继节点。

通常可以把一个线性表表示成一个线性序列：k1，k2，…，kn，其中k1是开始节点，kn是终端节点。

在编程领域中，线性结构具有如下两个基本特征：

• （1）列表中必存在唯一的“第一元素”和唯一的“最后元素”。
• （2）除最后一个元素之外，均有唯一的后继和唯一的前驱。

由n（n≥0）个数据元素（节点）a1，a2，…，an组成的有限序列，数据元素的个数n定义为表的长度。

当n=0时称为空表，我们通常将非空的线性表（n>0）记作：

(a1,a2,…,an)数据元素ai（1≤i≤n）没有特殊含义，大家不必去“刨根问底”地研究它。它只是一个抽象的符号，其具体含义在不同的情况下可以不同。

线性表虽然只是一个线性序列，但是其操作功能非常强大，具备了很多操作技能。

线性表的基本操作过程如下所示：

• （1）用Setnull(L)置空表。
• （2）用Length(L)求表的长度和表中各元素的个数。
• （3）用Get(L,i)获取表中的第i个元素（1≤i≤n）。
• （4）用Prior(L,i)获取i的前趋元素。
• （5）用Next(L,i)获取i的后继元素。
• （6）用Locate(L,x)返回指定元素在表中的位置。
• （7）用Insert(L,i,x)插入新元素。
• （8）用Delete(L,x)删除已存在的元素。
• （9）用Empty(L)来判断表是否为空。

• 均匀性：虽然不同数据表的数据元素是各种各样的，但同一线性表的各数据元素必须有相同的类型和长度。
• 有序性：各数据元素在线性表中的位置只取决于它们的序。数据元素之前的相对位置是线性的，

即存在唯一的“第一个”和“最后一个”的数据元素，除了第一个和最后一个外，其他元素前面只有一个数据元素直接前趋，后面只有一个直接后继。

1.顺序存储结构： 连续内存的线性存储结构，如数组、切片。

顺序表有一个硬性规定，即用连续的存储单元顺序存储线性表中的各元素。 根据这条硬性规定，当对顺序表进行插入和删除操作时，必须移动数据元素才能实现线性表逻辑上的相邻关系。 很不幸的是，这种操作会影响运行效率。

2.链式存储结构： 存储的值可以是不连续内存，每个节点都持有下一节点（或上一节点）的指针，链式存储结构不需要用地址连续的存储单元来实现，而是通过“链”建立起数据元素之间的次序关系。 所以它不要求逻辑上相邻的两个数据元素在物理结构上也相邻，在插入和删除时无须移动元素，从而提高了运行效率。 链式存储结构主要有单链表、循环链表、双向链表、静态链表等几种形式。

大多数语言在底层已经提供数组的实现，且是最基本的数据结构，是其他数据结构的基础。Go语言除数组外，更常用的是切片，在标准包中也提供了双向链表的包。这里为了演示线性表的这两种结构，我写了一些模拟代码：

// 自定义切片类型，切片底层为数组
type ListArray []interface{}

// 数组工厂方法
func NewArray(n int) *ListArray {
	slice := make([]interface{}, 0, n)
	a := ListArray(slice)
	return &a
}

// 计算顺序表长度；
func (a *ListArray) Len() int {
	return len(*a)
}

// 计算顺序表容量；
func (a ListArray) Cap() int {
	return cap(a)
}

// 清空操作；
func (a *ListArray) Clean() {
	*a = nil
}

// 判断是否为空；
func (a *ListArray) IsEmpty() bool {
	return len(*a) == 0
}

// 判断是否为满；
func (a *ListArray) IsFilled() bool {
	return len(*a) == cap(*a)
}

// 尾部追加
func (a *ListArray) Append(element ...interface{}) {
	*a = append(*a, element...)
}

// 任意元素插入
func (a *ListArray) Insert(i int, element ...interface{}) {
	slice := []interface{}(*a)
	if i > len(*a)-1 {
		slice[i] = element
		return
	}

	if i < 0 {
		i = 0
	}
	var b []interface{}
	b = append(slice[:i], element...)
	b = append(b, slice[i:]...)
	c := ListArray(b)
	*a = c
}

// 删除任意元素
func (a *ListArray) Remove(i int) {
	slice := []interface{}(*a)
	b := append(slice[:i], slice[i+1:]...)
	c := ListArray(b)
	*a = c
}

// 按值查找
func (a *ListArray) Contain(element interface{}) int {
	for k, v := range *a {
		if v == element {
			return k
		}
	}
	return -1
}

go标准包 container/list 已提供双向链表实现： 常用操作: 1.Init() 创建链表并初始化 2.Len() 保存于链表结构字段中 3.Front() 返回链表第一个元素 4.Back() 返回链表最后一个元素 5.Remove(element) 移除链表元素 6.PushFront(v) 插入元素到表头 7.PushBack(v) 插入元素到表尾 8.InsertBefore(v,mark) 在某个元素前插入 9.InsertAfter(v,mark) 在某个元素后插入 10.MoveToFront(e) 移动元素到表头 11.MoveToBack(e) 移动元素到表尾 12.MoveBefore(e,mark) 移动元素到某个元素之前 13.MoveAfter(e,mark) 移动元素到某个元素之后 14.PushBackList() 从另一个链表拷贝元素追加到当前链尾 15.PushFrontList() 从另一个链表拷贝元素追加到当前链头

以下参照标准包修改一个单向链表的代码：

// 实现单向链表
type Element struct {
	next  *Element
	list  *List
	Value interface{}
}

// 链表元素迭代方法
func (e *Element) Next() *Element {
	if p := e.next; e.list != nil && p != &e.list.root {
		return p
	}
	return nil
}

// 链表
type List struct {
	root Element // 哨兵根节点
	len  int     // 维护一个长度属性
}

// 初始化
func (l *List) Init() *List {
	l.root.next = &l.root
	l.len = 0
	return l
}

// 链表工厂方法
func New() *List { return new(List).Init() }

// 长度保存于链表结构字段中
func (l *List) Len() int { return l.len }

// 返回链表的第一个元素
func (l *List) Front() *Element {
	return l.root.next
}

// 返回链表最后一个元素
func (l *List) Back() *Element {
	e := l.root.next // root为哨兵头节点，第一个节点为root.next
	if e == &l.root {
		// 没有元素时还是返回root
		return e
	}
	for {
		if e.next == nil {
			return e
		}
		e = e.Next()
	}
}

// 内部方法：插入元素
func (l *List) insert(e, at *Element) *Element {
	n := at.next
	at.next = e
	e.next = n
	e.list = l
	l.len++
	return e
}

// 内部方法：插入值
func (l *List) insertValue(v interface{}, at *Element) *Element {
	return l.insert(&Element{Value: v}, at)
}

// 内部方法：删除元素
func (l *List) remove(e *Element) *Element {
	var prev *Element
	ele := l.root.next // 第一个元素
	for {
		if ele.next == nil { // 尾元素
			return nil
		}
		if ele == e { // 找到该删除的元素
			prev.next = ele.next // 前一个元素接链
			l.len--
			return ele
		}
		prev = ele       // 暂存当前迭代元素
		ele = ele.Next() // 迭代下一个
	}

	return nil
}

// 内部方法，移动元素
func (l *List) move(e, at *Element) *Element {
	if e == at {
		return e
	}
	n := at.next
	at.next = e
	e.next = n

	return e
}

// 删除链表元素
func (l *List) Remove(e *Element) *Element {
	return l.remove(e)
}

// 插入元素到表头
func (l *List) PushFront(v interface{}) {
	l.insertValue(v, &l.root)
}

// 插入元素到表尾
func (l *List) PushBack(v interface{}) {
	var tail *Element
	for {
		e := l.root.Next()
		if e.next == nil {
			tail = e
			break
		}
	}
	l.insertValue(v, tail)
}

// 在某个元素前插入
func (l *List) InsertBefore(v interface{}, mark *Element) *Element {
	return l.insertValue(v, mark)
}

// 在某个元素后插入
func (l *List) InsertAfter(v interface{}, mark *Element) *Element {
	return l.insertValue(v, mark)
}

// 移动元素到表头
func (l *List) MoveToFront(e *Element) {
	l.move(e,&l.root)
}

// 移动元素到表尾
func (l *List) MoveToBack(e *Element) {
	var tail *Element
	for {
		e := l.root.Next()
		if e.next == nil {
			tail = e
			break
		}
	}
	l.move(e,tail)
}

// 移动元素到某个元素之前
func (l *List) MoveBefore(e, mark *Element) {
	l.move(e,mark)
}

// 移动元素到某个元素之后
func (l *List) MoveAfter(e, mark *Element) {
	l.move(e,mark)
}

// 从另一个链表拷贝元素追加到当前链尾
func (l *List) PushList(other *List) {
	l.lazyInit()
	for i, e := other.Len(), other.Front(); i > 0; i, e = i-1, e.Next() {
		l.PushBack(e.Value)
	}
}


// lazyInit lazily initializes a zero List value.
func (l *List) lazyInit() {
	if l.root.next == nil {
		l.Init()
	}
}