02-链表

链表

动态数据结构，不需要处理固定容量问题，但是丧失了随机访问的能力
将数据存储在一个单独的节点中（即一个对象中），该节点包括至少俩部分内容（即对象的属性）
- 存储的数据
- 指向下一个节点的指针（最后一个节点指向null）
链表没有索引的概念，因为这些数据节点在内存中是分散的，由于链表没有索引的概念，为了找到指定位置的元素，只能设置了一个头指针（永远指向链表头部的指针），也就是说现在只能获得第一个节点，这就够了，因为第一个节点的next就是第二个节点，第二个节点的next就是第三个节点，依次类推，所以每次查找到对应的节点时都需要从头节点开始遍历每个节点的next

普通的单向链表

/**
 * @ClassName: LinkedList
 * @Description: 不带有虚拟头节点的自定义单向链表
 */
public class LinkedList<E> {
  private class Node { //私有的内部类，不希望暴漏给外部使用，使用该类创建节点对象并进行链表的组装
    private E data; //存储节点数据
    private Node next;  //存储下一个节点

    /**
     * @MethodName: Node
     * @Description: 创建节点对象，指定数据和下一个节点
     * @Param data: 数据
     * @Param next: 下一个节点
     */
    public Node(E data, Node next) {
      this.data = data;
      this.next = next;
    }

    /**
     * @MethodName: Node
     * @Description: 创建节点对象，只指定数据，下一个节点为null，即最后一个节点
     * @Param data:
     */
    public Node(E data) {
      this(data, null);
    }

    /**
     * @MethodName: Node
     * @Description: 创建节点对象，此时数据和下一个节点都是null，即最后一个节点并且数据也是null
     */
    public Node() {
      this(null, null);
    }

    @Override
    public String toString() {
      return this.data.toString(); //只打印数据，屏蔽掉节点指针
    }
  }

  private Node head;  //头节点指针，永远指着头
  private int size; //链表长度

  /**
   * @MethodName: LinkedList
   * @Description: 创建一个空链表
   */
  public LinkedList() {
    this.head = null;
    this.size = 0;
  }

  /**
   * @MethodName: getSize
   * @Description: 获取链表中元素的个数
   * @Return int
   */
  public int getSize() {
    return size;
  }

  /**
   * @MethodName: isEmpty
   * @Description: 判断链表是否为空
   * @Return boolean
   */
  public boolean isEmpty() {
    return size == 0;
  }

  /**
   * @MethodName: add
   * @Description: 向指定的位置插入指定的元素
   * 是另一种实现方式，统一了向每个位置添加时的操作，减少向链表头部添加的判断
   * @Param index:
   * @Param element:
   * @Return void
   */
  public void add(int index, E element) {
    if (this.size < 0 || index > this.size) { //若传入位置不合法则抛出异常
      throw new IllegalArgumentException("Add failed, Index is illegal");
    }
    /**
     * 分析：
     *     为指定位置添加指定元素需要先找到指定位置的前一个节点，并改变前一个节点的next
     *     指向要添加的节点，添加节点的next指向前一个节点原来的next
     *注意事项：
     *     改变next指针时需要注意修改的顺序，应该先将前一个节点原来节点的next赋给要添加
     *     节点的next后，再将前一个节点的next指向要添加的元素，否则会导致添加节点自己指
     *     向自己的情况
     */
    if (index == 0) {
      //对于向链表头部添加元素时，由于没有前一个节点，所以需要单独处理
      this.head = new Node(element, this.head); //创建新节点，为头节点
    } else {
      Node prev = this.head; //用来存储上一个节点的指针
      for (int i = 0; i < index - 1; i++) {
        //找前一个节点，需要遍历到指定位置的前一个,所以需要减1
        prev = prev.next; //指针后移
      }
      prev.next = new Node(element, prev.next); //添加节点
    }
    this.size++;  //添加后链表大小加1
  }

