第六章鏈表-有解無憂

說在前面

鏈表

添加和洗掉操作一定要記得維護count
push的時候注意是否為插入第一個元素
指定位置插入的時候更要注意是否為插入第一個還是插入最后一個,這兩個都要做一定的特殊處理

雙向鏈表

插入元素的時候注意是否為第一次插入,如果是需要維護head,tail兩個指標,移除也是一樣
記得維護元素的prev指標,還有head的prev指標為undefined,以及tail的next的指標為undefined

說明

要存盤多個元素,陣列(或串列)可能是最常用的資料結構.然而,這種資料有一個缺點:(在大多數語言中)陣列的大小是固定的,從陣列的起點或中間插入或移除項的成本非常高,因為需要移動元素.鏈表存盤有序的資料集合,但是不同于陣列,鏈表中的元素在記憶體中并不是連續放置的.每個元素都由一個存盤元素本身的節點和一個指向下一個元素的參考(也稱指標或鏈接)組成.

鏈表與陣列的區別

相對于傳統的陣列,鏈表的一個好處在于,添加或移除元素的時候不需要移動其他元素.然而,鏈表需要使用指標,因此實作鏈表時需要額外注意.在陣列中,我們可以直接訪問任意位置的任何元素,而要訪問鏈表中間的一個元素,則需要從起點(表頭)開始迭代鏈表直到找到所需的元素.所以陣列插入和移動消耗的時間長,而鏈表查詢消耗的時間更長

鏈表

簡單圖解

鏈表的基礎方法

push(element(s)) : 向鏈表尾部添加一個(或多個)新的項
getElementAt(index) :獲取鏈表指定位置的一個元素
insert(element,index) : 在鏈表指定位置插入一個元素
removeAt(index) : 移除鏈表中指定位置的元素
remove(element) : 移除鏈表中指定的元素
indexOf(element) : 回傳當前元素在鏈表中的位置
getHead() : 回傳鏈表的頭部
clear() : 移除鏈表中的所有元素
size() : 回傳鏈表的元素個數
isEmpty: 鏈表是空的

class Node<T> {
    constructor(public element: T, public next?: Node<T>) {}
}

export type IEqualsFunction<T> = (a: T, b: T) => boolean;

function defaultEquals<T>(a: T, b: T): boolean {
    return a === b;
}

export default class LinkedList<T> {
    protected count = 0;
    protected head: Node<T> | undefined;

    constructor(protected equalsFn: IEqualsFunction<T> = defaultEquals) {
    }

    // 插入到元素的最尾處
    push(element: T): void {
        let node = new Node(element);
        if (this.head === undefined) {
            this.head = node;
        }else{
            //使用型別斷言解決下面提示錯誤問題,因為這里肯定能取到值
            let current = this.getElementAt(this.count - 1) as Node<T>;
            current.next = node;
        }
        this.count++;
    }

    getElementAt(index: number): Node<T> | undefined {
        if (index >= this.count && index < 0) {
            return undefined;
        }
        //這里拿到了第0個
        let current: (Node<T> | undefined) = this.head;
        //這里從1開始
        let i = 1;
        //回圈判斷是否存在node,并且判斷i <= index,這里要取等于,傳入的index為下標(取第3個數,傳入下標2)
        while (i <= index && current) {
            current = current.next;
            //這里要進行i++
            i++;
        }
        return current;
    }


    // 指定位置插入,一定要記得count++
    insert(element: T, index: number) {
        let node = new Node(element);
        // 頭部插入
        if (index === 0) {
            let current = this.head;
            this.head = node;
            node.next = current;
            this.count++;
            return true;
        }
        //尾部插入
        if (index === this.count) {
            this.push(element)
            return true;
        }
        //其他位置插入
        if (index > 0 && index < this.count) {
            let prev = this.getElementAt(index - 1);
            if (prev) {
                let current = prev.next;
                prev.next = node;
                node.next = current;
                this.count++;
                return true;
            }
        }
        return false;
    }

    //移除元素要count--
    removeAt(index: number): T | undefined {
        if (index >= this.count) {
            return undefined;
        }
        if (index === 0) {
            return this.removeHead();
        }

        let prev = this.getElementAt(index - 1) as Node<T>;
        let current = prev.next;
        if (current) {
            prev.next = current.next;
        } else {
            prev.next = undefined;
        }
        this.count--;
        return current && current.element;
    }

