LinkedList是什么

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

LinkedList是一个链表集合。

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

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

private static class Node {    E item;    Node next;    Node prev;    Node(Node prev, E element, Node 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 node(int index) {    // assert isElementIndex(index);    // 采用二分法遍历链表    if (index < (size >> 1)) {        Node x = first;        for (int i = 0; i < index; i++)            x = x.next;        return x;    } else {        Node x = last;        for (int i = size - 1; i > index; i--)            x = x.prev;        return x;    }}

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

peek() 直接返回头节点

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

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