乐趣区

关于前端:JavaScript-数据结构与算法单向链表

jiezi

链表和数组

链表和数组的实现机制齐全不同。

数组

  • 存储多个元素，数组（或列表）可能是最罕用的数据结构。
  • 简直每一种编程语言都有默认实现数组构造，提供了一个便当的 [] 语法来拜访数组元素。

  • 数组毛病：

    数组的创立须要申请一段间断的内存空间(一整块内存)，并且大小是固定的，以后数组不能满足容量需要时，须要扩容。(个别状况下是申请一个更大的数组，比方 2 倍，而后将原数组中的元素复制过来)

    在数组结尾或两头地位插入数据的老本很高，须要进行大量元素的位移。

链表

  • 不同于数组，链表中的元素在内存中不用是间断的空间。
  • 链表的每个元素由一个存储元素自身的节点和一个指向下一个元素的援用 (有些语言称为指针) 组成。

  • 链表长处：

    内存空间不用是间断的，能够充沛利用计算机的内存，实现灵便的内存动静治理。

    链表不用在创立时就确定大小，并且大小能够有限延长上来。

    链表在插入和删除数据时，工夫复杂度能够达到 O(1)，绝对数组效率高很多。

  • 链表毛病：

    拜访任何一个地位的元素时，须要从头开始拜访。(无奈跳过第一个元素拜访任何一个元素)

    无奈通过下标值间接拜访元素，须要从头开始一个个拜访，直到找到对应的元素。

    尽管能够轻松地达到下一个节点，然而回到前一个节点是很难的。

单向链表

单向链表相似于火车，有一个火车头，火车头会连贯一个节点，节点上有乘客，并且这个节点会连贯下一个节点，以此类推。

  • 链表的数据结构

    head 属性指向链表的第一个节点。
    链表中的最初一个节点指向 null。
    当链表中一个节点也没有的时候，head 间接指向 null。

链表中的常见操作

  • append(element) 向链表尾部增加一个新的项。
  • insert(position, element) 向链表的特定地位插入一个新的项。
  • get(position) 获取对应地位的元素。
  • indexOf(element) 返回元素在链表中的索引。如果链表中没有该元素就返回 -1。
  • update(position, element) 批改某个地位的元素。
  • removeAt(position) 从链表的特定地位移除一项。
  • remove(element) 从链表中移除一项。
  • isEmpty() 如果链表中不蕴含任何元素，返回 trun，如果链表长度大于 0 则返回 false。
  • size() 返回链表蕴含的元素个数，与数组的 length 属性相似。
  • toString() 因为链表项应用了 Node 类，就须要重写继承自 JavaScript 对象默认的 toString 办法，让其只输入元素的值。

单向链表的封装

创立单向链表类

先创立单向链表类 LinkedList，增加根本属性，再逐渐实现单向链表的罕用办法。

class LinkedList {
 // 初始化链表长度为 0
 length = 0;
 // 初始 head 为 null，head 指向链表的第一个节点
 head = null;
 // 外部类（链表里的节点 Node）Node = class {
  data:
  next = null;
  constructor(data) {this.data = data}
 };
}

实现 append() 办法

// append() 往链表尾部追加数据
append(data) {
 // 1. 创立新节点
 const newNode = new this.Node(data)
 // 2. 追加新节点
 if (this.length === 0) {
  // 链表长度为 0，只有 head 的时候
  this.head = newNode;
 } else {
  // 链表长度大于 0 时，在最初面增加新节点
  let currentNode = this.head
   // 当 currentNode.next 不为空时
   // 循序顺次找最初一个节点，即节点的 next 为 null 时
   while (currentNode.next !== null) {currentNode = currentNode.next;}
   // 最初一个节点的 next 指向新节点
  currentNode.next = newNode;
 }
 // 3. 追加完新节点后，链表长度 +1
 this.length++
}

实现 toString() 办法

toString() {
 let currentNode = this.head;
 let result = '';
 // 遍历所有的节点，拼接为字符串，直到节点为 null
 while (currentNode) {
  result += currentNode.data + ' ';
  currentNode = currentNode.next;
 }
 return result;
}

