【数据结构】:单链表 循环链表 双向循环链表 双链表

单链表

image.png
若是是null,就说明后面没有节点了,若是不是null就说明后面要链接节点
image.png
每一个节点包含2部分,数据域,和一个指向下一个节点引用的指针next
data域--存放结点值的数据域
next域--存放结点的直接后继的地址的指针域(链域)
链表经过每一个结点的链域将线性表的n个结点按其逻辑顺序连接在一块儿的,每一个结点只有一个链域的链表称为单链表(Single Linked List)。
单链表
image.png
显示全部节点信息
image.pngspa

  • 头部插入节点
  • 若是链表没有头结点,新结点直接成为头结点;不然新结点的next直接指向当前头结点,并让新结点成为新的头结点。
    image.png
/**
* 添加结点至链表头部
*
* @param value
*/
public void addHeadNode(T value) {
   Node newNode = new Node(value);
   //头结点不存在,新结点成为头结点
   if (head == null) {
       head = newNode;
       return;
   }
   //新结点next直接指向当前头结点
   newNode.next = head;
   //新结点成为新的头结点
   head = newNode;
}
  • 尾部插入节点
  • 若是链表没有头结点,新结点直接成为头结点;不然须要先找到链表当前的尾结点,并将新结点插入到链表尾部。
    image.png
/**
* 添加结点至链表尾部
*
* @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位置。
    image.png
/**
 * 结点插入至指定位置
 *
 * @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++;
        }
    }
}

插入一个节点作当前节点的下一个节点
image.png.net

  • 指定位置删除节点
  • 找出当前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++;
    }

}
  • 删除下一个节点
    image.png
  • 链表反转
  • 在链表遍历的过程当中将指针顺序置换,即每遍历一次链表就让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;
}

循环链表

image.png
循环链表
image.png指针

双链表

image.png
image.png
双向链表code

循环双向列表

循环双向列表一开始的pre和next都是本身
image.png
image.png
image.png
image.pngblog

相关文章
相关标签/搜索