数据结构

链表

线性表

  • 有限的序列
  • 序列中的每个元素都有唯一的前驱和后继 除了开头和结尾两个节点

顺序表：分配一块连续的内存去存放这些元素 例如数组

链表：内存是不连续的 元素各自分配一块内存 内存和内存之间用指针进行相连

具体实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
package main
// 定义类型
type ListNode {
    data int
    next *ListNode
}

// 初始化
func initList () *ListNode {
    list := &ListNode{
        data: 0,
        next: nil,
    }
    return list
}

// 头插法
func headInsert (list *ListNode, data int) {
    node := &ListNode{
        data:data,
        next:nil
    }
    node.next = list.next
    list.next = node
    list.data++
}

// 尾插法
func tailInsert (list *ListNode,data int) {
    node := &ListNode {
        data:data,
        next:nil
    }
    tail = list.next
    for tail.next != nil {
        tail = tail.next
    }
    tail.next = node
    list.data++
}

// 删除
func delete (list *ListNode,data int) {
    pre := list.next
    for pre.next != nil {
        if pre.next.data == data {
            // 删除当前节点
            pre.next = pre.next.next
            list.data--
        }
        pre = pre.next
    }
}

// print
func printList (list *ListNode) {
    list = list.next
    for list != nil {
        fmt.Printfln(list.data)
        list = list.next
    }
}

func main() {
	list := initList()
	headInsert(list, 1)
	headInsert(list, 2)
	headInsert(list, 3)
	tailInsert(list, 4)
	tailInsert(list, 5)
	tailInsert(list, 6)
	printList(list)
	delete(list, 3)
	delete(list, 4)
	delete(list, 6)
	printList(list)
}

循环链表

具体实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
package main

import "fmt"

type ListNode struct {
	data int
	next *ListNode
}

// 初始化
func initList() *ListNode {
	list := &ListNode{
		data: 0,
		next: nil,
	}
	// loop
	list.next = list
	return list
}

// 头插法
func headInser(list *ListNode, data int) {
	node := &ListNode{
		data: data,
		next: nil,
	}
	node.next = list.next
	list.next = node
	list.data++
}

// 尾插法
func tailInser(list *ListNode, data int) {
	node := &ListNode{
		data: data,
		next: nil,
	}
	tail := list.next
	// 找到尾部
	for tail.next != list {
		tail = tail.next
	}
	tail.next = node
	node.next = list
	list.data++
}

// 删除
func delete(list *ListNode, data int) {
	// 前指针
	pre := list
	for pre.next != list {
		if pre.next.data == data {
			pre.next = pre.next.next
			list.data--
			return
		}
		pre = pre.next
	}
}

func printList(list *ListNode) {
	head := list
	list = list.next
	for list != head {
		fmt.Print(list.data, "->")
		list = list.next
	}
	fmt.Println("Null")
}

func main() {
	list := initList()
	headInser(list, 1)
	headInser(list, 2)
	headInser(list, 3)
	headInser(list, 4)
	headInser(list, 5)
	tailInser(list, 6)
	tailInser(list, 7)
	tailInser(list, 8)
	tailInser(list, 9)
	tailInser(list, 10)
	printList(list)
	delete(list, 5)
	delete(list, 1)
	delete(list, 10)
	printList(list)
}

双向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
package main

type ListNode struct {
	data int
	pre  *ListNode
	next *ListNode
}

// 初始化
func initList() *ListNode {
	node := &ListNode{
		data: 0,
		pre:  nil,
		next: nil,
	}
	return node
}

// 头插法
func headInsert(list *ListNode, data int) {
	node := &ListNode{
		data: data,
		pre:  nil,
		next: nil,
	}
	if list.data == 0 {
		// 链表为空
		node.next = list.next
		node.pre = list
		list.next = node
		list.data++
	} else {
		// 链表不为空
		node.pre = list
		node.next = list.next
		list.next.pre = node
		list.next = node
		list.data++
	}

}

