链表

链表是一种物理存储单元上非连续, 非顺序的存储结构, 数据元素的逻辑顺序是通过链表指针实现的, 链表由一些列结点组成, 每个节点包含两个部分: 一个是存储数据元素的数据域, 另一个是存储下一个结点地址的指针域

链表结构可以充分利用计算机内存空间, 实现灵活的内存动态管理, 但是链表失去了数组孙继读取的优点, 同时链表由于增加了结点的指针域, 空间开销比较大

链表的特点

• 插入删除效率高 O(1), 只需要改变指针指向即可, 随机访问效率低 O(n)(需要从链头到链尾遍历)
• 与数组相比, 内存空间消耗更大, 因为每个存储数据的节点都需要额外的空间存储后继指针

‍

‍

单链表

单链表的每一个节点, 都包含了数据区域和 next 指向下一个节点的指针

代码实现

class LinkNode {
    element: any;
    next: LinkNode | null | undefined;

    constructor(element: any) {
        this.element = element;
        this.next = null;
    }
}

class LinkedList {
    count: number;
    head: LinkNode | null | undefined;
    constructor() {
        this.count = 0;
        this.head = null;
    }
    push(element: any) {
        // 新建节点
        const newNode = new LinkNode(element);
        // 如果链表为空
        if (!this.head) {
            this.count++;
            this.head = newNode;
        } else {
            this.count++;
            let current = this.head;
            // 遍历链表, 直到最后一个元素
            while (current.next) {
                current = current.next;
            }
            current.next = newNode;
        }
        return newNode;
    }
    // 删除指定位置的节点
    removeAt(index: number) {
        let removeNode: LinkNode | null | undefined;
        if (index < 0 || index >= this.count || this.count === 0) {
            return undefined;
        } else {
            // 如果删除第一个元素
            if (index == 0) {
                // 头指针指向第二个元素
                removeNode = this.head;
                this.head = removeNode?.next;
                this.count--;
                console.log("要删除的元素是" + removeNode?.element);
                return removeNode?.element;
            } else {
                // 如果删除的不是第一个元素
                // 找到他的前一个元素
                const prev = this.getNodeAt(index - 1);
                removeNode = prev?.next;
                console.log("要删除的元素是" + removeNode?.element);
                // 要删除的元素前一个元素的next=要删除的元素后一个元素
                prev!.next = removeNode?.next;
                this.count--;
            }
            return removeNode?.element;
        }
    }
    remove(element: any) {
        const index = this.indexOf(element);

        if (index === -1) {
            return undefined;
        } else {
            return this.removeAt(index);
        }
    }
    indexOf(element: any) {
        // 根据数据, 返回索引
        let current = this.head;
        let index = 0;
        while (current?.next) {
            if (JSON.stringify(current.element) == JSON.stringify(element)) {
                return index;
            }
            index++;
            current = current?.next;
        }
        return -1;
    }

    getNodeAt(index: number) {
        let current = this.head;

        if (index < 0 || index >= this.count || this.count === 0) {
            return undefined;
        } else {
            for (let i = 0; i < index; i++) {
                current = current?.next;
            }
            return current;
        }
    }
    toString() {
        let current = this.head;
        let str = "";
        while (current) {
            str += JSON.stringify(current.element) + "-";
            current = current?.next;
        }
        return str;
    }
    insertElement(element: any, index: number) {
        if (index < 0 || index > this.count) {
            return undefined;
        }
        // 如果插入最后一个元素
        if (index === this.count) {
            return this.push(element);
        }
        const newNode = new LinkNode(element);
        // 如果在第一个元素之前插入
        if (index === 0) {
            this.count++;
            newNode.next = this.head;
            this.head = newNode;
            return this.head;
        }
        // 在指定位置插入一个元素
        // 新建一个节点, 新节点的next=插入位置的next, 插入位置的next=新节点,
        // 插入位置的节点
        const insertedNode = this.getNodeAt(index - 1);
        if (insertedNode) {
            this.count++;
            newNode.next = insertedNode?.next;
            insertedNode.next = newNode;
            return newNode;
        } else {
            return undefined;
        }
    }
    size() {
        return this.count;
    }
    isEmpty() {
        return this.size() === 0;
    }
}

‍

‍

单链表的应用

// 回文数检查
function check(str: string) {
    // 全部转小写, 去掉空格
    str = str.toLocaleLowerCase().split(" ").join("");
    console.log("处理后的字符串:" + str);
    // 将字符串加入队列
    const list = new LinkedList();
    for (let i = 0; i < str.length; i++) {
        list.push(str[i]);
    }
    let tag = true;

    // 取出首尾元素进行对比
    while (list.size() > 1) {
        if (list.removeAt(0) !== list.removeAt(list.size() - 1)) {
            tag = false;
            break;
        }
    }
    console.log(tag);
}

check("abc dc bA");

双向链表

节点除了数据区域外, 还有两个指针, 分别为前驱指针 prev 和后继指针 next

在双向链表中删除元素需要考虑以下边界条件：

1. 如果链表为空，不能进行删除操作。
2. 如果要删除的元素是头结点或者尾节点，则需要更新 head​ 或 tail​ 指针。
3. 如果要删除的元素不是头节点或尾节点，则需要更新其前驱节点的 next​ 指针和后继节点的 prev​ 指针。
4. 如果输入的索引超出链表长度，应该返回 undefined​。