  /**
   * @MethodName: get
   * @Description: 用户根据索引获取元素内容
   * @Param index: 用户指定的索引
   * @Return E
   */
  public E get(int index) {
    if (this.size < 0 || index > this.size) { //若传入位置不合法则抛出异常
      throw new IllegalArgumentException("Get failed, Index is illegal");
    }
    Node cur = head; //存储当前节点的指针，从头节点开始遍历
    for (int i = 0; i < index; i++) {
      cur = cur.next; //当前节点指针后移
    }
    return cur.data;  //返回指定节点的内容
  }

  /**
   * @MethodName: set
   * @Description: 用户根据索引修改元素内容
   * @Param index: 用户指定的索引
   * @Param element: 用户指定要修改成的元素
   * @Return void
   */
  public void set(int index, E element) {
    if (this.size < 0 || index > this.size) { //若传入位置不合法则抛出异常
      throw new IllegalArgumentException("Set failed, Index is illegal");
    }
    Node cur = head; //存储当前节点的指针，从第头节点开始遍历
    for (int i = 0; i < index; i++) {
      cur = cur.next; //当前节点指针后移
    }
    cur.data = element; //修改指定节点内容
  }

  /**
   * @MethodName: contains
   * @Description: 根据用户指定的元素判断链表中是否包含该元素
   * @Param element: 用户指定的元素
   * @Return boolean
   */
  public boolean contains(E element) {
    Node cur = head; //存储当前节点的指针，从头节点开始遍历
    while (cur != null) { //若当前节点已经为null，说明当前节点指针已经指到了末尾
      if (element.equals(cur.data)) { //若与用户指定元素相同
        return true;  //返回true
      }
      cur = cur.next; //当前节点指针后移
    }
    return false; //若遍历完整个链表都没有相同的，就返回false
  }

  /**
   * @MethodName: remove
   * @Description: 根据用户指定索引删除节点
   * @Param index: 用户指定索引
   * @Return E
   */
  public E remove(int index) {
    if (this.size < 0 || index > this.size) { //若传入位置不合法则抛出异常
      throw new IllegalArgumentException("Remove failed, Index is illegal");
    }
    /**
     * 分析：
     *     为指定位置删除指定元素需要先找到指定位置的前一个节点，并改变前一个节点的next
     *     指向要被删除节点所指向的节点（即跳过要被删除节点）
     */
    Node delNode = null;  //要删除的节点
    if (index == 0) {
      //对于向链表头部删除元素时，由于没有前一个节点，所以需要单独处理
      delNode = this.head; //要删除的节点是头节点
      this.head = this.head.next; //头节点后移
    } else {
      Node prev = this.head; //用来存储上一个节点的指针
      for (int i = 0; i < index - 1; i++) {
        //找前一个节点，需要遍历到指定位置的前一个，所以需要减1
        prev = prev.next; //指针后移
      }
      delNode = prev.next; //要删除的节点是前一个节点的后面的一个节点
      prev.next = delNode.next; //将前一个节点的next指向要删除节点next所指向的节点，即跳过
    }
    delNode.next = null;  //将要删除节点的指向置为空，会与链表完全脱离，垃圾回收机制会快速回收
    this.size--;  //删除后需要将链表元素个数减1
    return delNode.data;  //返回删除的节点
  }

  /**
   * @MethodName: removeElement
   * @Description: 删除链表中指定元素，仅限第一个
   * @Param element: 要删除的元素
   * @Return void
   */
  public void removeElement(E element) {
    if (element.equals(this.head.data)) { //若头节点就是要删除的节点
      this.remove(0); //删除头节点
      return; //结束执行
    }
    Node perv = this.head; //用来存储上一个节点的指针，从第二个节点开始遍历
    while (perv.next != null) { //若上一个节点的下一个节点，也就是当前节点，不为空说明没有遍历到底
      if (element.equals(perv.next.data)) { //若当前节点是用户要删除的节点，就不再让指针后移
        break;
      }
      perv = perv.next; //指针后移
    }
    if (perv.next != null) {  //若当前指针指向有元素，则是要删除元素
      // 否则就是遍历到末尾也没有找到要删除元素，即删除元素不存在，不用删除
      Node delNode = perv.next; //要删除的节点
      perv.next = delNode.next;  //将前一个节点的next指向要删除节点next所指向的节点，即跳过
      delNode.next = null;   //将要删除节点的指向置为空，会与链表完全脱离，垃圾回收机制会快速回收
      this.size--;  //删除后需要将链表元素个数减1
    }
  }
  