    private removeHead(): T |undefined {
        if(this.head){
            let value = https://www.cnblogs.com/wangzhaoyv/p/this.head.element;
            this.head = this.head.next;
            this.count--;
            return value;
        }
    }

    remove(element: T): T | undefined {
        // 如果鏈表沒有資料
        if (!this.head) {
            return undefined;
        }
        if (this.head.element === element) {
            return this.removeHead()
        }
        let current = this.head;
        let prev: Node = this.head;
        while (current) {
            if (current.element === element) {
                prev.next = current.next;
                this.count--;
                return element;
            }
            prev = current;
            current = current.next;
        }
        return undefined;
    }

    indexOf(element: T): number {
        let current = this.head;
        let index: number = -1;
        while (current) {
            index++;
            if (element === current.element) {
                return index;
            }
            current = current.next;
        }
        return -1;
    }

    size() {
        return this.count;
    }

    getHead() {
        return this.head;
    }

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

    clear() {
        this.head = undefined;
        this.count = 0;
    }

    toString() {
        if (this.head == null) {
            return'';
        }
        let objString = `${this.head.element}`;
        let current = this.head.next;
        for (let i = 1; i < this.size() && current != null; i++) {
            objString = `${objString},${current.element}`;
            current = current.next;
        }
        return objString;
    }
}

雙向鏈表

說明

雙向鏈表和單項鏈表的不同在于,雙向鏈表多出一個指向上一個元素的指標

簡單圖解

一個雙向鏈表的基本方法

以上鏈表的方法
getTail() : 回傳雙向鏈表的尾部

class DoublyNode<T> {
    constructor(public element:T, public next?:DoublyNode<T>,public prev?:DoublyNode<T>) {
    }
}

export default class DoublyLinkedList<T> {
    head: DoublyNode<T> | undefined;//頭部指標
    tail: DoublyNode<T> | undefined; //尾部指標
    count: number;//總個數


    constructor() {
        this.head = undefined;
        this.tail = undefined;
        this.count = 0;
    }

    /**
     * 向鏈表最后添加一個元素
     * @param element  插入的元素
     * 因為是尾部插入,所以不需要維護插入元素的next指標,但是需要維護prev指標
     */
    push(element: T) {
        //生成一個node節點
        let node = new DoublyNode(element);
        //判斷是否為第一個元素 || 判斷是否為最后一個元素
        if (!this.tail) {
            this.head = node;
            this.tail = node;
        } else {
            /**
             * 頭部插入
             let current = this.head;
             //判斷是否有下一個元素,有就回圈,這樣就可以找到最后一個元素了
             while (current.next) {
                current = current.next;
             }
             //將元素放在next元素后面
             current.next = node;
             //將node的prev指標指向current
             node.prev = current;
             //將尾部指標指向node
             this.tail = node;
             */

            //但是我這個時候明顯是有尾指標的,所以可以直接從尾部插入
            //獲取最后一個元素
            let current = this.tail;
            //將最后一個元素的next指標指向node
            current.next = node;
            //將node的prev指標指向current
            node.prev = current;
            //將tail指標指向node
            this.tail = node;
        }
        //注意這里一定要更新count
        this.count++;
    }

    /**
     * 獲取指定位置的元素
     * @param index   傳入的index為下標
     * 下標約定從0開始
     * 優化:可以根據index的值,與count的值對比,判斷從頭還是從尾開始搜索
     */
    getElementAt(index: number) {
        /**
         * 兩種情況是不需要找的
         * 1.當下標(index)大于等于總數(count)
         * 2.當下標小于0
         */
        if (index >= this.count || index < 0) {
            return undefined;
        }
        //其他情況都應該找得到元素,默認拿到第0個元素
        let current = this.head;
        /**
         * 這里用for回圈更好點,如果用while回圈可能會忘記維護這個i,畢竟我們不是找最后一個
         * 第二這里要注意我們需要找到i === index的那個元素
         * 第三我們這里回圈從i = 1開始,因為我們默認就拿到0的元素了
         *
         * 第四,當然我們把第二第三點合在一起就得到了  let i = 0; i < index && current; i++
         */
        for (let i = 1; i <= index && current; i++) {
            current = current.next;
        }
        //回傳
        return current;
    }


