【梦幻联动】数据结构第一讲——单双链表

如何理解链表rice已经讲过了，我这里再以抽象的方式解释一下

单链表

定义

在计算机科学中，链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向上一个/或下一个节点的位置的链接（"links"）。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的访问往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。

链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的访问和操作。程序语言或面向对象语言，如C/C++和Java依靠易变工具来生成链表。

摘自中文版Wikipedia

 

上面那段话不看也可以

 

“通俗“地解释一下

我们想象一种物体，它有两个属性。第一个属性是一个数据（数据的形式、内容不限），我们将这个属性称为这个物体所含的信息；第二个属性是一个指向另一个这种物体的指针，我们将这个属性称为这个物体指向下个物体的指针。

这种“物体”被称为链表的Node（结点）。

如上图所示，第一个结点所含的信息是12这个数，指针指向了信息值为99的结点。注意到没有物体指向12结点，我们称之为链表的“头”结点。又注意到37结点指向的结点不存在，我们称之为这个结点为链表的“尾”结点。

来看几个具体问题，以下问题中，我们将插入的结点的值设为100

1. 向头部插入一个新的头结点

我们将100结点的指针指向12结点，将链表头设置为100结点。

1. 向尾部插入一个新的尾结点

将37结点的指针指向100结点，将100结点设置为链表尾。

1. 向12和99中间插入一个结点

将12结点的指针指向100结点，将100结点的指针指向99结点。

1. 删除99结点

将12结点指针指向37结点就可以了。

如果这里语言没有自动GC功能的话可能还得Free一下99结点的内存（如C和C++）。

代码

老样子，这个专栏虽然名为”算法专栏“，但是每次都被我用来讲代码，这次也不例外。

我们这次使用的语言是Go语言，因为Go语言的指针可以更加方便的实现和讲解链表。

同往常不一样，我们这次先来写一段“伪代码”，帮助理解，伪代码不区分语言。

结构 Node {
    属性1：数据
    单链表属性2：下一项
}
​
结构 LinkedList {
    属性1：头结点
    属性2：尾结点
}

然后我们实现一下真实代码：（这里我们的数据是整数类型）

package main
type Node struct {
    Data int
    Next *Node
}
​
type LinkedList struct {
    Head *Node
    Tail *Node
}

单链表我们直接来实现主要的Append与InsertToFront方法

// ...
func (l *LinkedList) Append(data int) {
    node := &Node{Data: data}
    // 如果链表为空则将链表头尾均初始化为node
    if l.Head == nil {
        l.Head = node
        l.Tail = node
        return
    }
    l.Tail.Next = node // 将当前尾结点下一项指向node
    l.Tail = node // 将尾结点设置为node
}
​
func (l *LinkedList) InsertToFront(data int) {
    node := &Node{Data: data}
    if l.Head == nil { // 同上注释
        l.Head = node
        l.Tail = node
        return
    }
    node.Next = l.Head // 将当前头结点上一项指向node
    l.Head = node // 将头结点设为node
}

我们再来实现结构LinkedList的String方法使其继承Go内置的Stringer接口。（我估计大部分人实际上应该看不懂这句话...）

import (
    "strings"
    "strconv"
)
// ...
​
func (l LinkedList) ToSlice() []int {
    slice := []int{}
    // 遍历链表
    for currentNode := l.Head; currentNode != nil; currentNode = currentNode.Next {
        slice = append(slice, currentNode.Data) // 添加到slice中
    }
    return slice
}
​
func (l LinkedList) ToStringSlice() []string {
    slice := []string{}
    for _, i := range l.ToSlice() {
        slice = append(slice, strconv.Itoa(i)) // 转换成字符串
    }
    return slice
}
​
func (l LinkedList) String() string {
    return strings.Join(l.ToStringSlice(), " -> ")
}

