单向链表是什么,前端如何实现(数据结构系列)
发布于 3 年前 作者 weidai 2825 次浏览 来自 分享

1. 什么是链表

  • 链表类似于火车:有一个火车头,一堆车厢。火车头会通过节点连接车厢,车厢间也会使用节点依次串联起来。
  • 链表的数据结构

2. 链表与数组对比

共同点

  • 都是用于存储一系列元素

不同点

  • 数组

    • 优点:

      • 编程语言基本都会内置数组结构,使用简单方便
      • []访问对应的元素,访问的时间复杂度为O(1)
*   缺点:
    
    *   固定大小:大多数编程语言定义数组时,需要先声明大小。(js不需要,js底层会根据数组大小,自动伸缩管理容量)
    *   连续空间:在开辟内存时,需要申请连续的空间
    *   数组越往前`` 增删 ``元素时,时间复杂度越高。(js底层为保证连续性,需要移动增删位置之后的元素)
  • 链表

    • 优点:

      • 申请空间时不需要事先确定大小
      • 不需要申请连续的内存空间,内存利用率更高
      • 越往前对链表增删,时间复杂度越低,增删开头时间复杂度为O(1)
*   缺点
    
    *   访问任意位置元素时,需要从头开始遍历,时间复杂度为O(N)

3. 链表代码的实现

class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.count = 0;
        this.head = null;
    }
    // 链表尾部追加元素
    append(value) {
        let newNode = new Node(value);
        if (this.head === null) {
            this.head = newNode;
        } else {
            let currentNode = this.getElementAt(this.count - 1);
            currentNode.next = newNode;
        }
        this.count++;
    }
    // 在指定位置插入元素,越界返回false,表示插入失败
    insert(index, value) {
        if (index < 0 || index > this.count) {
            return false;
        }
        let newNode = new Node(value);

        if (this.head === null) {
            this.head = newNode;
        } else if (index === 0) {
            newNode.next = this.head;
            this.head = newNode;
        } else {
            let lastNode = this.getElementAt(index - 1);
            newNode.next = lastNode.next;
            lastNode.next = newNode;
        }
        this.count++;
        return true;
    }
    // 移除指定元素。若找不到该元素,则返回false,表示移除失败
    remove(value) {
        let lastNode = null;
        let currentNode = this.head;
        while (currentNode) {
            if (currentNode.value === value) {
                if (lastNode === null) {
                    this.head = this.head.next;
                } else {
                    lastNode.next = currentNode.next;
                }
                this.count--;
                return true;
            }
            lastNode = currentNode;
            currentNode = currentNode.next;
        }
        return false;
    }
    // 移除指定位置上的元素。若找不到该位置,则返回false,表示移除失败
    removeAt(index) {
        if (index < 0 || index > this.count - 1) {
            return false;
        }
        if (index === 0) {
            this.head = this.head.next;
        } else {
            let lastNode = this.getElementAt(index - 1);
            lastNode.next = lastNode.next.next;
        }
        this.count--;
        return true;
    }
    // 返回指定位置的节点,越界返回undefined
    getElementAt(index) {
        if (index < 0 || index >= this.count) {
            return undefined;
        }
        let currentNode = this.head;
        for (let i = 0; i < index; i++) {
            currentNode = currentNode.next;
        }
        return currentNode;
    }
    // 返回元素的索引值,若没改元素则返回-1
    indexOf(value) {
        let currentNode = this.head;
        let index = 0;
        while (currentNode) {
            if (currentNode.value === value) {
                return index;
            }
            currentNode = currentNode.next;
            index++;
        }
        return -1;
    }
    // 返回链表元素个数
    size() {
        return this.count;
    }
    // 返回当前是否为空链表
    isEmpty() {
        return this.count === 0
    }
    // 清空链表
    clear() {
        this.count = 0;
        this.head = null;
    }
    // 输出链表每项元素
    toString() {
        let arr = [];
        let currentNode = this.head;
        while (currentNode) {
            arr.push(currentNode.value);
            currentNode = currentNode.next;
        }
        return arr.join(",")
    }
}

4. 线上代码

戳我查看,含测试代码

5. 应用场景

  • 结合数组缺点、链表优点,可得出当频繁对数据增删的话,用链表效率更高;若是频繁读取数据,则数组更优。
  • 队列数据结构,之前是基于数组,在出栈时效率没有基于链表的效率高,后面基于双向链表再实现队列。

6. 相关文章

2 回复

大佬,有没有小程序具体应用场景的案例分享一下啊。

希望社区多些这样正经的文章,少些广告

回到顶部