复习计划——链表与 Java

本贴最后更新于 2905 天前,其中的信息可能已经事过景迁

个人复习计划——Java 中链表的实现(部分分析)(待更新)

声明

写给今天的自己,只是简单总结下今天所整理的知识点。
当初学习数据结构的时候第一篇便是链表,链表也是一个再简单不过的概念,那么看看那些大师级的人物是如何编写 Java 中链表的实现的。本篇暂时先分析今天刚刚看到的 ArrayList 的源码 (jdk8 版本)和自己遇到的困惑


12 月 5 日所学

ArrayList 基于数组的链表

整体思路

1. 一个在简单不过的数组来存放元素

transient Object[] elementData; // non-private to simplify nested class access

这里有两个困惑点

  • 关键字 transient 的作用
  • 为什么没有使用 private 关键字,而是默认的范围

2. 易忽略点 : index 下标的检查

当涉及到 add(index) , get(index), remove(index) 等操作的时候,首先需要对 index 进行范围的检查

if (index < 0 || index > size) {
    throw new IndexOutofBoundException("Index: "+index+", Size: "+size);
}

3. 数组扩容的实现

数组扩容的道理很简单,但如何去制定这个扩量的度呢?我们看下他们是思路是什么。

  • Step 1 : 数组的创建。(分两种情况)
    • 创建数组时传递了数组的创建时的大小
    • 创建数组时没有传递任何信息(数组默认为一个长度为 0 的数组{})
  • Step 2 : 数组的扩容
    • 当数组长度为 0 时,则扩充到 max(minCapacity, DEFAULT_CAPACITY)
    • 当数组长度不为 0 是,扩充 1.5 倍
    • 当数组长度超过最大限制时,抛出异常

4. 易忽略点 : 删除操作

  • 版本一:数组实现的链表删除一个节点的思路十分简单:从即将删除的 index 节点开始,将后面的 index + 1 到 size(元素个数)向前平移一位。
// 参数的意义分别为 : src, srcPos, dest, destPos, length
System.arraycopy(elementData, index + 1, elementData, index, size - index);
size--;
  • 漏洞一:虽然实现了功能点,却漏掉了一个重要的内容,链表的最后一个对象依然被引用,所以我们需要释放它
// 参数的意义分别为 : src, srcPos, dest, destPos, length
System.arraycopy(elementData, index + 1, elementData, index, size - index);
elementData[--size] = null;  //由GC垃圾回收器回收未被引用的对象
  • 漏洞二:删除操作一定需要平移吗? NO!当删除的节点是尾节点时,此时不必再向前平移数组
int numMoved = size - index - 1;
if (numMoved > 0) {
    System.arraycopy(elementData, index + 1, elementData, index, size - index);
}
elementData[--size] = null;  //由GC垃圾回收器回收未被引用的对象

transient 关键字

只能修饰变量,是在类的序列化和反序列化中起到作用。被 transient 关键字修饰到的成员变量不会再被序列化(对于静态变量而言,永远都不能被序列化)

  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3187 引用 • 8213 回帖
  • Link
    1 引用 • 1 回帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...
  • vanlin

    必须要赞,,狠狠的赞