数据结构–双向链表

时间:2021-1-8 作者:admin

什么是双向链表

双向链表(DoublyLinkedList):也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向后一个节点和前一个节点。

单向链表和双向链表对比:

单向链表:

  • 只能从头遍历到尾或者从尾遍历到头。
  • 节点的相连是单向的,原理就是上一个节点中有下一个节点的引用。
  • 可以轻松的到达下一个节点,但是返回上一个节点比较难。

双向链表:

  • 既可以从头遍历到尾也可以从尾遍历到头。
  • 节点相连的过程是双向的,原理为本节点有下一个节点的引用,也有上一个节点的引用。

双链表的缺点:

  • 每次添加或者删除节点时,要操作 4 个引用,比较麻烦。
  • 相对于单向链表,所占内存空间大一点

双链表的结构:

  • 双向链表不仅有 head 节点存放首节点的引用,还有 tail 存放尾结点的引用。
  • 每个节点由三个部分组成:data:存放数据,next:存放下一个节点的引用,previous:存放上一个节点的引用。
  • 双向链表首节点的 previous 指向 null,尾结点的 next 指向 null。

双向链表如下图:

双向链表常用的方法

  • append(data) 向尾部添加一个节点
  • insert(position, data) 指定位置插入数据
  • getData(position) 获取指定位置的链表节点
  • indexOf(data) 查找数据对应的 index
  • removeAt(position) 删除指定位置的节点
  • update(position, data) 修改指定位置的节点
  • remove(data) 删除指定 data 所在的节点(继承单向链表)
  • isEmpty() 判断链表是否为空
  • size() 获取链表的长度
  • forwardToString() 链表数据从前往后以字符串形式返回
  • backwardString() 链表数据从后往前以字符串形式返回

ES6 实现双向链表结构

  • 双向链表内部节点类封装
/**
 * 节点类
 * data  节点的数据
 * next  存放下一个节点的引用
 * previous  存放上一个节点的引用
 * @class Node
 */
class Node {
  data;
  next = null;
  previous = null;
  constructor(data) {
    this.data = data;
  }
}
  • 双向链表类封装
class DoublyLinkedList {
  length = 0;
  // 存放头结点的引用
  head = null;
  // 存放尾结点的引用
  tail = null;
}
  • append(data) 方法实现
// append(data) 向尾部添加一个节点
  append(data) {
    // 1. 创建新的链表节点
    const newNode = new Node(data);

    // 追加元素
    if (this.length === 0) {
      // 如果链表为空的话
      this.head = newNode;
      this.tail = newNode;
    } else {
      // 追加到链表尾部
      // 巧妙的一点是不用循环找链表的尾部节点,现在 tail 中有尾节点的引用
      this.tail.next = newNode;
      newNode.previous = this.tail;
      this.tail = newNode;
    }
    // 长度增加
    this.length++;
  }
  • insert(position, data) 方法的实现
 // insert(position, data) 指定位置插入数据
  insert(position, data) {
    // 判断是否越界
    if (position < 0 || position > this.length) return false;

    // 创建新的链表节点
    const newNode = new Node(data);

    // 追加链表节点;共用一下几种情况:
    // 1. 空链表追加到头部
    // 2. 链表有数据追加到头部
    // 3. 追加到尾部
    // 4. 0----this.length 之间的追加
    if (position === 0) {
      // 追加到头部
      if (this.head === null) {
        // 链表无数据添加到头部
        this.head = newNode;
        this.tail = newNode;
      } else {
        // 链表有数据添加到头部
        newNode.next = this.head;
        this.head.previous = newNode;
        this.head = newNode;
      }
    } else if (position === this.length) {
      // 在链表尾部插入节点
      this.tail.next = newNode;
      newNode.previous = this.tail;
      this.tail = newNode;
    } else {
      // 0 --- this.length 中间插入

      // 准备变量
      let targetIndex = 0; // 代表节点位置的索引
      let currentNode = this.head;
      let previousNode = null; // 代表上一个节点

      // 循环查找节点
      while (targetIndex++ < position) {
        previousNode = currentNode;
        currentNode = currentNode.next;
      }

      // 插入
      previousNode.next = newNode;
      newNode.previous = previousNode;

      newNode.next = currentNode;
      currentNode.previous = newNode;
    }

    // 增加长度
    this.length++;
    return true;
  }
  • getData(position) 方法的实现
 // getData(position) 获取指定位置的链表节点
  getData(position = 0) {
    // 判断越界
    if (position < 0 || position >= this.length) return false;
    // 循环查找位置

    let targetIndex = 0; // 代表节点位置的索引
    let currentNode = this.head;

    while (targetIndex++ < position) {
      currentNode = currentNode.next;
    }
    // 返回
    return currentNode.data;
  }
  • indexOf(data) 方法的实现