  @Override
  public String toString() {
    StringBuilder sb = new StringBuilder();
    Node cur = this.head; //存储当前节点的指针，从第头节点开始遍历
    while (cur != null) { //若当前节点已经为null，说明当前节点指针已经指到了末尾
      sb.append(cur.data + "-> ");
      cur = cur.next; //当前节点指针后移
    }
    return "LinkedList{" +
        "linked=[" + sb +
        "]}";
  }
}

带有虚拟头的单向链表

对于向链表头部添加元素时，由于没有前一个节点，所以为了节点操作的逻辑统一，就在链表创建时，就创建一个虚拟节点（空的头节点），该节点对用户屏蔽，这时用户添加的节点就至少是第二个节点了，就算用户要向链表头插入元素，头节点就有前一个节点了，因为用户看到的头节点其实是第二个节点

/**
 * @ClassName: LinkedList
 * @Description: 带有虚拟头节点的自定义单向链表，仅仅是将链表头的操作和其他操作统一
 */
public class LinkedList<E> {
  private class Node { //私有的内部类，不希望暴漏给外部使用，使用该类创建节点对象并进行链表的组装
    private E data; //存储节点数据
    private Node next;  //存储下一个节点

    /**
     * @MethodName: Node
     * @Description: 创建节点对象，指定数据和下一个节点
     * @Param data: 数据
     * @Param next: 下一个节点
     */
    public Node(E data, Node next) {
      this.data = data;
      this.next = next;
    }

    /**
     * @MethodName: Node
     * @Description: 创建节点对象，只指定数据，下一个节点为null，即最后一个节点
     * @Param data:
     */
    public Node(E data) {
      this(data, null);
    }

    /**
     * @MethodName: Node
     * @Description: 创建节点对象，此时数据和下一个节点都是null，即最后一个节点并且数据也是null
     */
    public Node() {
      this(null, null);
    }

    @Override
    public String toString() {
      return this.data.toString(); //只打印数据，屏蔽掉节点指针
    }
  }

  private Node dummyHead;  //头节点指针，永远指着头（虚拟头）
  private int size; //链表长度

  /**
   * @MethodName: LinkedList
   * @Description: 创建一个空链表
   */
  public LinkedList() {
    this.dummyHead = new Node(); //创建链表时创建一个虚拟头节点
    this.size = 0;
  }

  /**
   * @MethodName: getSize
   * @Description: 获取链表中元素的个数
   * @Return int
   */
  public int getSize() {
    return this.size;
  }

  /**
   * @MethodName: isEmpty
   * @Description: 判断链表是否为空
   * @Return boolean
   */
  public boolean isEmpty() {
    return this.size == 0;
  }

  /**
   * @MethodName: add
   * @Description: 向指定的位置插入指定的元素
   * 是另一种实现方式，统一了向每个位置添加时的操作，减少向链表头部添加的判断
   * @Param index:
   * @Param element:
   * @Return void
   */
  public void add(int index, E element) {
    if (this.size < 0 || index > this.size) { //若传入位置不合法则抛出异常
      throw new IllegalArgumentException("Add failed, Index is illegal");
    }
    Node prev = this.dummyHead; //用来存储上一个节点的指针
    for (int i = 0; i < index; i++) {
      //找前一个节点，需要遍历到指定位置的前一个，但是现在多了一个虚拟节点，所以无需减1
      prev = prev.next; //指针后移
    }
    prev.next = new Node(element, prev.next); //添加节点
    this.size++;  //添加后链表大小加1
  }

  /**
   * @MethodName: get
   * @Description: 用户根据索引获取元素内容
   * @Param index: 用户指定的索引
   * @Return E
   */
  public E get(int index) {
    if (this.size < 0 || index > this.size) { //若传入位置不合法则抛出异常
      throw new IllegalArgumentException("Get failed, Index is illegal");
    }
    Node cur = this.dummyHead.next; //存储当前节点的指针，从第二个节点开始遍历，跳过虚拟头节点
    for (int i = 0; i < index; i++) {
      cur = cur.next; //当前节点指针后移
    }
    return cur.data;  //返回指定节点的内容
  }

