链表

是一种不连续的数据集合。

链表由节点组成，节点有存储的元素和指向下一节点的指针。

链表的核心思想就是：

• 查找时从表头开始，沿着每一个节点的 next 指针向下查找。a
• 增删改时则调整 next 指针即可。

class Node<T> {
    // 传入的元素会自动变为属性
    constructor(public element: T, public next?: Node<T>) { }
}

一个正常的链表应该有:

• 增加元素
• 插入元素
• 获取元素
• 查找元素
• 删除元素
• 查看链表大小
• 查看链表是否为空

class LinkedList<T> {
    protected count: number = 0
    protected head?: Node<T> | undefined

    push(element: T): void {
        const node = new Node(element)
        let current

        // 第一个元素时 直接添加
        if (this.head == null) this.head = node
        else {
            // 找到最后一个元素在其之后添加
            current = this.getNodeAt(this.size() - 1)
            current.next = node
        }

        // 最后 计数 加一
        this.count++
    }

    getNodeAt(index: number): Node<T> {
        if (index >= 0 &amp;&amp; index <= this.count) {
            let node = this.head

            // 在 第几位 上就 迭代 多少次
            for (let i = 0; i < index &amp;&amp; node !== null; i++) node = node?.next

            return node as Node<T>
        }
        return undefined!
    }

    getElementAt(index: number): T {
        return this.getNodeAt(index)?.element!
    }

    insert(element: T, index: number): boolean {
        if (index >= 0 &amp;&amp; index <= this.count) {
            const node = new Node(element)

            // 插入元素 分 第一个 和 非第一个 两种情况
            if (index === 0) {
                const current = this.head
                node.next = current
                this.head = node
            } else {
                // 解开 该位置的 next 连接 插入 新节点
                const previous = this.getNodeAt(index - 1)
                node.next = previous.next
                previous.next = node
            }

            // 计数 加一
            this.count++
            return true
        }
        return false
    }

    removeAt(index: number): T {
        if (index >= 0 &amp;&amp; index < this.count) {
            let current = this.head

            // 移出元素 分 第一个 和 非第一个 两种情况
            if (index === 0) this.head = current?.next
            else {
                const previous = this.getNodeAt(index - 1)
                current = previous.next
                previous.next = current?.next
            }

            // 计数减一
            this.count--
            return current?.element!
        }
        return undefined!
    }

    remove(element: T): T {
        // 调用 removeAt
        const index = this.indexOf(element)
        return this.removeAt(index)
    }

    indexOf(element: T): number {
        let current = this.head

        // 迭代查找相等元素
        for (let i = 0; i < this.size() &amp;&amp; current !== null; i++) {
            // 用到了 判断相等方法
            if (element === current?.element!) return i
            current = current?.next
        }
        return -1
    }

    isEmpty(): boolean {
        return this.size() === 0
    }

    size(): number {
        return this.count
    }

    getHead(): Node<T> {
        return this.head!
    }

    clear(): boolean {
        this.head = undefined
        this.count = 0
        return this.size() === 0
    }
}

双端链表 在普通链表的基础上，多了一个指向前一节点的指针。由原来的单向变为了双向。

class DoublyNode<T> {
    constructor(
        /** 当前节点保存的元素 */
        public element: T,
        /** 当前节点所指向的上一节点 */
        public prev?: DoublyNode<T>,
        /** 当前节点所指向的下一节点 */
        public next?: DoublyNode<T>
    ) { }
}

class DoublyLinkedList extends LinkedList<T> {
    push(element: T): void {
        const node = new DoublyNode(element)

        if (this.head === null) {
            this.head = node
            this.tail = node
        }
        else {
            // 交换指针
            // 先将链表尾部的 next 指针指向 node
            this.tail!.next = node
            // 再将 node 的 prev 指针指向 tail
            node.prev = this.tail
            // 最后将 链表的 tail 替换为 node
            this.tail = node
        }
        this.count++
    }

