Java集合框架(二)-LinkedList

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;
    }
}

3、LinkedList初始化

// LinkedList包含首尾操作的特有方法，在list接口中没有定义，不推荐多态创建集合对象
// List<String> strList = new LinkedList<>();
// strList.addFirst();
LinkedList<String> linkedList = new LinkedList<>();

4、常用方法

4.1 add(E e)

添加元素的普通方法：add(元素)，将元素自动添加到链表的末尾

4.2 addFirst(E e)

<code>addFirst(E e)添加到链表首部

4.3 addLast(E e)

<code>addLast(E e)添加到链表首部

4.4 getFirst()

<code>getFirst() 获取第一个元素

4.5 getLast()

<code>getLast() 获取最后一个元素

4.7 removeFirst()

<code>removeFirst() 删除第一个元素

4.8 removeLast()

<code>removeLast() 删除最后一个元素

4.9 size()

<code>size() 获取集合中元素个数方法

4.10 get(int index)

 1）获取的下标值必须是在有效的范围内：从0到元素个数-1之间，否则报错：IndexOutOfBoundsException;
 2）如果下标值在可以有效的范围内，自动进行二分法移动指针，先判断目标下标值在元素个数一半的前半段还是后半段;
    如果在前半段，自动从第一个节点开始，依次向后移动指针，直到找到下标位置，返回对应元素;
    如果在后半段，自动从最后一个节点，依次向前移动指针，直到找到指定下标位置，返回对应元素;
 所以：当下标位置越接近元素个数一半值（越靠近中间位置），效率是最低的，可以看出：遍历和随机访问的效率低;

源码

public E get(int index) {
    checkElementIndex(index); //判断下标是否大于集合元素总数
    return node(index).item; //返回结点值（元素）
}

//一个一个的往后找到指定的节点并返回
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;
    }
}

5、ArrayList 和 LinkedList的区别

相同点

都是list的实现类，存放的元素都是有序，不唯一的，都是线程不安全的

不同点

1）底层实现不同：ArrayList底层实现是Object对象数组，而LinkedList底层是双向链表结构;

2）扩容机制不同：ArrayList默认是空的Object对象数组（也可以指定大于0的初识容量），首次自动扩容为10个长度，后续每次扩容原来容量的1.5倍，LinkedList底层是链表，没有容量，没有扩容，存放元素没限制;

3）使用场景不同：ArrayList适用于快速的遍历和随机访问元素，而LinkedList适用于快速的添加删除元素;

标签：Node,index,Java,LinkedList,元素,链表,添加,集合

来源： https://www.cnblogs.com/xiaoqigui/p/16393961.html

---

搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]‍，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：Java集合框架(二)-LinkedList

喜欢 (0)赏

[搞代码]

分享 (0)