// indexOf(data) 查找数据对应的index
  indexOf(data) {
    // 循环查找数据

    let targetIndex = 0;
    let currentNode = this.head;

    while (currentNode) {
      if (data === currentNode.data) {
        return targetIndex;
      }
      currentNode = currentNode.next;
      targetIndex++;
    }
    // 否则返回-1
    return -1;
  }
  • removeAt(position) 方法的实现
// removeAt(position) 删除指定位置的节点
  removeAt(position) {
    // 判断是否越界
    if (position < 0 || position >= this.length) return false;
    let currentNode = this.head;

    // 根据不同的情况删除
    if (position === 0) {
      // 1. 删除头部的情况
      if (this.length === 1) {
        // 如果链表只有一个节点的情况
        this.head = null;
        this.tail = null;
      } else {
        // 如果链表有多个节点
        this.head = this.head.next;
        this.head.previous = null;
      }
    } else if (position === this.length) {
      // 删除链表最后的一个节点
      this.tail.previous.next = null;
      this.tail = this.tail.previous;
    } else {
      // 0-----this.length 的情况
      let targetIndex = 0;
      let previousNode = null;

      // 循环找到positions位置
      while (targetIndex++ < position) {
        previousNode = currentNode;
        currentNode = currentNode.next;
      }

      // 删除
      previousNode.next = currentNode.next;
      currentNode.next.previous = previousNode;
    }
    // 长度递减
    this.length--;
    return currentNode.data;
  }
  • update(position, data) 方法的实现
// update(position, data) 修改指定位置的节点
  update(position, data) {
    // 判断边界
    if (position < 0 || position >= this.length) return false;

    // 循环找的位置
    let targetIndex = 0;
    let currentNode = this.head;

    while (targetIndex++ < position) {
      currentNode = currentNode.next;
    }
    currentNode.data = data;
    return currentNode.data;
  }
  • remove(data) 方法的实现
  //remove(data) 删除指定 data 所在的节点(继承单向链表)

  remove(data) {
    return this.removeAt(this.indexOf(data));
  }
  • isEmpty() 方法的实现
  // isEmpty() 判断链表是否为空
  isEmpty() {
    return this.length === 0;
  }
  • size() 方法的实现
  // size() 获取链表的长度
  size() {
    return this.length;
  }
  • forwardToString() 方法的实现
  // forwardToString() 链表数据从前往后以字符串形式返回
  forwardToString() {
    let currentNode = this.head;
    let result = "";

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

    return result;
  }
  • backwardString() 方法的实现
 // backwardString() 链表数据从后往前以字符串形式返回
  backwardString() {
    let currentNode = this.tail;
    let result = "";

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

    return result;
  }

双向链表的总体代码

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

class DoublyLinkedList {
  length = 0;
  // 存放头结点的引用
  head = null;
  // 存放尾结点的引用
  tail = null;

  // 双向链表的方法
  // append(data) 向尾部添加一个节点
  append(data) {
    // 1. 创建新的链表节点
    const newNode = new Node(data);

    // 追加元素
    if (this.length === 0) {
      // 如果链表为空的话
      this.head = newNode;
      this.tail = newNode;
    } else {
      // 追加到链表尾部
      // 巧妙的一点是不用循环找链表的尾部节点,现在 tail 中有尾节点的引用
      this.tail.next = newNode;
      newNode.previous = this.tail;
      this.tail = newNode;
    }
    // 长度增加
    this.length++;
  }