实现 insert() 办法

// insert() 在指定地位（position）插入节点
insert(position, data) {
 // position 新插入节点的地位
 // position = 0 示意新插入后是第一个节点
 // position = 1 示意新插入后是第二个节点
 
 // 对 position 进行越界判断，不能小于 0 或大于链表长度
 if (position < 0 || position > this.length) return false;
 
 // 创立新节点
 const newNode = new this.Node(data)

 // 插入节点 
 if (position === 0) {
  // position = 0 的状况
  // 让新节点的 next 指向原来的第一个节点，即 head
  newNode.next = this.head;
  // head 赋值为 newNode
  this.head = newNode
 } else {
  // 0 < position <= length 的状况
  // 初始化一些变量
  let currentNode = this.head; // 以后节点初始化为 head
  let previousNode = null; // head 的 上一个节点 为 null
  let index = 0; // head 的 index 为 0
  
  // 在 0 ~ position 之间遍历，一直地更新 currentNode 和 previousNode
  // 直到找到要插入的地位
  while(index++ < position) {
   previousNode = currentNode;
   currrentNode = currentNode.next;
  }

   // 在以后节点和以后节点的上一个节点之间插入新节点，即它们的扭转指向
   // previous currentNode(position)
   newNode.next = currentNode;
   previous.next = newNode;
 }
 
 // 更新链表长度
 this.length++;
 return newNode;
}

实现 getData() 办法

获取指定地位（position）的 data。

getData(position) {
 // position 越界判断
 if (position < 0 || position >= this.length) return null;
 // 获取指定 position 节点的 data
 let currentNode = this.head;
 let index = 0
 
 while(index++ < position) {currentNode = currentNode.next}
 // 返回 data
 return currentNode.data
}

实现 indexOf() 办法

indexOf(data) 返回指定 data 的 index，如果没有，返回 -1。

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

实现 update() 办法

update(position, data) 批改指定地位节点的 data。

update(position, data) {
 // position 越界判断
 if (position < 0 || position >= this.length) return false;
 // 通过循环遍历，找到 position 的节点
 let currentNode = this.head;
 let index = 0;
 while (index++ < position) {currentNode = currentNode.next}
 // 批改节点的 data
 currentNode.data = data
 return currentNode;
}

实现 removeAt() 办法

removeAt(position) 删除指定地位的节点。

removeAt(position) {
 // position 越界判断
 if (position < 0 || position >= this.length) return null;
 // 删除指定 position 的节点
 let currentNode = this.head;
 if (position === 0) {
  // position = 0 的状况
  this.head = this.head.next
 } else {
  // positon > 0 的状况
 let previousNode = null;
 let index = 0;
 
 while (index++ < position) {
  previousNode = currentNode;
  currentNode = currentNode.next;
 }
 previous.next = currentNode.next;
 }
 // 更新链表长度 - 1
 this.length--;
 return currentNode;
}

实现 remove() 办法

remove(data) 删除指定 data 所在的节点。

remove(data) {this.removeAt(this.indexOf(data));
}

实现 isEmpty() 办法

isEmpty() 判断链表是否为空。

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

实现 size() 办法

size() 获取链表的长度。

size() {return this.length;}

残缺实现

class LinkedList {
  // 初始链表长度为 0
  length = 0;

  // 初始 head 为 null，head 指向链表的第一个节点
  head = null;

  // 外部类（链表里的节点 Node）Node = class {
    data;
    next = null;

