第六章鏈表

頭號碼甲 2021-09-06

展開全文

自我測試

本篇文章的測試用例及調(diào)試方法見前言

說在前面

鏈表

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

雙向鏈表

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

說明

要存儲多個元素,數(shù)組(或列表)可能是最常用的數(shù)據(jù)結(jié)構(gòu).然而,這種數(shù)據(jù)有一個缺點:(在大多數(shù)語言中)數(shù)組的大小是固定的,從數(shù)組的起點或中間插入或移除項的成本非常高,因為需要移動元素.鏈表存儲有序的數(shù)據(jù)集合,但是不同于數(shù)組,鏈表中的元素在內(nèi)存中并不是連續(xù)放置的.每個元素都由一個存儲元素本身的節(jié)點和一個指向下一個元素的引用(也稱指針或鏈接)組成.

鏈表與數(shù)組的區(qū)別

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

鏈表

簡單圖解

鏈表的基礎(chǔ)方法

push(element(s)) : 向鏈表尾部添加一個(或多個)新的項
getElementAt(index) :獲取鏈表指定位置的一個元素
insert(element,index) : 在鏈表指定位置插入一個元素
removeAt(index) : 移除鏈表中指定位置的元素
remove(element) : 移除鏈表中指定的元素
indexOf(element) : 返回當(dāng)前元素在鏈表中的位置
getHead() : 返回鏈表的頭部
clear() : 移除鏈表中的所有元素
size() : 返回鏈表的元素個數(shù)
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;
        //循環(huán)判斷是否存在node,并且判斷i <= index,這里要取等于,傳入的index為下標(取第3個數(shù),傳入下標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 = this.head.element;
            this.head = this.head.next;
            this.count--;
            return value;
        }
    }

    remove(element: T): T | undefined {
        // 如果鏈表沒有數(shù)據(jù)
        if (!this.head) {
            return undefined;
        }
        if (this.head.element === element) {
            return this.removeHead()
        }
        let current = this.head;
        let prev: Node<T> = 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;//總個數(shù)


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

    /**
     * 向鏈表最后添加一個元素
     * @param element  插入的元素
     * 因為是尾部插入,所以不需要維護插入元素的next指針,但是需要維護prev指針
     */
    push(element: T) {
        //生成一個node節(jié)點
        let node = new DoublyNode(element);
        //判斷是否為第一個元素 || 判斷是否為最后一個元素
        if (!this.tail) {
            this.head = node;
            this.tail = node;
        } else {
            /**
             * 頭部插入
             let current = this.head;
             //判斷是否有下一個元素,有就循環(huán),這樣就可以找到最后一個元素了
             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開始
     * 優(yōu)化:可以根據(jù)index的值,與count的值對比,判斷從頭還是從尾開始搜索
     */
    getElementAt(index: number) {
        /**
         * 兩種情況是不需要找的
         * 1.當(dāng)下標(index)大于等于總數(shù)(count)
         * 2.當(dāng)下標小于0
         */
        if (index >= this.count || index < 0) {
            return undefined;
        }
        //其他情況都應(yīng)該找得到元素,默認拿到第0個元素
        let current = this.head;
        /**
         * 這里用for循環(huán)更好點,如果用while循環(huán)可能會忘記維護這個i,畢竟我們不是找最后一個
         * 第二這里要注意我們需要找到i === index的那個元素
         * 第三我們這里循環(huán)從i = 1開始,因為我們默認就拿到0的元素了
         *
         * 第四,當(dāng)然我們把第二第三點合在一起就得到了  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;
        }
        //找到當(dāng)前需要替換位置的元素
        let current = this.getElementAt(index) as DoublyNode<T>;
        //找到上一個元素prevElement
        let prevElement = current.prev as DoublyNode<T>;
        //將其next指針指向node(斷開與current的聯(lián)系,并與node建立聯(lián)系)
        prevElement.next = node;
        //將current的prev指針指向node(斷開與prevElement的聯(lián)系,并與node建立聯(lián)系)
        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 {
            //獲取到需要移除的元素.上面已經(jīng)排除第一個元素,所以這里應(yīng)該是可以拿到一個節(jié)點的
            current = this.getElementAt(index) as DoublyNode<T>;
            //因為不再第一個節(jié)點上,所以肯定能獲取到上一個元素
            let prevElement = current.prev as DoublyNode<T>;
            //獲取下一個節(jié)點,這里如果是最后一個元素,也無所謂,因為next會有一個默認值undefined
            let nextElement = current.next;
            //架空當(dāng)前元素
            prevElement.next = nextElement;
            //因為可能會沒有獲取到對應(yīng)的next(最后一個元素的時候),所以有就將prev指針指向prevElement,沒有就過
            if (nextElement) {
                nextElement.prev = prevElement
            }
            //當(dāng)元素為最后一個的時候,移除后將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) {
                //如果元素的內(nèi)容等于傳入值,返回index
                if (current.element === element) {
                    return index;
                }
                //否則將current 賦值為 next
                current = current.next;
                //并且計數(shù)表示當(dāng)前元素的位置
                index++;
            }
        }
        //不滿足條件,或者循環(huán)完所有的元素后還是沒有這個元素的信息,就返回-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;
  }
}

循環(huán)鏈表

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;
  }
}