《学习JavaScript数据结构与算法》-- 3.链表(笔记)

爱学习的程序媛

发布于 2022-04-07 16:16:06

26200

代码可运行

文章被收录于专栏：学习/读书笔记学习/读书笔记

运行总次数：0

代码可运行

3.1 链表

链表，是存储有序的元素集合。不同于数组，链表中的元素在内存中并不是连续放置的，每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。

相对于数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。在数组中，我们可以直接访问任何位置的任何元素，而要想访问链表中间的一个元素，则需要从起点（表头）开始迭代链表直到找到所需的元素。

3.1.1 创建链表

class LinkedList {
    constructor(equalsFn = defaultEquals) {
        this.count = 0;
        this.head = undefined;
        this.equalsFn = equalsFn;
    }
}

3.1.2 向链表尾部添加一个新元素

push(element) {
    const node = new Node(element);
    let current;
    if (!this.head) {
        this.head = node;
    } else {
        current = this.head;
        while (current.next) {
            current = current.next;
        }
        current.next = node;
    }
    this.count++;
}

3.1.3 向链表中的特定位置插入一个新元素

insert(element, index) {
    if (index >= 0 && index <= this.count) {
        const node = new Node(element);
        if (index === 0) {
            const current = this.head;
            node.next = current;
            this.head = node;
        } else {
            const previous = this.getElementAt(index - 1);
            node.next = previous.next;
            previous.next = node;
        }
        this.count++;
        return true;
    }
    return false;
}

3.1.4 获取链表中特定位置的元素

getElementAt(index) {
    if (index >= 0 && index <= this.count) {
        let node = this.head;
        for (let i = 0; i < index && node; i++) {
            node = node.next;
        }
        return node;
    }
    return undefined;
}

3.1.5 从特定位置移除一个元素

removeAt(index) {
    if (index >= 0 && index < this.count) {
        let current = this.head;
        if (index === 0) {
            this.head = current.next;
        } else {
            const previous = this.getElementAt(index - 1);
            current = previous.next;
            previous.next = current.next;
        }
        this.count--;
        return current.element;
    }
    return undefined;
}

3.1.6 根据元素的值移除元素

remove(element) {
    const index = this.indexOf(element);
    return this.removeAt(index);
}

3.1.7 获取元素在链表中的索引

indexOf(element) {
    let current = this.head;
    for (let i = 0; i < this.size() && current; i++) {
        if (this.equalsFn(element, current.element)) {
            return i;
        }
        current = current.next;
    }
    return -1;
}

3.1.8 检查链表是否为空

isEmpty() {
    return this.size() === 0;
}

3.1.9 获取链表的长度

size() {
    return this.count;
}

3.1.10 获取链表的头元素

getHead() {
    return this.head;
}

3.1.11 清除链表元素

clear() {
    this.head = undefined;
    this.count = 0;
}

3.1.12 实现toString方法

toString() {
    if (!this.head) {
        return '';
    }
    let objStr = `${this.head.element}`;
    let current = this.head.next;
    for (let i = 1; i < this.size() && current; i++) {
        objStr = `${objStr}, ${current.element}`;
        current = current.next;
    }
    return objStr;
}

3.2 双向链表

在双向链表中，链接是双向的，一个链向下一个元素，一个链向前一个元素。双向链表提供了两种迭代方法：从头到尾或者从尾到头，我们也可以访问一个特定节点的下一个或前一个元素。双向链表可以直接获取头尾的元素，减少过程消耗。

3.2.1 创建双向链表

class DoublyLinkedList extends LinkedList {
    constructor(equalsFn = defaultEquals) {
        super(equalsFn);
        this.tail = undefined;
    }
}

3.2.1 向链表尾部添加一个新元素

push(element) {
    const node = new DoublyNode(element);
    if (!this.head) {
        this.head = node;
        this.tail = node;
    } else {
        this.tail.next = node;
        node.prev = this.tail;
        this.tail = node;
    }
    this.count++;
}

3.2.2 向链表中的特定位置插入一个新元素

insert(element, index) {
    if (index >= 0 && index <= this.count) {
        const node = new DoublyNode(element);
        let current = this.head;
        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) {
            current = this.tail;
            current.next = node;
            node.prev = current;
            this.tail = node;
        } else {
            const previous = this.getElementAt(index - 1);
            current = previous.next;
            node.next = current;
            previous.next = node;
            current.prev = node;
            node.prev = previous;
        }
        this.count++;
        return true;
    }
    return false;
}

3.2.3 从特定位置移除一个元素

removeAt(index) {
    if (index >= 0 && index < this.count) {
        let current = this.head;
        if (index === 0) {
            this.head = this.head.next;
            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.getElementAt(index);
            const previous = current.prev;
            previous.next = current.next;
            current.next.prev = previous;
        }
        this.count--;
        return current.element;
    }
    return undefined;
}

3.2.4 获取元素在链表中的索引

indexOf(element) {
    let current = this.head;
    let index = 0;
    while (current) {
        if (this.equalsFn(element, current.element)) {
            return index;
        }
        index++;
        current = current.next;
    }
    return -1;
}

3.2.5 获取链表尾元素