  /**
   * @MethodName: set
   * @Description: 用户根据索引修改元素内容
   * @Param index: 用户指定的索引
   * @Param element: 用户指定要修改成的元素
   * @Return void
   */
  public void set(int index, E element) {
    if (this.size < 0 || index > this.size) { //若传入位置不合法则抛出异常
      throw new IllegalArgumentException("Set failed, Index is illegal");
    }
    Node cur = this.dummyHead.next; //存储当前节点的指针，从第二个节点开始遍历，跳过虚拟头节点
    for (int i = 0; i < index; i++) {
      cur = cur.next; //当前节点指针后移
    }
    cur.data = element; //修改指定节点内容
  }

  /**
   * @MethodName: contains
   * @Description: 根据用户指定的元素判断链表中是否包含该元素
   * @Param element: 用户指定的元素
   * @Return boolean
   */
  public boolean contains(E element) {
    Node cur = this.dummyHead.next; //存储当前节点的指针，从第二个节点开始遍历，跳过虚拟头节点
    while (cur != null) { //若当前节点已经为null，说明当前节点指针已经指到了末尾
      if (element.equals(cur.data)) { //若与用户指定元素相同
        return true;  //返回true
      }
      cur = cur.next; //当前节点指针后移
    }
    return false; //若遍历完整个链表都没有相同的，就返回false
  }

  /**
   * @MethodName: remove
   * @Description: 根据用户指定索引删除节点
   * @Param index: 用户指定索引
   * @Return E
   */
  public E remove(int index) {
    if (this.size < 0 || index > this.size) { //若传入位置不合法则抛出异常
      throw new IllegalArgumentException("Remove failed, Index is illegal");
    }
    Node prev = this.dummyHead; //用来存储上一个节点的指针
    for (int i = 0; i < index; i++) {
      //找前一个节点，需要遍历到指定位置的前一个，但是现在多了一个虚拟节点，所以无需减1
      prev = prev.next; //指针后移
    }
    Node delNode = prev.next; //要删除的节点
    prev.next = delNode.next; //将前一个节点的next指向要删除节点next所指向的节点，即跳过
    delNode.next = null;  //将要删除节点的指向置为空，会与链表完全脱离，垃圾回收机制会快速回收
    this.size--;  //删除后需要将链表元素个数减1
    return delNode.data;  //返回删除的节点
  }
  
  /**
   * @MethodName: removeElement
   * @Description: 删除链表中指定元素，仅限第一个
   * @Param element: 要删除的元素
   * @Return void
   */
  public void removeElement(E element) {
    Node perv = this.dummyHead; //用来存储上一个节点的指针
    while (perv.next != null) { //若上一个节点的下一个节点，也就是当前节点，不为空说明没有遍历到底
      if (element.equals(perv.next.data)) { //若当前节点是用户要删除的节点，就不再让指针后移
        break;
      }
      perv = perv.next; //指针后移
    }
    if (perv.next != null) {  //若当前指针指向有元素，则是要删除元素
      // 否则就是遍历到末尾也没有找到要删除元素，即删除元素不存在，不用删除
      Node delNode = perv.next; //要删除的节点
      perv.next = delNode.next;  //将前一个节点的next指向要删除节点next所指向的节点，即跳过
      delNode.next = null;   //将要删除节点的指向置为空，会与链表完全脱离，垃圾回收机制会快速回收
      this.size--;  //删除后需要将链表元素个数减1
    }
  }
  
  @Override
  public String toString() {
    StringBuilder sb = new StringBuilder();
    Node cur = this.dummyHead.next; //存储当前节点的指针，从第二个节点开始遍历，跳过虚拟头节点
    while (cur != null) { //若当前节点已经为null，说明当前节点指针已经指到了末尾
      sb.append(cur.data + "-> ");
      cur = cur.next; //当前节点指针后移
    }
    return "LinkedList{" +
        "linked=[" + sb +
        "]}";
  }
}