链表详解教程

一、链表概述

链表是一种线性表，实际上是由节点（Node）组成的，一个链表拥有不定数量的节点。其数据在内存中存储是不连续的，它存储的数据分散在内存中，每个结点只能也只有它能知道下一个结点的存储位置。由N各节点（Node）组成链表，每一个Node记录本Node的数据及下一个Node。向外暴露的只有一个头节点（Head），我们对链表的所有操作，都是直接或者间接地通过其头节点来进行的。

二、为什么链表这么重要

1. 链表是一种真正意义上的动态数据结构
2. 链表是最基础最简单的动态数据结构，熟练的掌握链表可以在后续学习更加高级的数据结构打下基础
3. 学习链表可以更加深刻的理解指针的概念
4. 更加深入的理解递归
5. 链表可以辅助组成更加高级的数据结构，比如说图结构等

三、链表结构图示

优点： 真正的动态不需要处理固定容量的问题

缺点： 丧失的随机访问的能力

四、链表和数组对比

1. 数组最好适用于索引有语意的情况，最大的优点是支持快速查询
2. 链表不适合用于索引有语意的情况，最大的优点是动态

五、链表的简单实现

class LinkedList:
    """
    链表实现
    Created by wb-yxk397023 on 2018/6/19.
    """

    class Node:
        """
        声明内部类
        """

        def __init__(self, e=None, next_node=None):
            """
            构造器
            :param e: 要存储的元素
            :param next_node: 指向下一个元素位置的指针
            """
            # 要存储的元素
            self.e = e
            # 声明指针(指向下一个元素位置)
            self.next = next_node

        def __str__(self):
            """
            toString方法
            :return: 字符串表示
            """
            return str(self.e) if self.e is not None else "None"

六、在链表中添加元素

1. 链表结构图示

上边有说过：向外暴露的只有一个头节点（Head），我们对链表的所有操作，都是直接或者间接地通过其头节点来进行的；所以完整的数据结构图示应该是这样的：

2. 简单的代码实现

class LinkedList:
    """
    链表实现
    Created by wb-yxk397023 on 2018/6/19.
    """

    class Node:
        """
        声明内部类
        """

        def __init__(self, e=None, next_node=None):
            """
            构造器
            :param e: 要存储的元素
            :param next_node: 指向下一个元素位置的指针
            """
            # 要存储的元素
            self.e = e
            # 声明指针(指向下一个元素位置)
            self.next = next_node

        def __str__(self):
            """
            toString方法
            :return: 字符串表示
            """
            return str(self.e) if self.e is not None else "None"

    def __init__(self):
        """
        构造函数
        """
        # 默认初始值为None
        self.head = None
        # 默认元素个数为0
        self.size = 0

    def get_size(self):
        """
        获取链表中元素的个数
        :return: 元素个数
        """
        return self.size

    def is_empty(self):
        """
        判断链表是否为空
        :return: 是否为空
        """
        return self.size == 0

3. 向链表中添加元素

向链表中添加元素，当我们操作向数组中添加元素的时候我们实际操作的是向数组尾部添加元素，因为向数组尾部添加元素是最方便的，因为在数组中我们有维护一个size，这个size属性追踪的是数组的尾部，所以说我们在为数组添加元素的时候向数组尾部添加是最方便的；而对于链表则是完全相反的，链表添加元素的时候向头部添加是最方便的，因为在链表中我们有维护一个head的属性，这个属性表示链表的头部，所以在向链表中添加元素是与数组恰恰相反的。

4. 在链表头添加元素图示

链表添加元素的关键在于怎么把一个数据添加到现有的结构中同时又不会破坏现有的结构：

5. 代码实现

def add_first(self, e):
    """
    在链表头添加新的元素e
    :param e: 要添加的元素
    """
    # 声明一个新的node作用域
    node = self.Node(e)
    # 改变node中next的指向，让其指向head
    node.next = self.head
    # 让head指向node
    self.head = node

    # 可以简写为：self.head = self.Node(e, self.head)
    # 维护size
    self.size += 1

6. 在链表中间添加新的元素图示

在链表"索引"为2的位置添加元素，链表没有索引在这里只是借助索引的概念来方便理解：

注意： 这个操作的关键点在于需要找到要添加的节点的前一个节点；另外指向关系的顺序是固定的，加入顺序发生了变化的话就会变成下边这样：

所以说在操作链表的时候顺序非常重要，如果颠倒顺序的话结果有可能就是错误的。

7. 代码实现

def add(self, e, index):
    """
    在链表的index(0-based)位置添加新的元素e(此功能不常用)
    :param e: 要添加的元素
    :param index: 索引位置
    """
    # 判断index是否合法
    if index < 0 or index > self.size:
        raise ValueError("Add failed. Illegal index.")

    # 判断是否是在链表头进行添加操作
    if index == 0:
        self.add_first(e)
    else:  # 如果不是在链表头进行添加操作就执行这个逻辑
        # 声明prev属性，用来标示需要添加的节点的前一个节点
        prev = self.head
        # 通过遍历找到要添加节点的前一个节点
        for i in range(index - 1):
            prev = prev.next

        # 创建新的node节点
        node = self.Node(e)
        # 改变指向，将新的元素指向prev的下一个元素
        node.next = prev.next
        # 改变指向，将prev.next的指针指向node
        prev.next = node

        # 可以简写为 prev.next = self.Node(e, prev.next)

        # 维护size属性
        self.size += 1