    /**
     * 這里指定位置插入元素
     * @param element  插入的元素
     * @param index    插入的位置
     *
     * 注意點
     * index 不能大于count,或小于0,否則顯示插入失敗(等于count,等于push)
     * index === 0 時添加到頭部,這里要特殊處理
     * index === this.count 時是push一個新元素
     */
    insert(element: T, index: number) {
        if (index > this.count || index < 0) {
            return false;
        }
        let node = new DoublyNode(element);
        if (index === 0) {
            if (this.head) {
                //取下頭
                let current = this.head;
                //node的next指標指向current
                node.next = current;
                //current的prev指標指向node
                current.prev = node;
                //再將node安裝在頭上
                this.head = node;

            } else {
                this.head = node;
                this.tail = node;
            }
            //別忘了維護count
            this.count++;
            return true;

        }
        if (index === this.count) {
            this.push(element);
            return true;
        }
        //找到當前需要替換位置的元素
        let current = this.getElementAt(index) as DoublyNode<T>;
        //找到上一個元素prevElement
        let prevElement = current.prev as DoublyNode<T>;
        //將其next指標指向node(斷開與current的聯系,并與node建立聯系)
        prevElement.next = node;
        //將current的prev指標指向node(斷開與prevElement的聯系,并與node建立聯系)
        current.prev = node;
        //node的prev指標指向prevElement
        node.prev = prevElement;
        //node的next指標指向current
        node.next = current;
        //別忘了維護count
        this.count++;
        return true;
    }


    /**
     * 移除指定下標元素
     * @param index  指定下標
     * @return T     回傳移除的元素值
     * 判斷下標
     * 如果index >= count || index < 0 回傳undifend
     * index === 0 是一種特殊情況
     * index === count - 1 一種特殊情況
     * count - 1 === index 的情況維護tail
     */
    removeAt(index: number) {
        if (index >= this.count || index < 0 || !this.head) {
            return undefined;
        }
        let current: DoublyNode<T> | undefined = undefined;
        if (index === 0) {
            current = this.head;
            this.head = current.next;
            //只有一個元素
            if (this.count === 1) {
                this.tail = undefined;
            }
        } else {
            //獲取到需要移除的元素.上面已經排除第一個元素,所以這里應該是可以拿到一個節點的
            current = this.getElementAt(index) as DoublyNode<T>;
            //因為不再第一個節點上,所以肯定能獲取到上一個元素
            let prevElement = current.prev as DoublyNode<T>;
            //獲取下一個節點,這里如果是最后一個元素,也無所謂,因為next會有一個默認值undefined
            let nextElement = current.next;
            //架空當前元素
            prevElement.next = nextElement;
            //因為可能會沒有獲取到對應的next(最后一個元素的時候),所以有就將prev指標指向prevElement,沒有就過
            if (nextElement) {
                nextElement.prev = prevElement
            }
            //當元素為最后一個的時候,移除后將tail指向prevElement
            else {
                this.tail = prevElement;
            }
        }
        //記得維護count
        this.count--;
        return current ? current.element : undefined;
    }

    remove(element: T) {

    }

    /**
     * 查找元素所在位置
     * @param element 查找的元素
     * 如果沒有找到回傳-1
     */
    indexOf(element: T): number {
        if (this.head) {
            let index = 0;
            let current: DoublyNode<T> | undefined = this.head;
            while (current) {
                //如果元素的內容等于傳入值,回傳index
                if (current.element === element) {
                    return index;
                }
                //否則將current 賦值為 next
                current = current.next;
                //并且計數表示當前元素的位置
                index++;
            }
        }
        //不滿足條件,或者回圈完所有的元素后還是沒有這個元素的資訊,就回傳-1
        return -1;
    }

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

    size() {
        return this.count;
    }

    getHead() {
        return this.head;
    }

    getTail() {
        return this.tail
    }

    clear() {
        this.head = undefined;
        this.tail = undefined;
        this.count = 0;
    }

    toString() {
        if (this.head == null) {
            return '';
        }
        let objString = `${this.head.element}`;
        let current = this.head.next;
        while (current != null) {
            objString = `${objString},${current.element}`;
            current = current.next;
        }
        return objString;
    }

