数据结构与算法javascript描述-链表

128 阅读3分钟

图解链表结构

链表(非连续的) VS 数组的物理存储结构(连续存储)

链表

链表通过指针将一组零散的内存块串联在一起。其中,我们把内存块称为链表的“结点”。为了将所有的结点串起来,每个链表的结点除了存储数据之外,还需要记录链上的下一个结点的地址。如图所示,我们把这个记录下个结点地址的指针叫作后继指针 next。

链表

我们习惯性地把第一个结点叫作头结点,把最后一个结点叫作尾结点。其中,头结点用来记录链表的基地址。有了它,我们就可以遍历得到整条链表。而尾结点特殊的地方是:指针不是指向下一个结点,而是指向一个空地址 NULL,表示这是链表上最后一个结点。

单链表

循环链表

双向链表

常见的链表操作

链表尾部添加元素

链表中插入元素

代码实现链表


const assert = require("assert");

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

class LinkedList {
  constructor() {
    this.head = null;
    this.length = 0;
  }
  // 在链表尾部追加结点
  append(element) {
    const addNode = new Node(element);
    // 空链表
    if (this.isEmpty()) {
      this.head = addNode;
    } else {
      // 非空链表,先找到链表尾部
      let cur = this.head;
      while (cur.next) {
        cur = cur.next;
      }
      cur.next = addNode;
    }
    this.length += 1;
  }

  insert(position, element) {
    // 边界情况处理
    if (
      (Number.isInteger(position) && position > -1) ||
      position < this.size()
    ) {
      const addNode = new Node(element);
      let cur = this.head;
      let prev = null;
      // 在链表头位置插入
      if (position === 0) {
        this.head = addNode;
        addNode.next = cur;
      } else {
        // 在其他位置插入
        let index = 0;
        while (index < position) {
          prev = cur;
          cur = cur.next;
          index++;
        }
        prev.next = addNode;
        addNode.next = cur;
      }
      this.length++;
    }
  }

  removeAt(position) {
    if (
      (Number.isInteger(position) && position > -1) ||
      position < this.size()
    ) {
      let cur = this.head;
      // 移除链表头
      if (position === 0) {
        this.head = cur.next;
      } else {
        // 移除其他元素
        let index = 0;
        let prev = null;
        while (index < position) {
          prev = cur;
          cur = cur.next;
          index++;
        }
        prev.next = cur.next;
      }
      this.length--;
      return cur;
    }
    return null;
  }

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

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

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

  size() {
    return this.length;
  }
}

// test case
const l = new LinkedList();
l.append(1);
assert.strictEqual(l.head.element, 1);
l.append(2);
l.append(3);
assert.strictEqual(l.length, 3);
l.insert(0, 0);
l.insert(1, 100);
assert.strictEqual(l.head.next.element, 100);
assert.strictEqual(l.removeAt(1).element, 100);
assert.strictEqual(l.size(), 4);
assert.strictEqual(l.head.next.element, 1);
assert.strictEqual(l.indexOf(1), 1)
assert.strictEqual(l.remove(3).element, 3)
assert.strictEqual(l.size(), 3);

链表 VS 数组性能大比拼

链表 VS 数组性能大比拼

不过,数组和链表的对比,并不能局限于时间复杂度。而且,在实际的软件开发中,不能仅仅利用复杂度分析就决定使用哪个数据结构来存储数据。数组简单易用,在实现上使用的是连续的内存空间,可以借助 CPU 的缓存机制,预读数组中的数据,所以访问效率更高。而链表在内存中并不是连续存储,所以对 CPU 缓存不友好,没办法有效预读。

数组的缺点是大小固定,一经声明就要占用整块连续内存空间。如果声明的数组过大,系统可能没有足够的连续内存空间分配给它,导致“内存不足(out of memory)”。如果声明的数组过小,则可能出现不够用的情况。这时只能再申请一个更大的内存空间,把原数组拷贝进去,非常费时。链表本身没有大小的限制,天然地支持动态扩容,我觉得这也是它与数组最大的区别。

所以,在我们实际的开发中,针对不同类型的项目,要根据具体情况,权衡究竟是选择数组还是链表

PS: 感兴趣的可以关注下我的公众号。