02-链表、栈、队列、递归、哈希表、顺序表.md

[TOC]
# 1 链表、栈、队列、递归、哈希

## 1.1 链表

### 1.1.1 单向链表
> 单向链表的节点结构：

```Go
// Node 单项链表节点结构
type Node struct {
	V int
	Next *Node
}
```
### 1.1.2 双向链表

> 双向链表的节点结构：

```Go
// DoubleNode 双向链表节点结构
type DoubleNode struct {
	V int
	Pre *DoubleNode
	Next *DoubleNode
}
```

### 1.1.3 单双链表简单练习

1. 单链表和双链表如何反转

> 例如单链表：1 -> 2 -> 3 转换为 3 -> 2 -> 1;


```Go
// ReverseLinkedList 翻转单链表
func ReverseLinkedList(head *Node) *Node {
	var pre *Node
	var next *Node
	for head != nil {
		// 把当前节点的下一个节点保存到next
		next = head.Next
		// 当前节点的指向，改为指向前一个节点
		head.Next = pre
		// pre 节点按原链表方向向下移动
		pre = head
		// head 节点按原链表方向向下移动
		head = next
	}
	// 按照原链表方向移动，当前节点为nil退出循环的时候，那么pre节点就是原链表的最后一个节点，链表被成功翻转。
	// 当前头结点pre返回
	return pre
}
```

```Go
// ReverseDoubleLinkedList 翻转双向链表
func ReverseDoubleLinkedList(head *DoubleNode) *DoubleNode {
	var pre *DoubleNode
	var next *DoubleNode
	for head != nil {
		// 保留当前节点的next节点的地址
		next = head.Next
		// 当前节点的下一个节点指pre
		head.Next = pre
		// 当前节点的上一个节点指向原链表当前节点的next节点。
		head.Pre = next
		// pre 节点按原链表方向向下移动
		pre = head
		// head 节点按原链表方向向下移动
		head = next
	}
	return pre
}
```

2. 把给定的值都删除

> 比如给定一个链表头结点，删除该节点上值为3的节点，那么可能头结点就是3，存在删头部的情况，这里最终返回应该是删除所有值为3的节点之后的新的头部

```Go
// RemoveValue 删除链表中值等于target的节点
func RemoveValue(head *Node, target int) *Node {
	// 处理链表头结点的值即等于target的节点
	for head != nil {
		if head.V != target {
			break
		}
		head = head.Next
	}

	// 1、链表中的节点值全部都等于target
	// 2、原始链表为nil
	if head == nil {
		return head
	}

	// head来到第一个不需要删除的位置
	pre := head
	cur := head
	for cur != nil {
		// 当前节点cur往下，有多少v等于target的节点，就删除多少节点
		if cur.V == target {
			pre.Next = cur.Next
		} else {
			pre = cur
		}
		// 当前节点向下滑动
		cur = cur.Next
	}
	return head
}
```

## 1.2 栈、队列
1. 逻辑概念

> 栈：数据先进后出，犹如弹夹

> 队列: 数据先进先出，排队

```Go
// 利用双向链表实现双端队列
package main

// DoubleEndsNode 双端队列节点
type DoubleEndsNode struct {
	val  int
	pre  *DoubleEndsNode
	next *DoubleEndsNode
}

// DoubleEndsList 双端队列接口
type DoubleEndsList interface {
	// AddFromHead 从头部添加节点
	AddFromHead(v int)
	// AddFromBottom 从尾部添加节点
	AddFromBottom(v int)
	// PopFromHead 从头部弹出节点
	PopFromHead() (int, bool)
	// PopFromBottom 从尾部弹出节点
	PopFromBottom() (int, bool)
	// IsEmpty 双端队列是否为空
	IsEmpty() bool
}

type DoubleEndsQueue struct {
	head *DoubleEndsNode
	tail *DoubleEndsNode
}

func (q *DoubleEndsQueue) AddFromHead(v int) {
	cur := &DoubleEndsNode{
		val: v,
	}
	if q.head == nil {
		q.head = cur
		q.tail = cur
	} else {
		cur.next = q.head
		q.head.pre = cur
		q.head = cur
	}
}

func (q *DoubleEndsQueue) AddFromBottom(v int) {
	cur := &DoubleEndsNode{
		val: v,
	}
	if q.head == nil {
		q.head = cur
		q.tail = cur
	} else {
		q.tail.next = cur
		cur.pre = q.tail
		q.tail = cur
	}
}

func (q *DoubleEndsQueue) PopFromHead() (int, bool) {
	if q.head == nil {
		return 0, false
	}
	v := q.head.val
	if q.head == q.tail {
		q.head = nil
		q.tail = nil
		return v, true
	} else {
		h := q.head
		q.head = q.head.next
		q.head.pre = nil
		h.next = nil
		return v, true
	}
}

func (q *DoubleEndsQueue) PopFromBottom() (int, bool) {
	if q.head == nil {
		return 0, false
	}
	v := q.tail.val
	if q.head == q.tail {
		q.head = nil
		q.tail = nil
		return v, true
	} else {
		t := q.tail
		q.tail = q.tail.pre
		q.tail.next = nil
		t.pre = nil
		return v, true
	}
}

func (q *DoubleEndsQueue) IsEmpty() bool {
	return q.head == nil
}
```