// 尾插法
func tailInsert(list *ListNode, data int) {

	node := &ListNode{
		data: data,
		pre:  nil,
		next: nil,
	}
	tail := list.next
	for tail.next != nil {
		tail = tail.next
	}
	tail.next = node
	node.pre = tail
	list.data++
}

// 删除
func delete(list *ListNode, data int) {
	current := list.next
	for current != nil {
		// 当前current
		if current.data == data {
			// 如果是最后一个节点
			if current.next == nil {
				current.pre.next = nil
			} else {
				current.pre.next = current.next
				current.next.pre = current.pre
			}
			list.data--
		}
		current = current.next
	}
}

func printList(list *ListNode) {
	list = list.next
	// 满足条件进入循环体
	for list != nil {
		print(list.data, "->")
		list = list.next
	}
	print("Null\n")
}

func main() {
	list := initList()
	headInsert(list, 1)
	headInsert(list, 2)
	headInsert(list, 3)
	headInsert(list, 4)
	tailInsert(list, 5)
	tailInsert(list, 6)
	tailInsert(list, 7)
	tailInsert(list, 8)
	printList(list)
	delete(list, 1)
	delete(list, 3)
	delete(list, 8)
	printList(list)
}

双向循环链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
package main

type ListNode struct {
	data int
	pre  *ListNode
	next *ListNode
}

// 初始化
func initList() *ListNode {
	node := &ListNode{
		data: 0,
		pre:  nil,
		next: nil,
	}
	node.next = node
	node.pre = node
	return node
}

// 头插法
func headInsert(list *ListNode, data int) {
	node := &ListNode{
		data: data,
		pre:  nil,
		next: nil,
	}
	if list.data == 0 {
		// 链表为空
		node.pre = list
		node.next = list.next
		list.next = node
		list.pre = node
	} else {
		node.next = list.next
		node.pre = list
		list.next.pre = node
		list.next = node
	}
	list.data++
}

// 尾插法
func tailInsert(list *ListNode, data int) {
	node := &ListNode{
		data: data,
		pre:  nil,
		next: nil,
	}
	current := list.next
	for current.next != list {
		current = current.next
	}
	current.next = node
	current.next.pre = node
	node.pre = current
	node.next = list
	list.data++
}

// 遍历
func printList(list *ListNode) {
	node := list.next
	// 满足条件进入循环体
	for node != list {
		print(node.data, "->")
		node = node.next
	}
	print("Null\n")
}

// 删除
func delete(list *ListNode, data int) {
	current := list.next
	for current != list {
		if current.data == data {
			current.pre.next = current.next
			current.next.pre = current.pre
			list.data--
			return
		}
		current = current.next
	}
}

func main() {
	list := initList()
	headInsert(list, 1)
	headInsert(list, 2)
	headInsert(list, 3)
	headInsert(list, 4)
	tailInsert(list, 5)
	tailInsert(list, 6)
	tailInsert(list, 7)
	tailInsert(list, 8)
	printList(list)
	delete(list, 3)
	delete(list, 4)
	delete(list, 8)
	printList(list)
}

栈

具体实现 (使用链表实现 push 即是头插法)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
package main

type Node struct {
	data int
	next *Node
}

// 使用链表实现
func initStack() *Node {
	S := &Node{
		data: 0,
		next: nil,
	}
	return S
}

func isEmpty(S *Node) bool {
	if S.data == 0 || S.next == nil {
		return true
	}
	return false
}

func push(S *Node, data int) {
	// 使用头插法完成
	node := &Node{
		data: data,
		next: nil,
	}
	node.next = S.next
	S.next = node
	S.data++
}

func pop(S *Node) int {
	if isEmpty(S) {
		return -1
	} else {
		data := S.next.data
		S.next = S.next.next
		S.data--
		return data
	}
}

func printStack(S *Node) {
	S = S.next
	for S != nil {
		print(S.data, "->")
		S = S.next
	}
	print("Null\n")
}

func main() {
	stack := initStack()
	push(stack, 1)
	push(stack, 2)
	push(stack, 3)
	push(stack, 4)
	printStack(stack)
	ele := pop(stack)
	print(ele, "\n")
	printStack(stack)
}

队列