一、简介

数据结构是用来组织数据的，如何将一个数据关联到另外一个数据呢？

链表可以将数据和数据之间关联起来，从一个数据指向另外一个数据。

定义：

链表由一个个数据节点（一个节点是一个结构体）组成，它是一个递归结构，要么它是空的，要么它存在一个指向另外一个数据节点的引用。

链表，可以说是最基础的数据结构。

二、最简单的链表

结构体 LinkNode （链表的一个节点）有两个字段，一个字段存放数据 Data，另一个字段是一个指针，指向下一个节点 NextNode 。这种从一个数据节点指向下一个数据节点的结构，都可以叫做链表。

package main

import (
	"fmt"
)

type LinkNode struct {   //链表的一个数据节点的结构体
	Data     int64
	NextNode *LinkNode
}

func main() {
	// 新的节点
	node := new(LinkNode)     //使用 new 实例化一个结构体，返回指向结构体的指针
	node.Data = 2
	
	// 新的节点
	node1 := new(LinkNode)
	node1.Data = 3
	node.NextNode = node1 // node1 链接到 node 节点上
	// 新的节点
	node2 := new(LinkNode)
	node2.Data = 4
	node1.NextNode = node2 // node2 链接到 node1 节点上
	// 按顺序打印数据
	nowNode := node
	for {
		if nowNode != nil {
			// 打印节点值
			fmt.Println(nowNode.Data)
			// 获取下一个节点
			nowNode = nowNode.NextNode
			continue
		}
		// 如果下一个节点为空，表示链表结束了
		break
	}
}

输出结果：

2
3
4

有些书籍，把链表做了很细的划分，比如单链表，双链表，循环单链表，循环双链表，其实没有必要强行分类，链表就是从一个数据指向另外一个数据，一种将数据和数据关联起来的结构而已。

好吧，我们还是要知道是什么：

单链表，就是链表是单向的，像我们上面这个结构一样，可以一直往下找到下一个数据节点，它只有一个方向，它不能往回找。
双链表，每个节点既可以找到它之前的节点，也可以找到之后的节点，是双向的。（有两个指针字段，一个指向上一个节点，一个指向下一个节点）
循环链表，就是它一直往下找数据节点，最后回到了自己那个节点，首尾相接，形成了一个回路。循环单链表和循环双链表的区别就是，一个只能一个方向走，一个两个方向都可以走。

三、循环链表

我们来实现一个循环链表 Ring（集链表大成者），参考 Golang 标准库 container/ring：：

// 循环链表
type Ring struct {
    next, prev *Ring       // 前驱和后驱节点
    Value      interface{} // 数据
}

该循环链表有一个三个字段，next 表示后驱节点，prev 表示前驱节点，Value 表示值。

接下来是该结构上的各操作：

1. 初始化循环链表

初始化一个空的循环链表：

package main

import (
	"fmt"
)

// 循环链表
type Ring struct {
	next, prev *Ring       // 前驱和后驱节点
	Value      interface{} // 数据
}

// 初始化空的循环链表，前驱和后驱都指向自己，因为是循环的
func (r *Ring) init() *Ring {
	r.next = r
	r.prev = r
	return r
}
func main() {
	r := new(Ring)
	fmt.Println(r.init())
}

输出结果：

&{0xc0000a43a0 0xc0000a43a0 <nil>}

因为绑定前驱和后驱节点为自己，没有循环，时间复杂度为：O(1)。

2. 创建一个指定大小 N 的循环链表，值全为空

package main

import (
	"fmt"
)

// 循环链表
type Ring struct {
	next, prev *Ring       // 前驱和后驱节点
	Value      interface{} // 数据，空接口类型的变量可以存储任意类型的变量
}

func New(n int) *Ring {
	if n <= 0 {
		return nil
	}
	r := new(Ring)  //新节点
	p := r

	for i := 1; i < n; i++ {  //创建n-1个新节点
		p.next = &Ring{prev: p}  //新节点
		p = p.next               //p 指向新节点
	}
	p.next = r    //首尾相接
	r.prev = p
	return r
}

