数据结构 -- 单向链表 & 双向链表

前端 algorithm

发布日期: 2022-07-01

# 优势

存储多个元素链表
不同于数组链表中的数据 不必是连续的空间
每个元素有一个 存储元素本身的节点 和 指向下一个元素的引用 组成

优点
1. 内存动态管理
2. 不必创建是就确认链表的大小可以无线延伸下去
3. 插入和删除数据事件复杂度达到 (0,1), 相对数组效率高很多
缺点
1. 链表访问任意位置的元素都需要 从头开始访问 (无法跳过第一个元素访问任何一个元素)
2. 无法直接下标访问元素需要从头开始直到找到对应元素

列表类似火车头：每一个火车头都有链接下一个火车头的节点节点上有 data

# 列表的方法

append (element) 向列表尾部添加一个新的项
insetr (position, element) 向列表的特定位置插入一个新的项
get (position) 获取对应位置的元素
indexOf (element) 返回元素在列表中的索引。如果列表中没有该元素则返回 - 1
update (position, element) 修改某个位置的元素
removeAt (position) 从列表特定的位置移除一项
remove (element) 从列表中移除一项
isEmpty () 如果列表中不包含任何元素，返回 true, 链表的长度大于 0 则返回 false
size () 返回列表包含元素的个数，与数组的 length 类似

# 单向链表


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

class LinkedList {
  head: any;
  length: number;
  constructor() {
    this.head = null;
    this.length = 0;
  }
  // 1. append(element) 向列表尾部添加一个新的项
  append(element: any) {
    const newNode = new Node(element);
    if (!this.head) {
      // 头没有值
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
    this.length++;
    return true;
  }
  // 2. insetr(position, element) 向列表的特定位置插入一个新的项
  insetr(position: number, element: any) {
    // 2.1 是否越界
    if (position < 0 || position > this.length) return false;
    // 2.2 创建新节点
    const newNode = new Node(element);
    // 2.3 插入元素
    if (position === 0) {
      newNode.next = this.head;
      this.head = newNode;
    } else {
      let index = 0;
      let current = this.head;
      let previous: any = null;
      while (index++ < position) {
        previous = current; // 前一个node
        current = current.next; // 当前node
      }
      previous.next = newNode;
      newNode.next = current;
    }
    this.length++;
    return true;
  }
  // 3. get(position) 获取对应位置的元素
  get(position: number) {
    if (position < 0 || position > this.length - 1) return null;
    let index = 0;
    let current = this.head;
    while (index++ < position) {
      current = current.next;
    }
    return current;
  }
  // 4. indexOf(element) 返回元素在列表中的索引.如果列表中没有该元素则返回-1
  indexOf(element: any) {
    // 获取第一个
    let current = this.head;
    let index = 0;
    // 开始循环
    while (current) {
      if (current.element === element) {
        return index;
      }
      index++;
      current = current.next;
    }
    return -1;
  }
  // 5. removeAt(position) 从列表特定的位置移除一项
  removeAt(position: number) {
    if (position < 0 || position > this.length - 1) return null;
    let current = this.head;
    let previous: any = null;
    let index = 0;
    if (position === 0) {
      this.head = current.next;
    } else {
      while (index++ < position) {
        previous = current;
        current = current.next;
      }
      previous.next = current.next;
    }
    this.length--;
    return current.element;
  }
  // 6. update(position, element) 修改某个位置的元素
  update(position: number, element: any) {
    const result = this.removeAt(position);
    this.insetr(position, element);
    return result;
    // if (position < 0 || position > this.length - 1) return null;
    // let current = this.head;
    // let index = 0;
    // while (index++ < position) {
    //   current = current.next;
    // }
    // current.element = element;
    // return true;
  }

  // 7. remove(element) 从列表中移除一项
  remove(element: any) {
    const index = this.indexOf(element);
    if (index === -1) return;
    return this.removeAt(index);
  }
  // 8. isEmpty() 如果列表中不包含任何元素,返回true,链表的长度大于0则返回false
  isEmpty() {
    return this.length === 0 ? true : false;
  }
  // 9. size() 返回列表包含元素的个数, 与数组的length类似
  size() {
    return this.length;
  }
}

export { LinkedList, Node };

# 双向链表


import { LinkedList, Node } from "./linked_list";
class DoublyNode extends Node {
  prev: any;
  constructor(element: any) {
    super(element);
    this.prev = null;
  }
}
export class DoubleLinkedList extends LinkedList {
  tail: any;
  constructor() {
    super();
    this.tail = null;
  }
  // 1. append(element) 向列表尾部添加一个新的项
  append(element: any) {
    const newNode = new DoublyNode(element);
    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    this.length++;
    return true;
  }
  insetr(position: number, element: any) {
    if (position < 0 || position > this.length) return false;
    const newNode = new DoublyNode(element);
    if (position === 0) {
      if (this.head === null) {
        this.head = newNode;
        this.tail = newNode;
      } else {
        newNode.next = this.head;
        this.head.prev = newNode;
        this.head = newNode;
      }
    } else if (this.length - 1 === position) {
      newNode.prev = this.head;
      this.head.next = newNode;
      this.tail = newNode;
    } else {
      let index = 0;
      let current = this.head;
      let prev = null;
      while (index++ < position) {
        prev = current;
        current = current.next;
      }
      prev.next = newNode;
      newNode.prev = prev;
      newNode.next = current;
      current.prev = newNode;
    }
    this.length++;
    return true;
  }
  // 5. removeAt(position) 从列表特定的位置移除一项
  removeAt(position: number) {
    if (position < 0 || position > this.length - 1) return null;
    let current = this.head;

    if (position === 0) {
      if (this.length === 1) {
        this.head = null;
        this.tail = null;
      } else {
        this.head = current.next;
        this.head.prev = null;
      }
    } else if (position === this.length - 1) {
      this.tail.prev.next = null;
      this.tail = this.tail.prev;
    } else {
      let previous: any = null;
      let index = 0;
      while (index++ < position) {
        previous = current;
        current = current.next;
      }
      previous.next = current.next;
      current.next.prev = previous;
    }
    this.length--;
    return current;
  }
}

# 程序的测试

import { DoubleLinkedList } from "./doubly_linked_list";

const linkedList = new DoubleLinkedList();

linkedList.append("aaa");
linkedList.append("bbb");
linkedList.append("ccc");
linkedList.append("ddd");

console.log(linkedList);

linkedList.insetr(1, "abc");
linkedList.insetr(3, "cba");
linkedList.insetr(0, "npc");

console.log(linkedList);

console.log(linkedList.get(3));
console.log(linkedList.indexOf("cba"));

console.log(linkedList.removeAt(1));
console.log(linkedList.removeAt(3));

console.log(linkedList);

console.log(linkedList.update(1, "123"));
console.log(linkedList.update(2, "456"));
console.log(linkedList);

console.log(linkedList.remove("123"));
console.log(linkedList.remove("456"));
console.log(linkedList);

console.log(linkedList.isEmpty());
console.log(linkedList.size());