8. 向链表的尾部添加元素代码实现

def add_last(self, e):
    """
    在链表的尾部添加元素
    :param e: 要添加的元素
    """
    self.add(e, self.size)

七、使用链表的虚拟头节点

1. 为链表设置虚拟头节点

背景： 在上边第七步中由于我们需要对是否在链表头部增加元素进行特殊的处理，所以接下来我们需要引入一个新的概念——链表中的虚拟头节点。

解决思路： 为链遍头增加一个虚拟节点，这个节点不存储真实数据，如图所示：

代码演示：

class Node:

    def __init__(self, e=None, next_node=None):
        """
        构造器
        :param e: 要存储的元素
        :param next_node: 指向下一个元素位置的指针
        """
        # 要存储的元素
        self.e = e
        # 声明指针(指向下一个元素位置)
        self.next = next_node

    def __str__(self):
        """
        toString方法
        :return: 字符串表示
        """
        return str(self.e) if self.e is not None else "None"

# 链表头元素
dummy_head = None
# 链表元素个数
size = 0

def __init__(self):
    """
    构造函数
    """
    # 默认初始值为None
    self.dummy_head = self.Node()
    # 默认元素个数为0
    self.size = 0

def get_size(self):
    """
    获取链表中元素的个数
    :return: 元素个数
    """
    return self.size

def is_empty(self):
    """
    判断链表是否为空
    :return: 是否为空
    """
    return self.size == 0

def add_first(self, e):
    """
    在链表头添加新的元素e
    :param e: 要添加的元素
    """
    self.add(e, 0)

def add(self, e, index):
    """
    在链表的index(0-based)位置添加新的元素e(此功能不常用)
    :param e: 要添加的元素
    :param index: 索引位置
    """
    # 判断index是否合法
    if index < 0 or index > self.size:
        raise ValueError("Add failed. Illegal index.")

    prev = self.dummy_head
    # 通过遍历找到要添加节点的前一个节点
    for i in range(index):
        prev = prev.next

    # 创建新的node节点
    # node = self.Node(e)
    # 改变指向，将新的元素指向prev的下一个元素
    # node.next = prev.next
    # 改变指向，将prev.next的指针指向node
    # prev.next = node

    prev.next = self.Node(e, prev.next)

    # 维护size属性
    self.size += 1

def add_last(self, e):
    """
    在链表的尾部添加元素
    :param e: 要添加的元素
    """
    self.add(e, self.size)

八、链表的遍历、查询和修改

1. 链表的遍历

def get(self, index):
    """
    获得链表的第index(0-based)个位置的元素,在链表中不是一个常用的操作.
    :param index: 索引位置
    :return: 元素值
    """
    if index < 0 or index >= self.size:
        raise ValueError("Get failed. Illegal index.")

    cur = self.dummy_head.next
    for i in range(index):
        cur = cur.next

    return cur.e

def get_first(self):
    """
    获取链表中的第一个元素
    :return: 第一个元素
    """
    return self.get(0)

def get_last(self):
    """
    获取链表中的最后一个元素
    :return: 最后一个元素
    """
    return self.get(self.size - 1)

2. 链表的更新操作

def set(self, index, e):
    """
    修改链表的第index(0-based)个位置的元素为e,在链表中不是一个常用的操作.
    :param index: 索引位置
    :param e: 新元素
    """
    if index < 0 or index >= self.size:
        raise ValueError("Set failed. Illegal index.")

    cur = self.dummy_head.next
    for i in range(index):
        cur = cur.next

    cur.e = e

3. 链表查询包含元素

def contains(self, e):
    """
    查询链表中是否存在元素e
    :param e: 要查询的元素
    :return: 是否存在
    """
    cur = self.dummy_head.next

    while cur is not None:
        if cur.e == e:
            return True
        cur = cur.next

    return False

4. 重写str

def __str__(self):
    """
    toString方法
    :return: 字符串表示
    """
    res = []
    cur = self.dummy_head.next

    while cur is not None:
        res.append(str(cur.e))
        cur = cur.next

    return "->".join(res) + "->None"

5. 测试

if __name__ == "__main__":
    linked_list = LinkedList()

    for i in range(5):
        linked_list.add_first(i)
        print(linked_list)

    linked_list.add(666, 2)
    print(linked_list)

九、从链表中删除元素

1. 删除元素图示

2. 代码实现