func main() {
	fmt.Println(New(3))
}

会连续绑定前驱和后驱节点，时间复杂度为：O(n)。

3. 获取上一个或下一个节点

// 获取下一个节点
func (r *Ring) Next() *Ring {
    if r.next == nil {
        return r.init()
    }
    return r.next
}
// 获取上一个节点
func (r *Ring) Prev() *Ring {
    if r.next == nil {
        return r.init()
    }
    return r.prev
}

获取前驱或后驱节点，时间复杂度为：O(1)。

4. 获取第 n 个节点

因为链表是循环的，当 n 为负数，表示从表头往前遍历，否则往后面遍历：

func (r *Ring) Move(n int) *Ring {
    if r.next == nil {
        return r.init()
    }
    switch {
    case n < 0:
        for ; n < 0; n++ {
            r = r.prev
        }
    case n > 0:
        for ; n > 0; n-- {
            r = r.next
        }
    }
    return r
}

因为需要遍历 n 次，所以时间复杂度为：O(n)。

5. 获取链表长度

// 查看循环链表长度
func (r *Ring) Len() int {
    n := 0
    if r != nil {
        n = 1
        for p := r.Next(); p != r; p = p.next {
            n++
        }
    }
    return n
}

通过循环，当引用回到自己，那么计数完毕，时间复杂度：O(n)。

因为循环链表还不够强壮，不知道起始节点是哪个，计数链表长度还要遍历，所以用循环链表实现的双端队列就出现了，一般具体编程都使用更高层次的数据结构。

四、数组和链表

数组是编程语言作为一种 基本类型 提供出来的，相同数据类型的元素按一定顺序排列的集合。

它的作用只有一种：存放数据，让你很快能找到存的数据。如果你不去额外改进它，它就只是存放数据而已，它不会将一个数据节点和另外一个数据节点关联起来。比如建立一个大小为 5 的数组 array:

package main

import "fmt"

func main() {
	array := [5]int64{}
	fmt.Println(array)
	array[0] = 8
	array[1] = 9
	array[2] = 7
	fmt.Println(array)
	fmt.Println(array[2])
}

我们可以通过下标 0，1，2 来获取数组中的数据，下标 0，1，2 就表示数据的位置，我们也可以把指定位置的数据替换成另外一个数据。

数组这一数据类型，是被编程语言高度抽象封装的结构，下标会转换成 虚拟内存地址，然后操作系统会自动帮我们进行寻址，这个寻址过程是特别快的，所以往数组的某个下标取一个值和放一个值，时间复杂度都为 O(1)。

它是一种将 虚拟内存地址 和 数据元素 映射起来的内置语法结构，数据和数据之间是挨着，存放在一连续的内存区域，每一个固定大小（8字节）的内存片段都有一个虚拟的地址编号。当然这个虚拟内存不是真正的内存，每个程序启动都会有一个虚拟内存空间来映射真正的内存，这是计算机组成的内容，和数据结构也有点关系，我们会在另外的高级专题讲，这里就不展开了。

数组是数据结构 顺序表 的具体实现。

用数组也可以实现链表，比如定义一个数组 [5]Value，值类型为一个结构体 Value ，该结构体有两个字段：值和下一个节点的下标：

package main

import "fmt"

func ArrayLink() {
	type Value struct {
		Data      string
		NextIndex int64
	}
	var array [5]Value          // 五个节点的数组
	array[0] = Value{"I", 3}    // 下一个节点的下标为3
	array[1] = Value{"Army", 4} // 下一个节点的下标为4
	array[2] = Value{"You", 1}  // 下一个节点的下标为1
	array[3] = Value{"Love", 2} // 下一个节点的下标为2
	array[4] = Value{"!", -1}   // -1表示没有下一个节点
	node := array[0]
	for {
		fmt.Println(node.Data)
		if node.NextIndex == -1 {
			break
		}
		node = array[node.NextIndex]
	}
}
func main() {
	ArrayLink()
}