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

42次阅读

共计 2522 个字符，预计需要花费 7 分钟才能阅读完成。

如果是 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 都是本人

正文完