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 +
        "]}";
  }
}