4-LinkedList底层布局和源码分析
介绍汇总:
- LinkedList的全面说明
- LinkedList的底层操作机制
- LinkedList的运行重要步骤
- ArrayList 和 LinkedList 比较
1-LinkedList的全面说明
- LinkedList 底层实现了双向链表和双端队列特点
- 可以添加任意元素(元素可以重复),包罗 null
- 线程不安全,没有实现同步
2-LinkedList的底层操作机制
- LinkedList 底层维护了一个双向链表。
- LinkedList 中维护了两个属性 first 和 last 分别指向 首节点和尾节点。
- 每个节点(Node 对象),里面又维护了 prev、next、item 三个属性,其中通过 prev 指向前一个,通过 next 指向后一个节点,终极实现双向链表。
- 所以 linkedList 的元素的添加和删除,不是通过数组完成,相对来说效率较高(仅需改变几个指针,无需移动数据)。
- 模仿一个简单的双向链表
- // 节点代码
- 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的运行重要步骤
因为双向链表是通过指针指向内存中的数据节点,形成一个链的聚集,所以为啥叫双向链表。所以存储的东西只有指针、巨细,也并没有扩容机制,只要不超出规定的内存,理论上可以无穷添加数据。
- 这里主要 debug 看源码就可以搞清晰了,关键是每个方法的详细使用的算法,比较故意思。
- 详细算法介绍
- // 添加数据为链表第一个,也就是 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 比较
- ArrayList 和 LinkedList 区别
聚集底层布局增删的效率改查的效率ArrayList可变数组较低数组扩容较高LinkedList双向链表较高,通过链表追加较低
- 如何选择 ArrayList 和 LinkedList
- 若改查的操作多,选择 ArrayList
- 若增删的操作多,选择 LinkedList
- 通例来说,程序中,80% - 90% 都是查询,因此大部分情况下选择 ArrayList
- 在一个项目中,根据业务灵活选择,也可能这样,一个模块使用的是 ArrayList ,另外一个模块是 LinkedList 。也就是说,要根据业务进行选择
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。 |