def remove(self, index):
    """
    从链表中删除index(0-based)位置的元素, 返回删除的元素(在链表中不是一个常用的操作)
    :param index: 索引位置
    :return: 被删除的元素
    """
    if index < 0 or index >= self.size:
        raise ValueError("Remove failed. Index is illegal.")

    prev = self.dummy_head
    for i in range(index):
        prev = prev.next

    ret_node = prev.next
    prev.next = ret_node.next
    ret_node.next = None
    self.size -= 1

    return ret_node.e

3. 完善其他删除逻辑

def remove_first(self):
    """
    从链表中删除第一个元素
    :return: 被删除的元素
    """
    return self.remove(0)

def remove_last(self):
    """
    从链表中删除最后一个元素
    :return: 被删除的元素
    """
    return self.remove(self.size - 1)

4. 测试代码

if __name__ == "__main__":
    linked_list = LinkedList()

    for i in range(5):
        linked_list.add_first(i)
        print(linked_list)

    linked_list.add(666, 2)
    print(linked_list)

    linked_list.remove(2)
    print(linked_list)
    linked_list.remove_first()
    print(linked_list)
    linked_list.remove_last()
    print(linked_list)

十、使用链表实现栈

1. 代码实现以及自测

from linked_list import LinkedList

class LinkedListStack:
    """
    使用链表实现栈
    Created by wb-yxk397023 on 2018/6/22.
    """

    def __init__(self):
        self.list = LinkedList()

    def get_size(self):
        """获取栈的大小"""
        return self.list.get_size()

    def is_empty(self):
        """判断栈是否为空"""
        return self.list.is_empty()

    def push(self, e):
        """入栈操作"""
        self.list.add_first(e)

    def pop(self):
        """出栈操作"""
        return self.list.remove_first()

    def peek(self):
        """查看栈顶元素"""
        return self.list.get_first()

    def __str__(self):
        """toString方法"""
        return "Stack: top " + str(self.list)

# 链表栈自测
if __name__ == "__main__":
    stack = LinkedListStack()

    for i in range(5):
        stack.push(i)
        print(stack)

    stack.pop()
    print(stack)() {
        return list.removeFrist();
    }

    @Override
    public E peek() {
        return list.getFirst();
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Stack: top ");
        res.append(list);
        return res.toString();
    }

    /**
     * 链表栈自测
     * @param args
     */
    public static void main(String[] args) {

        LinkedListStack<Integer> stack = new LinkedListStack<>();

        for(int i = 0 ; i < 5 ; i ++){
            stack.push(i);
            System.out.println(stack);
        }

        stack.pop();
        System.out.println(stack);
    }
}

十一、使用链表实现队列

1. 链表实现队列图示

参考数组实现队列的原理，链表实现队列也需要对现有的链表进行改进，如下所示：

由于有head元素的存在帮助我们标记链表头的位置，可以让我们对链表头操作变的非常方便，但是队列是一个有首有尾的结构，所以我们也需要对链表的尾部进行操作，所以需要对现有的链表进行改造，如下所示：

由于在链表中删除节点需要先找到待删除节点的前一个节点，所以对于尾部节点tail来说删除元素并没有head头部节点操作起来方便，无法使用O(1)的复杂度来删除tail位置的节点，但是操作添加节点是可以使用O(1)复杂度实现的，所以我们需要将head作为队首，tail作为队尾！

由于队列不会对中间节点直接进行操作，所以链表实现的队列就没有添加虚拟头节点的必要了；但是需要注意链表为空的情况，如图所示：

2. 代码实现以及测试

class LinkedListQueue:
    """
    使用链表实现队列
    Created by wb-yxk397023 on 2018/6/23.
    """

    class Node:
        def __init__(self, e=None, next_node=None):
            self.e = e
            self.next = next_node

        def __str__(self):
            return str(self.e) if self.e is not None else "None"

    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def get_size(self):
        """获取队列大小"""
        return self.size

    def is_empty(self):
        """判断队列是否为空"""
        return self.size == 0

    def enqueue(self, e):
        """入队操作"""
        if self.tail is None:
            self.tail = self.Node(e)
            self.head = self.tail
        else:
            self.tail.next = self.Node(e)
            self.tail = self.tail.next
        self.size += 1

    def dequeue(self):
        """出队操作"""
        if self.is_empty():
            raise ValueError("Cannot dequeue from an empty queue.")

        ret_node = self.head
        self.head = self.head.next
        ret_node.next = None

        if self.head is None:
            self.tail = None

        self.size -= 1
        return ret_node.e

    def get_front(self):
        """获取队首元素"""
        if self.is_empty():
            raise ValueError("Cannot get front from an empty queue.")

        return self.head.e

    def __str__(self):
        """toString方法"""
        res = ["Queue: front "]

        cur = self.head
        while cur is not None:
            res.append(str(cur.e) + "->")
            cur = cur.next
        res.append("NULL tail")

        return "".join(res)

if __name__ == "__main__":
    queue = LinkedListQueue()

    for i in range(10):
        queue.enqueue(i)
        print(queue)

        if i % 3 == 2:
            queue.dequeue()
            print(queue)