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是什么”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！