    inverseToString() {
        if (this.tail == null) {
            return '';
        }
        let objString = `${this.tail.element}`;
        let previous = this.tail.prev;
        while (previous != null) {
            objString = `${objString},${previous.element}`;
            previous = previous.prev;
        }
        return objString;
    }
}

書中代碼

鏈表

type IEqualsFunction<T> = (a: T, b: T) => boolean;

function defaultEquals<T>(a: T, b: T): boolean {
  return a === b;
}

class Node<T> {
  constructor(public element: T, public next?: Node<T>) {}
}



export default class LinkedList<T> {
  protected count = 0;
  protected head: Node<T> | undefined;

  constructor(protected equalsFn: IEqualsFunction<T> = defaultEquals) {}

  push(element: T) {
    const node = new Node(element);
    let current;

    if (this.head == null) {
      // catches null && undefined
      this.head = node;
    } else {
      current = this.head;

      while (current.next != null) {
        current = current.next;
      }

      current.next = node;
    }
    this.count++;
  }

  getElementAt(index: number) {
    if (index >= 0 && index <= this.count) {
      let node = this.head;
      for (let i = 0; i < index && node != null; i++) {
        node = node.next;
      }
      return node;
    }
    return undefined;
  }

  insert(element: T, index: number) {
    if (index >= 0 && index <= this.count) {
      const node = new Node(element);

      if (index === 0) {
        const current = this.head;
        node.next = current;
        this.head = node;
      } else {
        const previous = this.getElementAt(index - 1);
        node.next = previous.next;
        previous.next = node;
      }
      this.count++;
      return true;
    }
    return false;
  }

  removeAt(index: number) {
    if (index >= 0 && index < this.count) {
      let current = this.head;

      if (index === 0) {
        this.head = current.next;
      } else {
        const previous = this.getElementAt(index - 1);
        current = previous.next;
        previous.next = current.next;
      }
      this.count--;
      return current.element;
    }
    return undefined;
  }

  remove(element: T) {
    const index = this.indexOf(element);
    return this.removeAt(index);
  }

  indexOf(element: T) {
    let current = this.head;

    for (let i = 0; i < this.size() && current != null; i++) {
      if (this.equalsFn(element, current.element)) {
        return i;
      }
      current = current.next;
    }

    return -1;
  }

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

  size() {
    return this.count;
  }

  getHead() {
    return this.head;
  }

  clear() {
    this.head = undefined;
    this.count = 0;
  }

  toString() {
    if (this.head == null) {
      return '';
    }
    let objString = `${this.head.element}`;
    let current = this.head.next;
    for (let i = 1; i < this.size() && current != null; i++) {
      objString = `${objString},${current.element}`;
      current = current.next;
    }
    return objString;
  }
}

雙向鏈表

class DoublyNode<T> extends Node<T> {
  constructor(
    public element: T,
    public next?: DoublyNode<T>,
    public prev?: DoublyNode<T>
  ) {
    super(element, next);
  }
}

type IEqualsFunction<T> = (a: T, b: T) => boolean;

function defaultEquals<T>(a: T, b: T): boolean {
  return a === b;
}

export default class DoublyLinkedList<T> extends LinkedList<T> {
  protected head: DoublyNode<T> | undefined;
  protected tail: DoublyNode<T> | undefined;

  constructor(protected equalsFn: IEqualsFunction<T> = defaultEquals) {
    super(equalsFn);
  }

  push(element: T) {
    const node = new DoublyNode(element);

    if (this.head == null) {
      this.head = node;
      this.tail = node; // NEW
    } else {
      // attach to the tail node // NEW
      this.tail.next = node;
      node.prev = this.tail;
      this.tail = node;
    }
    this.count++;
  }

  insert(element: T, index: number) {
    if (index >= 0 && index <= this.count) {
      const node = new DoublyNode(element);
      let current = this.head;

      if (index === 0) {
        if (this.head == null) {
          // NEW
          this.head = node;
          this.tail = node;
        } else {
          node.next = this.head;
          this.head.prev = node; // NEW
          this.head = node;
        }
      } else if (index === this.count) {
        // last item // NEW
        current = this.tail; // {2}
        current.next = node;
        node.prev = current;
        this.tail = node;
      } else {
        const previous = this.getElementAt(index - 1);
        current = previous.next;
        node.next = current;
        previous.next = node;

        current.prev = node; // NEW
        node.prev = previous; // NEW
      }
      this.count++;
      return true;
    }
    return false;
  }