getTail() {
    return this.tail;
}

3.2.6 清除链表元素

clear() {
    super.clear();
    this.tail = undefined;
}

3.2.7 实现toString方法

toString() {
    if (!this.head) {
        return '';
    }
    let objStr = `${this.head.element}`;
    let current = this.head.next;
    while (current) {
        objStr = `${objStr}, ${current.element}`;
        current = current.next;
    }
    return objStr;
}

3.2.8反向返回链表字符串

inverseToString() {
    if (!this.tail) {
        return '';
    }
    let objStr = `${this.tail.element}`;
    let previous = this.tail.prev;
    while (previous) {
        objStr = `${objStr}, ${previous.element}`;
        previous = previous.prev;
    }
    return objStr;
}

3.3 循环链表

循环链表可以像链表一样只有单向引用，也可以像双向链表一样有双向引用。循环链表最后一个元素指向下一个元素的指针（tail.next）指向第一个元素（head）。双向循环链表有指向head元素的tail.next和指向tail元素的head.prev。

3.3.1 创建循环链表

class CircularLinkedList extends LinkedList {
    constructor(equalsFn = defaultEquals) {
        super(equalsFn);
    }
}

3.3.2 向链表尾部添加一个新元素

push(element) {
    const node = new Node(element);
    let current;
    if (!this.head) {
        this.head = node;
    } else {
        current = this.getElementAt(this.size() - 1);
        current.next = node;
    }
    node.next = this.head;
    this.count++;
}

3.3.3 向链表中的特定位置插入一个新元素

insert(element, index) {
    if (index >= 0 && index <= this.count) {
        const node = new Node(element);
        let current = this.head;
        if (index === 0) {
            if (!this.head) {
                this.head = node;
                node.next = this.head;
            } else {
                node.next = current;
                current = this.getElementAt(this.size());
                this.head = node;
                current.next = this.head;
            }
        } else {
            const previous = this.getElementAt(index - 1);
            node.next = previous.next;
            previous.next = node;
      }
      this.count++;
      return true;
    }
    return false;
}

3.3.4 从特定位置移除一个元素

removeAt(index) {
    if (index >= 0 && index < this.count) {
        let current = this.head;
        if (index === 0) {
            if (this.size() === 1) {
                this.head = undefined;
            } else {
                const removed = this.head;
                current = this.getElementAt(this.size() - 1);
                this.head = this.head.next;
                current.next = this.head;
                current = removed;
            }
        } else {
            const previous = this.getElementAt(index - 1);
            current = previous.next;
            previous.next = current.next;
        }
        this.count--;
        return current.element;
    }
    return undefined;
}

3.4 有序链表

有序链表，是指保持元素有序的链表结构。除了使用排序算法外，我们还可以将元素插入到正确的位置来保证链表的有序性。

3.4.1 创建有序链表

class SortedLinkedList extends LinkedList {
    constructor(equalsFn = defaultEquals, compareFn = defaultCompare) {
        super(equalsFn);
        this.compareFn = compareFn;
    }
}

3.4.2 向链表尾部添加一个新元素

push(element) {
    if (this.isEmpty()) {
        super.push(element);
    } else {
        const index = this.getIndexNextSortedElement(element);
        super.insert(element, index);
    }
}

3.4.3 向链表中的特定位置插入一个新元素

insert(element, index = 0) {
    if (this.isEmpty()) {
        return super.insert(element, index === 0 ? index : 0);
    }
    const pos = this.getIndexNextSortedElement(element);
    return super.insert(element, pos);
}

3.4.4 获取元素的插入位置

getIndexNextSortedElement(element) {
    let current = this.head;
    let i = 0;
    for (; i < this.size() && current; i++) {
        const comp = this.compareFn(element, current.element);
        if (comp === Compare.LESS_THAN) {
            return i;
        }
        current = current.next;
    }
    return i;
}

3.5 创建基于链表的栈

可以使用LinkedList类及其扩展作为内部的数据结构来创建其他的数据类型，例如栈、队列和双向队列。

// 创建基于链表的栈
class StackLinkedList {
    constructor() {
        this.items = new DoublyLinkedList();
    }
    // 向栈中添加元素
    push(element) {
        this.items.push(element);
    }
    // 从栈中移除元素
    pop() {
        if (this.isEmpty()) {
            return undefined;
        }
        const result = this.items.removeAt(this.size() - 1);
        return result;
    }
    // 查看栈顶元素
    peek() {
        if (this.isEmpty()) {
            return undefined;
        }
        return this.items.getElementAt(this.size() - 1).element;
    }
    // 检查栈是否为空
    isEmpty() {
        return this.items.isEmpty();
    }
    // 获取栈的长度
    size() {
        return this.items.size();
    }
    // 清空栈元素
    clear() {
        this.items.clear();
    }
    // 实现toString方法
    toString() {
        return this.items.toString();
    }
}

详细代码：

https://github.com/chenxiaohuan117/learning-javasrcipt-note/tree/main/%E3%80%8A%E5%AD%A6%E4%B9%A0JavaScript%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%E3%80%8B(%E7%AC%AC3%E7%89%88)

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-03-04，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法