    insert(element: T, index: number): boolean {
        if (index >= 0 &amp;&amp; index <= this.count) {
            const node = new DoublyNode(element)
            let current = this.head

            // 插入第一个
            if (index === 0) {
                // 链表为空
                if (this.head === null) {
                    this.head = node
                    this.tail = node
                }
                // 链表不为空
                else {
                    // 将 node 的 next 指针指向 原本的 head
                    node.next = this.head
                    // 再将 head 的 prev 指针指向 node
                    this.head!.prev = node
                    // 然后将 head 变更为 node
                    this.head = node
                }
            }
            // 插入到最后一个
            else if (index === this.count) {
                current = this.tail
                current!.next = node
                node.prev = current
                this.tail = node
            }
            // 普通情况
            else {
                // 获取节点
                const previous = this.getNodeAt(index - 1)

                // 将 current 变更为 获取的节点的 next 指向的节点
                current = previous.next
                // 将 node 的 next 指针指向 current
                node.next = current
                // 将 获取的节点的 next 指向变更为 node
                previous.next = node
                // 将 current 的 prev 指向 node
                current!.prev = node
                // 将 node 的 prev 指向 获取的节点
                node.prev = previous
            }
            this.count++
            return true
        }
        return false
    }

    removeAt(index: number): T {
        if (index >= 0 &amp;&amp; index < this.count) {
            let current = this.head

            // 删除第一个
            if (index === 0) {
                this.head = this.head?.next
                // 如果只有一个元素 需要同时调整 tail
                if (this.count === 1) this.tail = undefined
                else this.head!.prev = undefined
            }
            // 删除最后一个
            else if (index === this.count - 1) {
                current = this.tail
                this.tail = current?.prev
                this.tail!.next = undefined
            }
            // 普通删除
            else {
                current = this.getNodeAt(index)
                const previous = current.prev
                const next = current.next

                previous!.next = next
                next!.prev = previous
            }
            this.count--
            return current!.element
        }
        return undefined!
    }

    getTail(): DoublyNode<T> | undefined {
        return this.tail
    }

    clear(): boolean {
        this.head = undefined
        this.count = 0
        return this.size() === 0
    }
}

普通链表访问到链尾时，会因为没有下一个指针而停止。而循环链表则是会重新访问到表头。

class CircularLinkedList<T> extends LinkedList<T> {
    push(element: T): void {
        const node = new Node(element)
        let current

        if (this.head === null) this.head = node
        else {
            current = this.getNodeAt(this.size() - 1)
            current.next = node
        }

        // 循环链表的最后一个元素的 next 指向 head
        node.next = this.head
        this.count++
    }

    insert(element: T, index: number): boolean {
        if (index >= 0 &amp;&amp; index <= this.count) {
            const node = new Node(element)
            let current = this.head

            if (index === 0) {
                // 插入第一个元素的两种情况

                // 无元素
                if (this.head === null) {

                    this.head = node
                    // 循环链表 的 最后一个 节点
                    // 的 next 指向 链表 head
                    node.next = this.head
                }
                // 已有若干元素
                else {
                    let tail = this.getNodeAt(this.size() - 1)
                    this.head = node
                    node.next = current
                    tail.next = this.head
                }
            }
            else {
                const previous = this.getNodeAt(index - 1)
                node.next = previous.next
                previous.next = node
            }
            this.count++
            return true
        }
        return false
    }

    removeAt(index: number): T {
        if (index >= 0 &amp;&amp; index < this.count) {
            let current = this.head
            if (index === 0) {
                // 删除第一个时 分两种情况

                // 只有一个元素
                if (this.size() === 1) this.head = undefined
                // 有若干元素
                else {
                    let tail = this.getNodeAt(this.size() - 1)
                    this.head = this.head?.next
                    // 循环链表的最后一个节点的 next 需要指向 head
                    tail.next = this.head
                }
            }else {
                const previous = this.getNodeAt(index - 1)
                current = previous.next
                previous.next = current?.next
            }
            this.count--
            return current!.element
        }
        return undefined!
    }
        }
    }
}