特别地，如果链表只有一个元素，那么删除唯一一个元素后，需要将 head​ 和 tail​ 指针都置为 null​。

代码实现

import { LinkNode, LinkedList } from "./单链表";
class doubleLinkNode extends LinkNode {
    prev: doubleLinkNode | null | undefined;
    next: doubleLinkNode | null | undefined;
    constructor(element: any) {
        super(element);
        this.prev = null;
    }
}
class doubleLinkList extends LinkedList {
    head: doubleLinkNode | null | undefined;
    tail: doubleLinkNode | null | undefined;
    constructor() {
        super();
        this.tail = null;
    }
    push(element: any): doubleLinkNode {
        const node = new doubleLinkNode(element);
        // 如果链表内没有元素,
        // 直接添加
        if (this.head == null) {
            this.head = node;
            this.tail = node;
        } else {
            // 如果链表内有元素
            // 当前的最后一个元素的next指向新元素,
            // 新元素的prev指向当前的元素
            // 改变tail的指向
            this.tail!.next = node;
            node.prev = this.tail;
            this.tail = node;
        }
        this.count++;

        return node;
    }
    insert(element: any, index: number) {
        // 首先判断index是否符合条件
        if (index < 0 || index > this.count) {
            return undefined;
        }
        const node = new doubleLinkNode(element);

        if (index === 0) {
            // 如果没有元素
            if (!this.head) {
                this.head = node;
                this.tail = node;
            } else {
                // 如果有元素想要插入最前
                node.next = this.head;
                this.head.prev = node;
                this.head = node;
            }
        } else if (index === this.count) {
            // 如果是在最后插入
            this.tail!.next = node;
            node.prev = this.tail;
            this.tail = node;
        } else {
            // 在内部插入
            // 前一个结点的next=新节点
            // 后一个节点的prev=新节点
            // 新节点的prev=前一个结点
            // 新节点的next=后一个节点
            const prevNode = this.getNodeAt(index - 1) as doubleLinkNode;
            const nextNode = this.getNodeAt(index) as doubleLinkNode;

            prevNode.next = node;
            nextNode.prev = node;
            node.prev = prevNode;
            node.next = nextNode;
        }

        this.count++;
        return node;
    }

    removeAt(index: number) {
        //在双向链表中删除元素需要考虑以下边界条件：
        // 如果链表为空，不能进行删除操作。
        // 如果要删除的元素是头结点或者尾节点，则需要更新 head 或 tail 指针。
        // 如果要删除的元素不是头节点或尾节点，则需要更新其前驱节点的 next 指针和后继节点的 prev 指针。
        // 如果输入的索引超出链表长度，应该返回 undefined。
        // 特别地，如果链表只有一个元素，那么删除唯一一个元素后，需要将 head 和 tail 指针都置为 null。
        if (index < 0 || index >= this.count || this.count == 0) {
            return undefined;
        }
        let current: doubleLinkNode | null | undefined;
        if (index === 0) {
            current = this.head;
            if (this.count === 1) {
                this.head = null;
                this.tail = null;
            } else {
                this.head = current?.next;
                this.head!.prev = null;
            }
        } else if (index === this.count - 1) {
            // 删除最后的元素
            current = this.tail;
            this.tail = current?.prev;
            this.tail!.next = null;
        } else {
            // 删除中间的元素
            const prevNode = this.getNodeAt(index - 1) as doubleLinkNode;
            current = prevNode.next;
            prevNode.next = current?.next;
            current!.next!.prev = prevNode;
        }
        this.count--;
        return current;
    }
}

‍

循环链表

循环列表的最后一个结点的 next 指向 head 结点

代码实现

import { LinkNode, LinkedList } from "./单链表";

class circularLinkedList extends LinkedList {
    constructor() {
        super();
    }
    push(element: any): LinkNode {
        const newNode = new LinkNode(element);

        // 如果空表
        if (this.count === 0) {
            this.head = newNode;
        } else {
            const current = this.getNodeAt(this.count - 1);
            current!.next = newNode;
        }

        newNode.next = this.head;
        this.count++;
        return newNode;
    }
    insertElement(element: any, index: number): LinkNode | undefined {
        if (index < 0 || index > this.count) {
            return;
        }
        const newNode = new LinkNode(element);
        let current = this.head;
        if (index === 0) {
            // 如果没有元素
            if (this.count === 0) {
                this.head = newNode;
                newNode.next = this.head;
            } else {
                newNode.next = current;
                this.head = newNode;

                // 将最后的元素重新指向头
                current = this.getNodeAt(this.count - 1);
                current!.next = this.head;
            }
        } else {
            // 在中间插入
            current = this.getNodeAt(index - 1);
            newNode.next = current?.next;
            current!.next = newNode;
        }
        this.count++;
        return newNode;
    }

    removeAt(index: number) {
        if (index < 0 || index >= this.count || this.count === 0) {
            return;
        }
        let current = this.head;
        if (index === 0) {
            if (this.count === 1) {
                // 如果只有一个元素
                this.head = null;
            } else {
                let last = this.getNodeAt(this.count - 1);
                this.head = current?.next;
                last!.next = this.head;
            }
        } else {
            current = this.getNodeAt(index - 1);
            current!.next = current?.next?.next;
        }
        this.count--;
        return current;
    }
}

‍