链表（Linked List）

首发于：2020-08-03

概念

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。

单链表

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

/**
 * @class
 * 单链表节点
 */
class Node {
    constructor(data) {
        // 节点的数据域
        this.data = data
        // 下一个节点的指针域
        this.next = null
    }
}

/**
 * @class
 * 单链表类
 */
class SinglyLinkedList {
    constructor() {
        // 表头节点
        this.head = new Node('head')
        // 链表的长度
        this.size = 0
        // 当前节点位置
        this.currentNode = this.head
    }

    /**
     * 查找元素所在的节点
     * @param {*} item 查找的元素 
     * @return {Node} 节点对象
     */
    find(item) {
        let currentNode = this.head
        while (currentNode && currentNode.data !== item) {
            // 没找到当前节点，就切换到下一个节点继续找，直到找到为止
            currentNode = currentNode.next
        }
        return currentNode
    }

    /**
     * 获取链表的最后一个节点
     */
    findLast() {
        let currentNode = this.head
        while (currentNode.next) {
            currentNode = currentNode.next
        }
        return currentNode
    }

    /**
     * 查找当前节点的前一个节点
     * @param {*} item 当前节点信息
     */
    findPre(item) {
        // 从最开头开始找
        let currentNode = this.head;
        while (currentNode && currentNode.next && currentNode.next.data !== item) {
            if (currentNode.next) {
                currentNode = currentNode.next;
            } else {
                currentNode = null;
            }
        }
        return currentNode;
    }   

    /**
     * 在链表的尾部添加元素
     * @param {*} item 需要插入的节点
     */
    append(item) {
        let currentNode = this.findLast()
        if (!currentNode) return
        currentNode.next = new Node(item)
        this.size++
    }

    /**
     * 向链表中插入元素
     * @param {*} item 需要插入的节点
     * @param {*} preItem 前一个节点（可以不传这个参数）
     */
    insert(item, preItem) {
        if (preItem) {
            // 插入到某个元素之后
            let preNode = this.find(preItem)
            if (!preNode) return // 没有找到这个节点

            let newNode = new Node(item)
            // 前一个节点原来的下一个节点变成了新节点的下一个节点
            newNode.next = preNode.next
            // 前一个节点现在的下一个节点变成了新节点
            preNode.next = newNode
            this.size++
        } else {
            // 默认插入到最后一个元素
            this.append(item)
        }       
    }

    /**
     * 在链表中删除一个节点
     * @param {*} item 节点元素
     */
    remove(item) {
        // 找到当前节点
        let currentNode = this.find(item)
        if (!currentNode) {
            // 找不到此节点
            return
        }
        if (item === 'head') {
            // 想要移除头节点
            if (this.isEmpty() === false) {
                // 不是空链，不允许删除头节点
                return;
            } else {
                // 是空链则重置
                this.clear();
                return;
            }
        }
        // 找到该节点的上一个节点
        let preNode = this.findPre(item)        
        if (!preNode) {
            // 找不到此节点
            return
        }
        if (currentNode.next) {
            // 当前节点的下一个节点如果存在
            preNode.next = currentNode.next
        } else {
            preNode.next = null
        }
        this.size--
    }

    /**
     * 判断链表是否为空
     * @returns {boolean}
     */
    isEmpty() {
        return this.size === 0
    }

    /**
     * 获取链表的长度
     * @returns {Number}
     */
    getLength() {
        return this.size
    }

    /**
     * 从当前节点向前移动 n 个节点
     * @param {Number} n 移动的节点数
     */
    advance(n) {
        while ((n--) && this.currentNode.next) {
            this.currentNode = this.currentNode.next;
        }
        return this.currentNode;
    }

    /**
     * 显示当前节点
     * @returns {Node} 当前节点
     */
    show() {
        return this.currentNode
    }

    /**
     * 链表的遍历显示
     * @returns {String}
     */
    display() {
        let res = '';
        let currentNode = this.head;
        while (currentNode) {
            res += currentNode.data;
            currentNode = currentNode.next;
            if(currentNode) {
                res += '->';
            }
        }
        console.log(res);
        return res
    }
    
    /**
     * 清空链表
     */
    clear() {
        this.head.next = null;
        this.currentNode = this.head
        this.size = 0;
    }
}

const sll = new SinglyLinkedList()
sll.display()
sll.append(1)
sll.append(3)
sll.append(4)
sll.insert(2, 1)
sll.remove(3)
sll.display()

双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

/**
 * @class
 * 双向链表节点
 */
class Node {
    constructor(data) {
        // 节点的数据域
        this.data = data
        // 下一个节点的指针域
        this.next = null
        // 上一个节点的指针域
        this.prev = null
    }
}

/**
 * @class
 * 双向链表类
 */
class DoublyLinkedList {
    constructor() {
        // 表头节点
        this.head = new Node('head')
        // 链表的长度
        this.size = 0
        // 当前节点位置
        this.currentNode = this.head
    }