  // insert(position, data) 指定位置插入数据
  insert(position, data) {
    // 判断是否越界
    if (position < 0 || position > this.length) return false;

    // 创建新的链表节点
    const newNode = new Node(data);

    // 追加链表节点;共用一下几种情况:
    // 1. 空链表追加到头部
    // 2. 链表有数据追加到头部
    // 3. 追加到尾部
    // 4. 0----this.length 之间的追加
    if (position === 0) {
      // 追加到头部
      if (this.head === null) {
        // 链表无数据添加到头部
        this.head = newNode;
        this.tail = newNode;
      } else {
        // 链表有数据添加到头部
        newNode.next = this.head;
        this.head.previous = newNode;
        this.head = newNode;
      }
    } else if (position === this.length) {
      // 在链表尾部插入节点
      this.tail.next = newNode;
      newNode.previous = this.tail;
      this.tail = newNode;
    } else {
      // 0 --- this.length 中间插入

      // 准备变量
      let targetIndex = 0; // 代表节点位置的索引
      let currentNode = this.head;
      let previousNode = null; // 代表上一个节点

      // 循环查找节点
      while (targetIndex++ < position) {
        previousNode = currentNode;
        currentNode = currentNode.next;
      }

      // 插入
      previousNode.next = newNode;
      newNode.previous = previousNode;

      newNode.next = currentNode;
      currentNode.previous = newNode;
    }

    // 增加长度
    this.length++;
    return true;
  }

  // getData(position) 获取指定位置的链表节点
  getData(position = 0) {
    // 判断越界
    if (position < 0 || position >= this.length) return false;
    // 循环查找位置

    let targetIndex = 0; // 代表节点位置的索引
    let currentNode = this.head;

    while (targetIndex++ < position) {
      currentNode = currentNode.next;
    }
    // 返回
    return currentNode.data;
  }

  // indexOf(data) 查找数据对应的index
  indexOf(data) {
    // 循环查找数据

    let targetIndex = 0;
    let currentNode = this.head;

    while (currentNode) {
      if (data === currentNode.data) {
        return targetIndex;
      }
      currentNode = currentNode.next;
      targetIndex++;
    }
    // 否则返回-1
    return -1;
  }

  // removeAt(position) 删除指定位置的节点
  removeAt(position) {
    // 判断是否越界
    if (position < 0 || position >= this.length) return false;
    let currentNode = this.head;

    // 根据不同的情况删除
    if (position === 0) {
      // 1. 删除头部的情况
      if (this.length === 1) {
        // 如果链表只有一个节点的情况
        this.head = null;
        this.tail = null;
      } else {
        // 如果链表有多个节点
        this.head = this.head.next;
        this.head.previous = null;
      }
    } else if (position === this.length) {
      // 删除链表最后的一个节点
      this.tail.previous.next = null;
      this.tail = this.tail.previous;
    } else {
      // 0-----this.length 的情况
      let targetIndex = 0;
      let previousNode = null;

      // 循环找到positions位置
      while (targetIndex++ < position) {
        previousNode = currentNode;
        currentNode = currentNode.next;
      }

      // 删除
      previousNode.next = currentNode.next;
      currentNode.next.previous = previousNode;
    }
    // 长度递减
    this.length--;
    return currentNode.data;
  }

  // update(position, data) 修改指定位置的节点
  update(position, data) {
    // 判断边界
    if (position < 0 || position >= this.length) return false;

    // 循环找的位置
    let targetIndex = 0;
    let currentNode = this.head;

    while (targetIndex++ < position) {
      currentNode = currentNode.next;
    }
    currentNode.data = data;
    return currentNode.data;
  }

  //remove(data) 删除指定 data 所在的节点(继承单向链表)

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

  // isEmpty() 判断链表是否为空
  isEmpty() {
    return this.length === 0;
  }
  // size() 获取链表的长度
  size() {
    return this.length;
  }
  // forwardToString() 链表数据从前往后以字符串形式返回
  forwardToString() {
    let currentNode = this.head;
    let result = "";

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

    return result;
  }

  // backwardString() 链表数据从后往前以字符串形式返回
  backwardString() {
    let currentNode = this.tail;
    let result = "";

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

    return result;
  }
}

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。