javascript資料結構和算法——連結清單，雙向連結清單

一、單向連結清單

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

class linkList {
  constructor() {
    this.head = null;
    this.length = 0;
  }
  // 向連結清單中添加元素
  append(element) {
    let newEle = new Node(element)
    if (this.length === 0) {
      this.head = newEle;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newEle;
    }
    this.length++;
  }
  // 輸出字元串的方法
  toString() {
    let result = '';
    let current = this.head;
    while (current) {
      result += current.element + " ";
      current = current.next;
    }
    return result;
  }
  // 插傳入連結表算法
  insert(position, element) {
    let insertEle = new Node(element);
    if (position < 0 || position > this.length) {
      return false;
    }
    // 當插入的位置為0時
    if (position == 0) {
      insertEle.next = this.head;
      this.head = insertEle;
    } else {
      let index = 0;
      let current = this.head;
      let prov = null;
      while (index++ < position) {
        prov = current;
        current = current.next;
      }
      prov.next = insertEle;
      insertEle.next = current;
    }
    this.length++;
    return true;
  }
  // 擷取某一個位置的元素資料
  get(position) {
    if (position < 0 || position > this.length) {
      return false;
    }
    let index = 0;
    let current = this.head;
    while (index++ < position) {
      current = current.next;
    }
    return current.element;
  }
  // indexOf()用來查找
  indexOf(ele) {
    let index = 0;
    let current = this.head;
    while (current) {
      if (current.element === ele) {
        return index;
      }
      current = current.next;
      index++;
    }
    return -1;
  }
  // updata()方法來更新資料
  updata(position, newData) {
    if (position < 0 || position > this.length) {
      return false;
    }
    let current = this.head;
    let index = 0;
    while (index++ < position) {
      current = current.next;
    }
    current.element = newData;
    return true;
  }
  removeAt(position) {
    if (position < 0 && position >= this.length) {
      return false;
    } else {
      let index = 0;
      let current = this.head;
      let prov = null;
      while (index++ < position) {
        prov = current;
        current = current.next;
      }
      prov.next = current.next;
    }
    return true;
  }
  // 删除某一個元素
  remove(ele) {
    let position = this.indexOf(ele);
    this.removeAt(position);
  }
  // 判斷元素是否為空
  isEmpty(){
    return this.length == 0;
  }
  // 傳回連結清單最終的長度
  size(){
    return this.length;
  }
}
let list = new linkList();
list.append("aaa");
list.append("bbb");
list.append("ccc");
list.append('ddd');
console.log(list.toString());
console.log(list.isEmpty());
console.log(list.size());
</script>
           

二、雙向連結清單

<script>
class Node {
  constructor(element) {
    this.element = element;
    this.next = null;
    this.prov = null;
  }
}

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  // 這裡append()方法就是對其進行添加元素
  append(element) {
    let newNode = new Node(element);
    if (this.length === 0) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.prov = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
  }
  // 将連結清單轉化成字元串
  // 1、toString()
  toString() {
    let result = "";
    let current = this.head;
    while (current) {
      result += current.element + " ";
      current = current.next;
    }
    return result;
  }
  // 2、forwordString()
  forwordString() {
    let result = "";
    let current = this.tail;
    while (current) {
      result += current.element + " ";
      current = current.prov;
    }
    return result;
  }
  // 3、backWordString()
  backWordString() {
    return this.toString();
  }
  // insert(position,element)插入
  insert(position, element) {
    let insertNode = new Node(element);
    // 确定位置符合條件
    if (position < 0 && position > this.length) {
      return false;
    }
    // 判斷長度是否為0
    if (this.length === 0) {
      this.head = insertNode;
      this.tail = insertNode;
    } else {
      // 當長度不等于0
      if (position === 0) {
        insertNode.next = this.head;
        this.head.prov = insertNode;
        this.head = insertNode;
      } else if (position === this.length) {
        insertNode.prov = this.tail;
        this.tail.next = insertNode;
        this.tail = insertNode;
      } else {
        let index = 0;
        let current = this.head;
        while (index++ < position) {
          current = current.next;
        }
        insertNode.next = current;
        insertNode.prov = current.prov;
        current.prov.next = insertNode;
        current.prov = insertNode;
      }
    }
    this.length++;
    return true;
  }
  // get(position)擷取元素資料
  get(position) {
    if (position < 0 && position >= this.length) {
      return false;
    }
    // 雙向連結清單和單向連結清單之間的差別
    let index
    let current;
    if (this.length / 2 > position) {
      // 從後向前數
      index = this.length - 1;
      current = this.tail;
      while (index-- > position) {
        current = current.prov;
      }
    } else {
      // 從前向後數
      index = 0;
      current = this.head;
      while (index++ < position) {
        current = current.next;
      }
    }
    return current.element;
  }
  //  查找元素下标
  indexOf(element) {
    let index = 0;
    let current = this.head;
    while (current) {
      if (current.element === element) {
        return index;
      }
      current = current.next;
      index++;
    }
    return -1;
  }
  // 更新資料
  updata(position, element) {
    if (position < 0 && position >= this.length) {
      return false;
    }
    let index;
    let current;
    // 雙向連結清單和單向連結清單的差別
    if (this.length / 2 > position) {
      // 在前半部分
      index = 0;
      current = this.head;
      while (index++ < position) {
        current = current.next;
      }
    } else {
      // 在後半部分
      index = this.length - 1;
      current = this.tail;
      while (index-- > position) {
        current = current.prov;
      }
    }
    current.element = element;
    return true;
  }
  // removeAt(position)//删除一個元素
  removeAt(position) {
    if (position < 0 && position >= this.length) {
      return false;
    }
    let index = 0;
    let current = this.head;
    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      if (position === 0) {
        this.head = this.head.next;
        this.head.prov = null;
      } else if (position === this.length - 1) {
        current = this.tail;
        this.tail = this.tail.prov;
        this.tail.next = null;
      } else {
        while (index++ < position) {
          current = current.next;
        }
        current.prov.next = current.next;
        current.next.prov = current.prov;
      }
    }
    this.length--;
    return current.element;
  }
  // remove(ele)删除指定元素
  remove(ele){
    let place = this.indexOf(ele);
    this.removeAt(place);
    this.length--;
  }
  // 判斷連結清單是否為空
  isEmpty(){
    return this.length=== 0;
  }
  // 連結清單的長度
  size(){
    return this.length;
  }
  // 取出第一個元素
  forHead(){
    return this.head.element;
  }
  // 取出最後一個元素
  forBack(){
    return this.tail.element;
  }
}
let double = new DoublyLinkedList();
double.append("aaa");
double.append("bbb");
double.append("ccc");
double.append("ddd");
console.log(double.isEmpty());
console.log(double.size());
console.log(double.forHead());
console.log(double.forBack());
</script>