    /**
     * 查找元素所在的节点
     * @param {*} item 查找的元素 
     * @return {Node} 节点对象
     */
    find(item) {
        let currentNode = this.head
        while (currentNode && currentNode.data !== item) {
            // 没找到当前节点，就切换到下一个节点继续找，直到找到为止
            currentNode = currentNode.next
        }
        return currentNode
    }

    /**
     * 获取链表的最后一个节点
     */
    findLast() {
        let currentNode = this.head
        while (currentNode.next) {
            currentNode = currentNode.next
        }
        return currentNode
    }

    /**
     * 查找当前节点的前一个节点
     * @param {*} item 当前节点信息
     */
    findPre(item) {
        // 从最开头开始找
        let currentNode = this.find(item)
        let preNode = null
        if (currentNode && currentNode.prev) {
            preNode = currentNode.prev
        }
        return preNode
    }

    /**
     * 在链表的尾部添加元素
     * @param {*} item 需要插入的节点
     */
    append(item) {
        let currentNode = this.findLast()
        if (!currentNode) return
        let newNode = new Node(item)
        newNode.prev = currentNode
        currentNode.next = newNode
        this.size++
    }

    /**
     * 向链表中插入元素
     * @param {*} item 需要插入的节点
     * @param {*} preItem 前一个节点（可以不传这个参数）
     */
    insert(item, preItem) {
        if (preItem) {
            // 插入到某个元素之后
            let preNode = this.find(preItem)
            if (!preNode) return // 没有找到这个节点
            let nextNode = preNode.next
            let newNode = new Node(item)
            // 前一个节点原来的下一个节点变成了新节点的下一个节点
            newNode.next = nextNode
            // 前一个节点变成新节点的上一个节点
            newNode.prev = preNode

            if (nextNode) {
                // 如果下一个节点存在，那么下一个节点的前一个节点就是新的节点
                nextNode.prev = newNode
            }
            // 前一个节点现在的下一个节点变成了新节点
            preNode.next = newNode
            this.size++
        } else {
            // 默认插入到最后一个元素
            this.append(item)
        }
    }

    /**
     * 在链表中删除一个节点
     * @param {*} item 节点元素
     */
    remove(item) {
        // 找到当前节点
        let currentNode = this.find(item)
        if (!currentNode) {
            // 找不到此节点
            return
        }
        if (item === 'head') {
            // 想要移除头节点
            if (this.isEmpty() === false) {
                // 不是空链，不允许删除头节点
                return;
            } else {
                // 是空链则重置
                this.clear();
                return;
            }
        }
        // 找到该节点的上一个节点
        let preNode = currentNode.prev       
        if (!preNode) {
            // 找不到此节点
            return
        }
        if (currentNode.next) {
            // 当前节点的下一个节点如果存在
            preNode.next = currentNode.next
            currentNode.next.prev = preNode
        } else {
            preNode.next = null
        }
        this.size--
    }

    /**
     * 判断链表是否为空
     * @returns {boolean}
     */
    isEmpty() {
        return this.size === 0
    }

    /**
     * 获取链表的长度
     * @returns {Number}
     */
    getLength() {
        return this.size
    }

    /**
     * 从当前节点向前移动 n 个节点
     * @param {Number} n 移动的节点数
     */
    advance(n) {
        while ((n--) && this.currentNode.next) {
            this.currentNode = this.currentNode.next;
        }
        return this.currentNode;
    }

    /**
     * 从当前节点往回移动 n 个节点
     * @param {Number} n 移动的节点数
     */
    back(n) {
        while ((n--) && this.currentNode.prev) {
            this.currentNode = this.currentNode.prev;
        }
        return this.currentNode;
    }

    /**
     * 显示当前节点
     * @returns {Node} 当前节点
     */
    show() {
        return this.currentNode
    }

    /**
     * 链表的遍历显示
     * @returns {String}
     */
    display() {
        let res = '';
        let currentNode = this.head;
        while (currentNode) {
            res += currentNode.data;
            currentNode = currentNode.next;
            if(currentNode) {
                res += '->';
            }
        }
        console.log(res);
        return res
    }

    /**
     * 链表反向的遍历显示
     * @returns {String}
     */
    displayReverse() {
        let res = '';
        let currentNode = this.findLast();
        while (currentNode) {
            res += currentNode.data;
            currentNode = currentNode.prev;
            if(currentNode) {
                res += '->';
            }
        }
        console.log(res);
        return res
    }
    
    /**
     * 清空链表
     */
    clear() {
        this.head.next = null;
        this.currentNode = this.head
        this.size = 0;
    }
}

const dll = new DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.append(4)
dll.append(5)
dll.insert(6, 5)
dll.display()
dll.displayReverse()

循环链表

循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。

/**
 * @class
 * 双向链表节点
 */
class Node {
    constructor(data) {
        // 节点的数据域
        this.data = data
        // 下一个节点的指针域
        this.next = null
        // 上一个节点的指针域
        this.prev = null
    }
}

/**
 * @class
 * 双向循环链表类
 */
