关于java:数据结构单链表-循环链表-双向循环链表-双链表

单链表

如果是null，就阐明前面没有节点了，如果不是null就阐明前面要连贯节点

每个节点蕴含2局部，数据域，和一个指向下一个节点援用的指针next
data域–寄存结点值的数据域
next域–寄存结点的间接后继的地址的指针域（链域）
链表通过每个结点的链域将线性表的n个结点按其逻辑程序链接在一起的，每个结点只有一个链域的链表称为单链表（Single Linked List）。
单链表

显示所有节点信息

• 头部插入节点
• 如果链表没有头结点，新结点间接成为头结点；否则新结点的next间接指向以后头结点，并让新结点成为新的头结点。
  

/**
* 增加结点至链表头部
*
* @param value
*/
public void addHeadNode(T value) {
   Node newNode = new Node(value);
   //头结点不存在，新结点成为头结点
   if (head == null) {
       head = newNode;
       return;
   }
   //新结点next间接指向以后头结点
   newNode.next = head;
   //新结点成为新的头结点
   head = newNode;
}

• 尾部插入节点
• 如果链表没有头结点，新结点间接成为头结点；否则须要先找到链表以后的尾结点，并将新结点插入到链表尾部。
  

/**
* 增加结点至链表尾部
*
* @param value
*/
public void addTailNode(T value) {
   Node newNode = new Node(value);
   //头结点不存在，新结点成为头结点
   if (head == null) {
       head = newNode;
       return;
   }
   //找到最初一个结点
   Node last = head;
   while (last.next != null) {
       last = last.next;
   }
   //新结点插入到链表尾部
   last.next = newNode;
}

• 指定地位插入节点
• 先判断插入地位为头尾两端的状况，即index == 0插入到头部，index == size()插入到尾部；如果插入地位不是头尾两端，则先找出以后index地位的结点cur以及前一个结点 pre，而后cur成为新结点的下一个结点，新结点成为pre的后一个结点，这样就胜利插入到index地位。
  

/**
 * 结点插入至指定地位
 *
 * @param value 结点数据
 * @param index 插入地位
 */
public void addNodeAtIndex(T value, int index) {
    if (index < 0 || index > size()) { //留神index是能够等于size()的
        throw new IndexOutOfBoundsException("IndexOutOfBoundsException");
    }
    if (index == 0) {  //插入到头部
        addHeadNode(value);//后面定义的办法
    } else if (index == size()) {  //插入到尾部
        addTailNode(value);//后面定义的办法
    } else {  //插到某个两头地位
        Node newNode = new Node(value);
        int position = 0;
        Node cur = head;  //标记以后结点
        Node pre = null;  //记录前置结点
        while (cur != null) {
            if (position == index) {
                newNode.next = cur;
                pre.next = newNode;
                return;
            }
            pre = cur;
            cur = cur.next;
            position++;
        }
    }
}

插入一个节点做以后节点的下一个节点

• 指定地位删除节点
• 找出以后index地位的结点cur以及前一个结点 pre，pre.next间接指向cur.next即可删除cur结点。

/**
 * 删除指定地位的结点
 *
 * @param index 指定地位
 */
public void deleteNodeAtIndex(int index) {
    if (index < 0 || index > size() - 1) {
        throw new IndexOutOfBoundsException("IndexOutOfBoundsException");
    }
    if (index == 0) { //删除头
        head = head.next;
        return;
    }
    int position = 0;  //记录以后地位
    Node cur = head;  //标记以后结点
    Node pre = null;  //记录前置结点
    while (cur != null) {
        if (position == index) {
            pre.next = cur.next;
            cur.next = null;  //断开cur与链表的连贯
            return;
        }
        pre = cur;
        cur = cur.next;
        position++;
    }

}

• 删除下一个节点
  
• 链表反转
• 在链表遍历的过程中将指针程序置换，即每遍历一次链表就让cur.next指向pre，最初一个结点成为新的头结点。反转之后指针入下图红线所示。

/**
 * 链表反转
 */
public void reverse() {
    Node cur = head; //标记以后结点
    Node pre = null; //标记以后结点的前一个结点
    Node temp;
    while (cur != null) {
        //保留以后结点的下一个结点
        temp = cur.next;
        //cur.next指向pre，指针程序置换
        cur.next = pre;
        //pre、cur持续后移
        pre = cur;
        cur = temp;
    }
    //最初一个结点变成新的头结点
    head = pre;
}

• 求倒数第k个结点
• 倒数第k个结点就是第size() – k + 1个结点，cur结点向后挪动size() – k次就是倒数第k个结点。

/**
 * 倒数第k个结点
 *
 * @param k
 * @return
 */
public T getLastK(int k) {
    if (k < 0 || k > size()) { //留神index是能够等于size()的
        throw new IndexOutOfBoundsException("IndexOutOfBoundsException");
    }
    Node cur = head;
    for (int i = 1; i < size() - k + 1; i++) {
        cur = cur.next;
    }
    return cur.value;
}

循环链表

循环链表

双链表

双向链表

循环双向列表

循环双向列表一开始的pre和next都是本人