2. 栈、队列的底层实现方式

> 利用双向链表（双端队列）封装栈和队列

```Go
// Stack 利用双端队列实现栈
type Stack struct {
	qu *DoubleEndsQueue
}

func (s *Stack) push(v int) {
	s.qu.AddFromHead(v)
}

func (s *Stack) pop() (int, bool) {
	return s.qu.PopFromHead()
}

func (s *Stack) peek() (int, bool){
	if s.qu.IsEmpty() {
		return 0, false
	}
	return s.qu.head.val, true
}
```

```Go
// Queue 利用双端队列实现队列
type Queue struct {
	qu *DoubleEndsQueue
}

func (q *Queue) push(v int) {
	q.qu.AddFromHead(v)
}

func (q *Queue) poll() (int, bool) {
	return q.qu.PopFromBottom()
}

func (q *Queue)IsEmpty() bool {
	return q.qu.IsEmpty()
}
```

> 数组实现栈和队列, 对于栈特别简单，略过，对于队列，如下


```Go
package main

import "fmt"

type Que struct {
	// 队列的底层结构
	arr []int
}

func (q *Que) push (v int) {
	q.arr = append(q.arr, v)
}

func (q *Que) poll () (int, bool){
	if len(q.arr) == 0 {
		return 0, false
	}
	v := q.arr[0]
	q.arr = q.arr[1:]
	return v, true
}

func main () {
	q := Que{}
	q.push(1)
	q.push(9)
	q.push(3)
	if poll, ok := q.poll(); ok {
		fmt.Println(poll)
	}
	if poll, ok := q.poll(); ok {
		fmt.Println(poll)
	}
	if poll, ok := q.poll(); ok {
		fmt.Println(poll)
	}
	if poll, ok := q.poll(); ok {
		fmt.Println(poll)
	}
}
```

## 1.3 栈、队列常见面试题

一、实现一个特殊的栈，在基本功能的基础上，再实现返回栈中最小元素的功能

1、pop、push、getMin操作的时间复杂度都是O(1)

2、设计的栈类型可以使用现成的栈结构

> 思路：准备两个栈，一个data栈，一个min栈。数据压data栈，min栈对比min栈顶元素，谁小加谁。这样的话data栈和min栈是同步上升的，元素个数一样多，且min栈的栈顶，是data栈所有元素中最小的那个。数据弹出data栈，我们同步弹出min栈，保证个数相等，且min栈弹出的就是最小值

```Go
type MinStack struct {
	data *Stack
	min  *Stack
}

func (s *MinStack) push(v int) {
	// min栈只保存最小的v，当然这里也可以设计成min栈和data栈同步上升的策略
	if s.min.IsEmpty() {
		s.min.push(v)
	} else if c, ok := s.min.peek(); ok {
		if v <= c { // 小于等于都入栈，弹出的时候等于也同步弹出min栈
			s.min.push(v)
		} else {
			s.min.push(c)
		}
	}
	// 数据栈稳步上升
	s.data.push(v)
}

func (s *MinStack) pop() (int, bool) {
	if s.data.IsEmpty() {
		return 0, false
	}
	v, _ := s.data.pop()
	if m, ok := s.min.peek(); ok {
		if m == v {
			s.min.pop()
		}
	}
	return v, true
}

func (s *MinStack) getMin() (int, bool){
	if s.min.IsEmpty() {
		return 0, false
	}
	return s.min.peek()
}
```

## 1.4 递归

1、从思想上理解递归

2、从实现角度出发理解递归

例子：

求数组arr[L...R]中的最大值，怎么用递归方法实现

1、 将[L...R]范围分成左右两半。左[L...Mid],右[Mid+1...R]
2、 左部分求最大值，右部分求最大值
3、[L...R]范围上的最大值，就是max{左部分最大值,右部分最大值}

> 2步骤是个递归过程，当范围上只有一个数，就可以不用再递归了