  removeAt(index: number) {
    if (index >= 0 && index < this.count) {
      let current = this.head;

      if (index === 0) {
        this.head = this.head.next; // {1}
        // if there is only one item, then we update tail as well //NEW
        if (this.count === 1) {
          // {2}
          this.tail = undefined;
        } else {
          this.head.prev = undefined; // {3}
        }
      } else if (index === this.count - 1) {
        // last item //NEW
        current = this.tail; // {4}
        this.tail = current.prev;
        this.tail.next = undefined;
      } else {
        current = this.getElementAt(index);
        const previous = current.prev;
        // link previous with current's next - skip it to remove
        previous.next = current.next; // {6}
        current.next.prev = previous; // NEW
      }
      this.count--;
      return current.element;
    }
    return undefined;
  }

  indexOf(element: T) {
    let current = this.head;
    let index = 0;

    while (current != null) {
      if (this.equalsFn(element, current.element)) {
        return index;
      }
      index++;
      current = current.next;
    }

    return -1;
  }

  getHead() {
    return this.head;
  }

  getTail() {
    return this.tail;
  }

  clear() {
    super.clear();
    this.tail = undefined;
  }

  toString() {
    if (this.head == null) {
      return '';
    }
    let objString = `${this.head.element}`;
    let current = this.head.next;
    while (current != null) {
      objString = `${objString},${current.element}`;
      current = current.next;
    }
    return objString;
  }

  inverseToString() {
    if (this.tail == null) {
      return '';
    }
    let objString = `${this.tail.element}`;
    let previous = this.tail.prev;
    while (previous != null) {
      objString = `${objString},${previous.element}`;
      previous = previous.prev;
    }
    return objString;
  }
}

回圈鏈表

class Node<T> {
  constructor(public element: T, public next?: Node<T>) {}
}

type IEqualsFunction<T> = (a: T, b: T) => boolean;

function defaultEquals<T>(a: T, b: T): boolean {
  return a === b;
}

export default class CircularLinkedList<T> extends LinkedList<T> {
  constructor(protected equalsFn: IEqualsFunction<T> = defaultEquals) {
    super(equalsFn);
  }

  push(element: T) {
    const node = new Node(element);
    let current;

    if (this.head == null) {
      this.head = node;
    } else {
      current = this.getElementAt(this.size() - 1);
      current.next = node;
    }

    // set node.next to head - to have circular list
    node.next = this.head;

    this.count++;
  }

  insert(element: T, index: number) {
    if (index >= 0 && index <= this.count) {
      const node = new Node(element);
      let current = this.head;

      if (index === 0) {
        if (this.head == null) {
          // if no node  in list
          this.head = node;
          node.next = this.head;
        } else {
          node.next = current;
          current = this.getElementAt(this.size());
          // update last element
          this.head = node;
          current.next = this.head;
        }
      } else {
        const previous = this.getElementAt(index - 1);
        node.next = previous.next;
        previous.next = node;
      }
      this.count++;
      return true;
    }
    return false;
  }

  removeAt(index: number) {
    if (index >= 0 && index < this.count) {
      let current = this.head;

      if (index === 0) {
        if (this.size() === 1) {
          this.head = undefined;
        } else {
          const removed = this.head;
          current = this.getElementAt(this.size() - 1);
          this.head = this.head.next;
          current.next = this.head;
          current = removed;
        }
      } else {
        // no need to update last element for circular list
        const previous = this.getElementAt(index - 1);
        current = previous.next;
        previous.next = current.next;
      }
      this.count--;
      return current.element;
    }
    return undefined;
  }
}

leetcode對應訓練

轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/217532.html

標籤：JavaScript

上一篇：第五章佇列與雙端佇列

下一篇：第七章集合

第六章 鏈表

說在前面

鏈表

雙向鏈表

說明

鏈表與陣列的區別

鏈表

簡單圖解

鏈表的基礎方法

雙向鏈表

說明

簡單圖解

一個雙向鏈表的基本方法

書中代碼

鏈表

雙向鏈表

回圈鏈表

leetcode對應訓練

第六章鏈表