数据结构与算法(五): 循环链表

数据结构与算法 2020-03-18 87 次浏览 本文字数:3972字

本文主要内容: 单向循环链表、双向循环链表

单向循环链表

  • 只需要尾节点的next指向头节点即可
    单向循环链表展示

单向循环列表接口设计

  • 相较于单向列表,单向循环列表只需重写插入节点、删除节点两个方法

单向循环列表的实现

/**
 * 三、添加元素
 * 需要注意插入元素为链表的第一个元素和插入链表第0个位置的元素
 */
public void add(int index, E element) {
    //检查索引是否越界
    rangeCheckForAdd(index);

    if (index == 0) {
        //插入的是第一个元素
        if (size == 0) {
            first = new Node<E>(element, first);
        }else {
            //插入到第0个位置的元素
            Node<E> oldFirst = first;
            Node<E> last = node(size - 1);
            first = new Node<E>(element, oldFirst);
            last.next = first;
        }
    }else {
        //找到指定位置前面的节点,用前面的节点next指向新节点,新节点的next指向先前节点的指向节点
        Node<E> prev = node(index - 1);
        prev.next = new Node<E>(element, prev.next);
    }
    size++;
}

/**
 * 四、删除元素
 * 注意判断删除元素是不是第一个元素和删除的是不是最后一个元素
 */
public E remove(int index) {
    //检查索引是否越界
    rangeCheck(index);

    //记录要删除的节点,准备返回
    Node<E> old = first;

    //删除头节点
    if (index == 0) {
        //只有一个节点
        if (size == 1) {
            first = null;
        } else {
            Node<E> last = node(size - 1);
            first = first.next;
            last.next = first;
        }
    } else {
        //找到前一个元素
        Node<E> node = node(index - 1);
        //记录需要删除的元素
        old = node.next;
        //讲前一个元素节点的next指向要删除节点的后一个节点
        node.next = node.next.next;
    }
    //注意size要减-1
    size--;
    return old.element;
}

双向循环链表

  1. 头节点的prev指向尾节点
  2. 尾节点的last指向头节点
    双向循环链表展示

双向循环链表的接口设计

  • 相较于双向列表,单向循环列表只需重写插入节点、删除节点两个方法

双向循环链表的实现

/**
 * 需特殊处理添加第一个元素和添加到尾节点两种特殊情况
 */
public void add(int index, E element) {
    //检查索引是否越界
    rangeCheckForAdd(index);

    //这是链表添加的第一个元素或者末尾元素
    if (index == size) {
        Node<E> node = new Node<>(last, element, first);
        if (size == 0) {
            first = node;
            last = node;
            node.prev = node;
            node.next = node;
        } else {
             // 原链表尾节点next指向node
            last.next = node;
            // 原链表头结点prev指向node
            first.prev = node;
            // last指向新的尾节点
            last = node;
        }             
    } else {
        //链表向中间添加元素或者向头部添加元素
        Node<E> next = node(index);
        Node<E> prev = next.prev;

        Node<E> node = new Node<>(prev, element, next);
        next.prev = node;
        if (prev == null) {
            //链表向初始添加元素
            first = node;
        } else {
            //链表向中间添加元素
            prev.next = null;
        }
    }
    size++;

}

/**
 * 删除节点:只需让被删节点的前后节点进行连接
 * 同时:需要处理第一个节点和最后一个节点
 */
public E remove(int index) {
    //检查索引是否越界
    rangeCheck(index);

    // 需要删除的节点
    Node<E> node = node(index);
    // 删除节点的前一个节点
    Node<E> prev = node.prev;
    // 删除节点的后一个节点
    Node<E> next = node.next;
    // 删除节点, 只需要去掉对这个节点的引用即可
    // 如果prev == null, 说明删除的是第一个节点
    if (prev == null) {
        first = next;
    }else {
        prev.next = next;
    }
    // 如果next == null, 说明删除的是最后一个节点
    if (next == null) {
        last = prev;
    }else {
        next.prev = prev;
    }
    size--;
    return node.element;
}

本文由 WarlockMarten 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。