    constructor(data) {this.data = data;}
  };

  // ------------ 链表的常见操作 ------------ //

  // append() 往链表尾部追加数据
  append(data) {
    // 1、创立新节点
    const newNode = new this.Node(data);

    // 2、追加新节点
    if (this.length === 0) {
      // 链表长度为 0 时，即只有 head 的时候
      this.head = newNode;
    } else {
      // 链表长度大于 0 时，在最初面增加新节点
      let currentNode = this.head;

      // 当 currentNode.next 不为空时，// 循序顺次找最初一个节点，即节点的 next 为 null 时
      while (currentNode.next !== null) {currentNode = currentNode.next;}

      // 最初一个节点的 next 指向新节点
      currentNode.next = newNode;
    }

    // 3、追加完新节点后，链表长度 + 1
    this.length++;
  }

  // insert() 在指定地位（position）插入节点
  insert(position, data) {
    // position 新插入节点的地位
    // position = 0 示意新插入后是第一个节点
    // position = 1 示意新插入后是第二个节点，以此类推

    // 1、对 position 进行越界判断，不能小于 0 或大于链表长度
    if (position < 0 || position > this.length) return false;

    // 2、创立新节点
    const newNode = new this.Node(data);

    // 3、插入节点
    if (position === 0) {
      // position = 0 的状况
      // 让新节点的 next 指向 原来的第一个节点，即 head
      newNode.next = this.head;

      // head 赋值为 newNode
      this.head = newNode;
    } else {
      // 0 < position <= length 的状况

      // 初始化一些变量
      let currentNode = this.head; // 以后节点初始化为 head
      let previousNode = null; // head 的 上一节点为 null
      let index = 0; // head 的 index 为 0

      // 在 0 ~ position 之间遍历，一直地更新 currentNode 和 previousNode
      // 直到找到要插入的地位
      while (index++ < position) {
        previousNode = currentNode;
        currentNode = currentNode.next;
      }

      // 在以后节点和以后节点的上一节点之间插入新节点，即它们的扭转指向
      newNode.next = currentNode;
      previousNode.next = newNode;
    }

    // 更新链表长度
    this.length++;
    return newNode;
  }

  // getData() 获取指定地位的 data
  getData(position) {
    // 1、position 越界判断
    if (position < 0 || position >= this.length) return null;

    // 2、获取指定 position 节点的 data
    let currentNode = this.head;
    let index = 0;

    while (index++ < position) {currentNode = currentNode.next;}

    // 3、返回 data
    return currentNode.data;
  }

  // indexOf() 返回指定 data 的 index，如果没有，返回 -1。indexOf(data) {
    let currentNode = this.head;
    let index = 0;

    while (currentNode) {if (currentNode.data === data) {return index;}
      currentNode = currentNode.next;
      index++;
    }

    return -1;
  }

  // update() 批改指定地位节点的 data
  update(position, data) {
    // 波及到 position 都要进行越界判断
    // 1、position 越界判断
    if (position < 0 || position >= this.length) return false;

    // 2、痛过循环遍历，找到指定 position 的节点
    let currentNode = this.head;
    let index = 0;
    while (index++ < position) {currentNode = currentNode.next;}

    // 3、批改节点 data
    currentNode.data = data;

    return currentNode;
  }

  // removeAt() 删除指定地位的节点
  removeAt(position) {
    // 1、position 越界判断
    if (position < 0 || position >= this.length) return null;

    // 2、删除指定 position 节点
    let currentNode = this.head;
    if (position === 0) {
      // position = 0 的状况
      this.head = this.head.next;
    } else {
      // position > 0 的状况
      // 通过循环遍历，找到指定 position 的节点，赋值到 currentNode

      let previousNode = null;
      let index = 0;

      while (index++ < position) {
        previousNode = currentNode;
        currentNode = currentNode.next;
      }

      // 奇妙之处，让上一节点的 next 指向到以后的节点的 next，相当于删除了以后节点。previousNode.next = currentNode.next;
    }

    // 3、更新链表长度 -1
    this.length--;

    return currentNode;
  }

  // remove() 删除指定 data 的节点
  remove(data) {this.removeAt(this.indexOf(data));
  }

  // isEmpty() 判断链表是否为空
  isEmpty() {return this.length === 0;}

  // size() 获取链表的长度
  size() {return this.length;}

  // toString() 链表数据以字符串模式返回
  toString() {
    let currentNode = this.head;
    let result = "";

    // 遍历所有的节点，拼接为字符串，直到节点为 null
    while (currentNode) {
      result += currentNode.data + " ";
      currentNode = currentNode.next;
    }

    return result;
  }
}

https://github.com/ChickenDre…

退出移动版