```Go
package main

import "fmt"

func getMax(arr []int) (int, error) {
	if len(arr) == 0 {
		return 0, fmt.Errorf("arr len is zero")
	}
	return process(arr, 0, len(arr)-1), nil
}

func process(arr []int, l, r int) int {
	if l == r {
		return arr[l]
	}
	mid := l + (r-l)/2
	// 左范围最大值
	lm := process(arr, l, mid)
	// 右范围最大值
	rm := process(arr, mid+1, r)
	if lm > rm {
		return lm
	} else {
		return rm
	}
}

func main() {
	arr := []int{1, 4, 2, 6, 992, 4, 2234, 83}
	m, err := getMax(arr)
	if err != nil {
		panic(err)
	}
	fmt.Println(m)
}
```

> 递归在系统中是怎么实现的？递归实际上利用的是系统栈来实现的。保存当前调用现场，去执行子问题，子问题的返回作为现场的需要的参数填充，最终构建还原栈顶的现场，返回。任何递归都可以改为非递归实现，需要我们自己压栈用迭代等实现

### 1.4.1 递归行为的时间复杂度

> 对于满足


```math
T(N) = aT(N/b) + O(N^d)
```
其中： a,b,d为常数

> 公式表示，子问题的规模是一致的,该子问题调用了a次，N/b代表子问题的规模，O(N^d)为除去递归调用剩余的时间复杂度。

> 比如上述问题的递归，[L...R]上有N个数，第一个子问题的规模是N/2，第二个子问题的规模也是N/2。子问题调用了2次。额为复杂度为O(1)，那么公式为：


```math
T(N) = 2T(N/2) + O(N^0)
```

结论：如果我们的递归满足这种公式，那么该递归的时间复杂度(Master公式)为

```math
logb^a > d   =>  O(N ^ (logb^a))

logb^a < d   =>  O(N^d)

logb^a == d   =>  O(N^d * logN)

```

那么上述问题的a=2, b=2,d=0,满足第一条，递归时间复杂度为：O(N)

## 1.5 哈希表HashMap、HashSet

> Hash表的增删改查，在使用的时候，一律认为时间复杂度是O(1)的

> Golang中hashMap的结构为map，hashSet可以由map结构进行简单改造即可实现

## 1.6 顺序表 TreeMap、TreeSet

> 顺序表比哈希表功能多，但是顺序表的很多操作时间复杂度是O(logN)

> 有序表的底层可以有很多结构实现，比如AVL树，SB树，红黑树，跳表。其中AVL,SB，红黑都是具备各自平衡性的搜索二叉树

> 由于平衡二叉树每时每刻都会维持自身的平衡，所以操作为O(logN)。后面篇幅会单独介绍平衡二叉树。

> 由于满足去重排序功能来维持底层树的平衡，所以如果是基础类型key直接按值来做比较，但是如果我们的key是自己定义的结构体类型，那么我们要自己制定比较规则，Go中为实现sort的接口，用来让底层的树保持比较后的平衡

```Go
// Go中HashSet的简单实现
package set

type Set interface {
	Add(elements ...interface{})
	Remove(elements ...interface{})
	Contains(elements ...interface{}) bool
}

var itemExists = struct{}{}

type HashSet struct {
	items map[interface{}]struct{}
}

func New(values ...interface{}) *HashSet {
	set := &HashSet{items: make(map[interface{}]struct{})}
	if len(values) > 0 {
		set.Add(values...)
	}
	return set
}

func (set *HashSet) Add(items ...interface{}) {
	for _, item := range items {
		set.items[item] = itemExists
	}
}

func (set *HashSet) Remove(items ...interface{}) {
	for _, item := range items {
		delete(set.items, item)
	}
}

func (set *HashSet) Contains(items ...interface{}) bool {
	for _, item := range items {
		if _, contains := set.items[item]; !contains {
			return false
		}
	}
	return true
}
```

```Go
// Go中基于红黑树TreeSet的简单使用
package main

import (
	"fmt"
	"github.com/emirpasic/gods/sets/treeset"
)

// treeSet => 去重排序
func main()  {
	set := treeset.NewWithIntComparator()
	set.Add()
	set.Add(1)
	set.Add(2)
	set.Add(2, 3)
	set.Add()
	set.Add(6)
	set.Add(4)
	if actualValue := set.Empty(); actualValue != false {
		fmt.Printf("Got %v expected %v", actualValue, false)
	}
	if actualValue := set.Size(); actualValue != 3 {
		fmt.Printf("Got %v expected %v", actualValue, 3)
	}
	if actualValue, expectedValue := fmt.Sprintf("%d%d%d", set.Values()...), "12346"; actualValue != expectedValue {
		fmt.Printf("Got %v expected %v", actualValue, expectedValue)
	}

	fmt.Println(set.Values()...)
}
```