LinkedList是什么

这篇文章主要介绍“LinkedList是什么”,在日常操作中,相信很多人在LinkedList是什么问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”LinkedList是什么”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!

LinkedList是一个链表集合。

public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable

可以发现LinkedList没有实现RandomAccess接口,意味着不可以使用for(int i = 0; i < size; i++)进行遍历数据

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

通过节点的数据结构,可以看出来LinkedList是一个双向链表。链表的特性是方便插入和删除界面。

/**
 * Tells if the argument is the index of an existing element.
 */
private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}

/**
 * Tells if the argument is the index of a valid position for an
 * iterator or an add operation.
 */
private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

isElementIndex, isPositionIndex是提供的两个对于边界检查的方法, 通过代码发现,一个是[0, size), 一个是[0,size], 范围是不一样的,因为索引为size的位置是一个可插入位,但不是现有的Element位。

/**
 * Returns the (non-null) Node at the specified element index.
 */
Node<E> node(int index) {
    // assert isElementIndex(index);

    // 采用二分法遍历链表
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

获取指定index的element,算法采用了二分法。虽然在时间复杂度上还是o(n), 但实际计算时确实节省了1/2的时间。

peek() 直接返回头节点

poll() 返回头节点,并在链表中删除

到此,关于“LinkedList是什么”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注亿速云网站,小编会继续努力为大家带来更多实用的文章!

原创文章,作者:Maggie-Hunter,如若转载,请注明出处:https://blog.ytso.com/220031.html

(0)
上一篇 2022年1月2日
下一篇 2022年1月2日

相关推荐

发表回复

登录后才能评论