class CircularDoublyLinkedList {
    constructor() {
        // 表头节点
        this.head = new Node('head')
        this.head.next = this.head
        this.head.prev = this.head
        // 链表的长度
        this.size = 0
        // 当前节点位置
        this.currentNode = this.head
    }

    /**
     * 查找元素所在的节点
     * @param {*} item 查找的元素 
     * @return {Node} 节点对象
     */
    find(item) {
        let currentNode = this.head
        while (currentNode && currentNode.data !== item) {
            // 没找到当前节点，就切换到下一个节点继续找，直到找到为止
            currentNode = currentNode.next
        }
        return currentNode
    }

    /**
     * 获取链表的最后一个节点
     */
    findLast() {
        return this.head.prev
    }

    /**
     * 查找当前节点的前一个节点
     * @param {*} item 当前节点信息
     */
    findPre(item) {
        // 从最开头开始找
        let currentNode = this.find(item)
        let preNode = null
        if (currentNode) {
            preNode = currentNode.prev
        }
        return preNode
    }

    /**
     * 在链表的尾部添加元素
     * @param {*} item 需要插入的节点
     */
    append(item) {
        let currentNode = this.findLast()
        let newNode = new Node(item)
        newNode.prev = currentNode
        
        // 形成环
        newNode.next = currentNode.next
        currentNode.next.prev = newNode

        currentNode.next = newNode
        this.size++
    }

    /**
     * 向链表中插入元素
     * @param {*} item 需要插入的节点
     * @param {*} preItem 前一个节点（可以不传这个参数）
     */
    insert(item, preItem) {
        if (preItem) {
            // 插入到某个元素之后
            let preNode = this.find(preItem)
            if (!preNode) return // 没有找到这个节点
            let nextNode = preNode.next
            let newNode = new Node(item)
            // 前一个节点原来的下一个节点变成了新节点的下一个节点
            newNode.next = nextNode
            // 前一个节点变成新节点的上一个节点
            newNode.prev = preNode
            // 下一个节点的前一个节点就是新的节点
            nextNode.prev = newNode
            // 前一个节点现在的下一个节点变成了新节点
            preNode.next = newNode
            this.size++
        } else {
            // 默认插入到最后一个元素
            this.append(item)
        }
    }

    /**
     * 在链表中删除一个节点
     * @param {*} item 节点元素
     */
    remove(item) {
        // 找到当前节点
        let currentNode = this.find(item)
        if (!currentNode) {
            // 找不到此节点
            return
        }
        if (item === 'head') {
            // 想要移除头节点
            if (this.isEmpty() === false) {
                // 不是空链，不允许删除头节点
                return;
            } else {
                // 是空链则重置
                this.clear();
                return;
            }
        }
        // 找到该节点的上一个节点
        let preNode = currentNode.prev       
        preNode.next = currentNode.next
        currentNode.next.prev = preNode
        this.size--
    }

    /**
     * 判断链表是否为空
     * @returns {boolean}
     */
    isEmpty() {
        return this.size === 0
    }

    /**
     * 获取链表的长度
     * @returns {Number}
     */
    getLength() {
        return this.size
    }

    /**
     * 从当前节点向前移动 n 个节点
     * @param {Number} n 移动的节点数
     */
    advance(n) {
        while ((n--) && this.currentNode.next) {
            this.currentNode = this.currentNode.next;
        }
        return this.currentNode;
    }

    /**
     * 从当前节点往回移动 n 个节点
     * @param {Number} n 移动的节点数
     */
    back(n) {
        while ((n--) && this.currentNode.prev) {
            this.currentNode = this.currentNode.prev;
        }
        return this.currentNode;
    }

    /**
     * 显示当前节点
     * @returns {Node} 当前节点
     */
    show() {
        return this.currentNode
    }

    /**
     * 链表的遍历显示
     * @returns {String}
     */
    display() {
        let res = 'head';
        let currentNode = this.head;
        let lastNode = this.findLast()
        while (currentNode !== lastNode) {
            currentNode = currentNode.next;
            res += `->${currentNode.data}`;
        }
        console.log(res);
        return res
    }

    /**
     * 链表反向的遍历显示
     * @returns {String}
     */
    displayReverse() {
        let res = '';
        let currentNode = this.findLast();
        while (currentNode.data !== 'head') {
            res += `${currentNode.data}->`;
            currentNode = currentNode.prev;
        }
        res += 'head'
        console.log(res);
        return res
    }
    
    /**
     * 清空链表
     */
    clear() {
        this.head.next = this.head;
        this.head.prev = this.head;
        this.currentNode = this.head
        this.size = 0;
    }
}

const cdll = new CircularDoublyLinkedList()
cdll.append(1)
cdll.append(2)
cdll.append(3)
cdll.append(4)
cdll.append(5)
cdll.insert(6, 5)
cdll.display()
cdll.displayReverse()

链表（Linked List） ​

概念 ​

单链表 ​

双向链表 ​

循环链表 ​

链表（Linked List）

概念

单链表

双向链表

循环链表