4-LinkedList底层结构和源码分析

4-LinkedList底层结构和源码分析

介绍汇总:

  1. LinkedList的全面说明
  2. LinkedList的底层操作机制
  3. LinkedList的运行重要步骤
  4. ArrayList 和 LinkedList 比较

1-LinkedList的全面说明

  1. LinkedList 底层实现了双向链表和双端队列特点
  2. 可以添加任意元素(元素可以重复),包括 null
  3. 线程不安全,没有实现同步

2-LinkedList的底层操作机制

  1. LinkedList 底层维护了一个双向链表。
  2. LinkedList 中维护了两个属性 first 和 last 分别指向 首节点和尾节点。
  3. 每个节点(Node 对象),里面又维护了 prev、next、item 三个属性,其中通过 prev 指向前一个,通过 next 指向后一个节点,最终实现双向链表。
  4. 所以 linkedList 的元素的添加和删除,不是通过数组完成,相对来说效率较高(仅需改变几个指针,无需移动数据)。
  5. 模拟一个简单的双向链表
// 节点代码
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;
        }
}

// 简单双向列表
class LinkedList {
    int size = 0;

    Node<E> first;

    Node<E> last;
}

3-LinkedList的运行重要步骤

  1. 构造器

​ 因为双向链表是通过指针指向内存中的数据节点,形成一个链的集合,所以为啥叫双向链表。所以存储的东西只有指针、大小,也并没有扩容机制,只要不超出规定的内存,理论上可以无限添加数据。

  1. 这里主要 debug 看源码就可以搞清楚了,关键是每个方法的具体使用的算法,比较有意思。
  2. 具体算法介绍
// 添加数据为链表第一个,也就是 first 指向的
// 具体流程:
// 1. 根据 first 指针获取当前第一个数据结点
// 2. 创建一个参数为 first 指向为空(第一个结点),数据值,
// 		last 指向当前链表中第一个数据结点的新结点
// 3. 将 first 指向新结点
// 4. 判断加入之前 first 指向是否为空,若为空说明链表为空,则把 last 也指向新结点
// 		反之,说明链表中有数据,而之前 first 指向的数据节点 prev 为 null 所以把之前的
// 		第一个结点的 prev 指向当前的新结点
// 5. 记得一定要将数据个数或长度 + 1 以及链表修改记录
private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
}

// 添加数据为链表最后一个,也就是 last 指向的
// 具体流程:
// 1. 根据 last 指针获取当前最后一个数据结点
// 2. 创建一个参数为 first 指向为当前链表中最后一个数据节点,数据值,
// 		last 指向为空(最后一个结点)的新结点
// 3. 将 last 指向新结点
// 4. 判断加入之前 last 指向是否为空,若为空说明链表为空,则把 first 也指向新结点
// 		反之,说明链表中有数据,而之前 last 指向的数据节点 next 为 null 所以把之前的
// 		最后一个结点的 next 指向当前的新结点
// 5. 记得一定要将数据个数或长度 + 1 以及链表修改记录
void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
}

// 根据索引寻找数据值
// 将链表长度除以 2 ,然后根据该结果与索引的大小比较
// 大的话,说明数据节点离最后一个节点近
// 小的话,说明数据节点离第一个节点近
// 然后开始进行遍历循环匹配索引值的数据节点
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;
        }
}

4-ArrayList 和 LinkedList 比较

  1. ArrayList 和 LinkedList 区别
集合 底层结构 增删的效率 改查的效率
ArrayList 可变数组 较低数组扩容 较高
LinkedList 双向链表 较高,通过链表追加 较低
  1. 如何选择 ArrayList 和 LinkedList
    1. 若改查的操作多,选择 ArrayList
    2. 若增删的操作多,选择 LinkedList
    3. 常规来说,程序中,80% - 90% 都是查询,因此大部分情况下选择 ArrayList
    4. 在一个项目中,根据业务灵活选择,也可能这样,一个模块使用的是 ArrayList ,另外一个模块是 LinkedList 。也就是说,要根据业务进行选择

热门相关:甜蜜婚令:陆少的医神娇妻   公子别秀   遥望行止   剑斗九天   学霸你女朋友掉了