这里之所以要实现ToSlice方法是为了之后使代码容易测试一些，为了进一步简化测试的工作量，我们实现FromSlice函数，使其能够自动从数组构造出一个链表来。

// ...
func FromSlice(slice []int) *LinkedList {
    ll := &LinkedList{}
    for _, i := range slice {
        ll.Append(i) // 调用前面写好的方法
    }
    return ll
}

我们来测试一下

import "fmt"
// ...
func main() {
    ll := FromSlice([]int{1, 2, 3})
    fmt.Println(ll)
}

输出：

1 -> 2 -> 3

成功！

代码地址在此，大家可以自己在线运行一下这段代码。

双链表

双链表，顾名思义就是双向链表。

这里就直接上伪代码了

结构 Node {
    属性1：数据
    属性2：上一项
    属性3：下一项
}
​
结构 DoubleLinkedList {
    属性1：头结点
    属性2：尾结点
}

注意到这里Node结点多了一个属性即指向上一项的指针。

双链表操作

如上图所示，还是那三个数。同样，我们插入的数据仍为100

1. 插入头结点

将100结点的下一项指向12结点，将12结点的上一项指向100结点，设置链接头为100结点。

1. 插入尾节点

将37结点下一项指向100结点，将100结点上一项指向100结点，设置链接尾为100结点

1. 插入12与99中间

将12的下一项指向100，将100上一项指向12；

将100的下一项指向99，将99上一项指向100；

1. 删除99结点

将12下一项指向37，将37上一项指向12。

如果是C和C++，Free一下99结点的内存。

代码

基本定义

type Node struct {
    Data int
    Prev *Node
    Next *Node
}
​
type DoubleLinkedList struct {
    Head *Node
    Tail *Node
}

实现Append及InsertToFront方法

func (dl *DoubleLinkedList) Append(data int) {
    node := &Node{Data: data}
    // 如果链表为空则将链表头尾均初始化为node
    if dl.Head == nil {
        dl.Head = node
        dl.Tail = node
        return
    }
    dl.Tail.Next = node // 将尾结点下一项指向node
    node.Prev = dl.Tail // 将node上一项指向当前尾结点
    dl.Tail = node // 设置尾结点
}
​
func (dl *DoubleLinkedList) InsertToFront(data int) {
    node := &Node{Data: data}
    // 同上
    if dl.Head == nil {
        dl.Head = node
        dl.Tail = node
        return
    }
    node.Next = dl.Head // 将头结点上一项指向node
    dl.Head.Prev = node // 将node下一项指向当前头结点
    dl.Head = node // 设置头结点
}

同样，我们来实现与数组的转换

​
func (dl DoubleLinkedList) String() string {
    return strings.Join(dl.ToStringSlice(), " <-> ")
}
​
func (dl DoubleLinkedList) ToStringSlice() []string {
    slice := []string{}
    for _, i := range dl.ToSlice() {
        slice = append(slice, strconv.Itoa(i)) // 转换为字符串
    }
    return slice
}
​
func (dl DoubleLinkedList) ToSlice() []int {
    slice := []int{}
    // 从头部向尾部遍历数组
    for currentNode := dl.Head; currentNode != nil; currentNode = currentNode.Next {
        slice = append(slice, currentNode.Data)
    }
    return slice
}
​
func (dl DoubleLinkedList) ToReverseSlice() []int {
    slice := []int{}
    // 因为这里每一项都有指向前一项的指针
    // 所以我们可以从尾部向前遍历至头部
    for currentNode := dl.Tail; currentNode != nil; currentNode = currentNode.Prev {
        slice = append(slice, currentNode.Data)
    }
    return slice
}

测试一下：

func main() {
    dl := FromSlice([]int{1, 2, 3})
    fmt.Println(dl)
    fmt.Println(dl.ToReverseSlice())
}

输出：

1 <-> 2 <-> 3
[3 2 1]

成功！

代码地址

 

注：本文图片皆截取自Wikipedia