链表也是面试的常客，听说有面试官让面试者手撸一个链表的，更有甚者直接让面试者手撸红黑树的。

我只能说，如果你遇到这样的面试官，你就可以起身离开了，醒醒吧，这地方很可能不适合你。

一、链表的概念

为了方便同学们理解，我画了一个图：

上条是单向链表，下面是双向链表。

两者区别是啥呢？

从查找速度来讲，双向的会更快些，但是缺点也是占用空间大些。

所以如果项目里面对空间要求高的话，就用前者，回头用时间换空间。

按照逻辑结构来说，他们应该是一个挨着一个的，但是在实际存储当中并没有像这样连续，可能会散落在各个内存区里面。

关于链表的作用就不在这里赘述了，感兴趣的面向搜索引擎提问吧。

二、Go 里面的链表操作

go 的标准库里面其实为我们提供了一个链表功能，在我们的 container/list 包里面。

所以很多时候我们不需要再手动实现，可以这样使用：

data := list.New()
// 写入值
data.PushBack(2)
data.PushBack(3)
data.PushBack(4)
// 循环
for e := data.Front(); e != nil; e = e.Next() {
 fmt.Printf("%v \n", e.Value)
}

他为我们提供了很多方法可以使用：

比如插入到最后面，还是哪个的后面，感兴趣的可以去详细看下。

上面的代码执行结果是：

$ go run n.go 
2
3
4

二、一些常用操作

1、移动交换

假如我们需要调换 2 和 3 的位置：

data := list.New()
//从尾部添加
e2 := data.PushBack(2)
e3 := data.PushBack(3)
data.PushBack(4)
data.MoveAfter(e2, e3)
//循环
for e := data.Front(); e != nil; e = e.Next() {
 fmt.Printf("%v \n", e.Value)
}

我们可以使用他的 MoveAfter 方法进行移动。

执行结果：

$ go run n.go 
3 
2 
4

2、插入

加入我们需要在 2 后面插入一个 2.5：

data := list.New()
//从尾部添加
e2 := data.PushBack(2)
data.PushBack(3)
data.PushBack(4)
data.InsertAfter(2.5, e2)
//循环
for e := data.Front(); e != nil; e = e.Next() {
 fmt.Printf("%v \n", e.Value)
}

我们可以使用 InsertAfter 方法进行操作。

执行结果为：

$ go run n.go 
2 
2.5 
3 
4

更多的操作方法就不一一举例了哈。