第六章 链表

自我测试

本篇文章的测试用例及调试方法见前言

说在前面

链表

• 添加和删除操作一定要记得维护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 = 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<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;//总个数

    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对应训练