纪念第一次手写源码

前几天看百度面试题,有一道题是手写Arraylist,于是一直在心中就想怎么实现,看自己能不能写出,于是翻源码看,感觉有些方法能看懂,但是有些确实需要很高深的数据结构的功底才能写出来,自己心里有点后怕。 但是我不服气啊哈哈! 今天就在java交流群里试探大家怎么看这件事,可是好多竟然都说很简单,我不知道那些是装逼的还是真的大神,可是我性格就是不愿意服输,于是下决心今天一定要把它写出来!!!


写Arraylist之前要先明白一些要素: 1.ArrayList的底层是Object类的数组,默认长度是10,超过10后,长度变为原长度的2倍。(这个数字可以变) 2.ArrayList底层是个动态数组实现的,长度不够时,调用Arrays.copyOf方法,拷 贝当前数组到一个新的长度更大的数组。如果是数组比较大,那么使用System.arraycopy会比较有优势,因为其使用的是内存复制,省去了大量的数组寻址访问等时间,所以我实现的方法全部用System.arraycopy。 3.因为是自己实现,所以只能实现一些主要的方法,我实现了一下方法。

1.rangCheck(index)-----检查数组下标是否越界
2.ensureCapasity()------保证数组的有效容量
3.空参构造方法和提供初始化容量的构造方法
4.增方法(add(int index,Oject obj))
5.删方法(remove())
6.赋值方法(set(int index,Object obj)
7.查询方法(get(int index)
8.获取集合长度方法size()

展示代码之前先说明一下 System.arraycopy(src, srcPos, dest, destPos, length);的用法: 复制指定源数组src到目标数组dest。复制从src的srcPos索引开始,复制的个数是length,复制到dest的索引从destPos开始。 整体代码如下:

package cn.baidu.list;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 自己实现一个Arraylist
 * @author kyy
 *在ArrayList中有个成员变量modCount,继承于AbstractList。
     这个成员变量记录着集合的修改次数,也就每次add或者remove它的值都会加1。这到底有什么用呢?
 */
public class MyArraylist {
    
    private Object[] elementData=null;
    
    private int size;
    
    //提供构造方法,默认长度为10
    public MyArraylist(){
        this(10);
    }
    
    //提供初始化长度的构造方法
    public MyArraylist(int initCpacity){
        //如果集合长度小于初始化长度
        if(initCpacity<0){
            try {
                throw new Exception();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        elementData=new Object[initCpacity];
    }
    
    public int size(){
        return size;
    }
    
    public boolean isEmpty(){
        return size==0;
    }
    
    //判断数组下标是否越界
    public void rangeCheck(int index){
        if(index<0||index>=size){
            try {
                throw new Exception();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }
    
    public void ensureCapacity(){
        if(size>=elementData.length){
            Object[] temp=new Object[elementData.length*2];  
            System.arraycopy(elementData, 0, temp, 0, size);
            elementData=temp;
        }
    }
    
    //增加元素
    public void add(Object obj){
        ensureCapacity();
        elementData[size++]=obj;
    }
    
    public void add(int index,Object obj){
        rangeCheck(index);
        ensureCapacity();
        System.arraycopy(elementData, index, elementData, index+1, size-index);
        elementData[index]=obj;
        size++;
    }
    
    //根据索引查询元素
    public Object get(int index){
        rangeCheck(index);
        return elementData[index];
    }
    
    //给指定索引赋值
    public Object set(int index,Object obj){
        rangeCheck(index);
        Object oldObj = elementData[index];
        elementData[index]=obj;
        return oldObj;
    }
    //删除指定索引元素
    public void remove(int index){
        rangeCheck(index);
        ensureCapacity();
        System.arraycopy(elementData, index+1, elementData, index, size-index-1);
        size--;
    }
}

注意:集合的初始容量是10不是说集合一开始就有10的长度,因为size()方法,指的是“逻辑”长度。 所谓“逻辑”长度,是指内存已存在的“实际元素的长度” 而“空元素不被计算” 即:当你利用add()方法,向ArrayList内添加一个“元素”时,逻辑长度就增加1位。 而剩下的9个空元素不被计算。

整体写下来不是很简单,因为牵扯到一些数组元素移动的计算,写的时候一定要考虑仔细,不然容易出错!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏工科狗和生物喵

【计算机本科补全计划】Java学习笔记(九) Java日期时间

### 1、 Java 日期时间 java.util 包提供了 Date 类来封装当前的日期和时间。 Date 类提供两个构造函数来实例化 Date 对象。第一...

912
来自专栏java工会

java集合详解

23910
来自专栏来自地球男人的部落格

[LeetCode] 347. Top K Frequent Elements

【原题】 Given a non-empty array of integers, return the k most frequent elements...

2797
来自专栏拭心的安卓进阶之路

Java 集合源码解析(1):Iterator

Java, Android 开发也有段时间了,当初为了早点学 Android,Java 匆匆了解个大概就结束了,基础不够扎实。 虽然集合框架经常用,但是一直...

2195
来自专栏Java后端技术栈

初探Java源码之LinkedList

上篇文章我们分析了常见的ArrayList源码,它的内部是由一个数组来实现的。那么今天,我们来分析另一个常见的类LinkedList。本文分析都来自Java8。...

1202
来自专栏程序员互动联盟

读 Java Arrays 源码 笔记

Arrays.java是Java中用来操作数组的类。使用这个工具类可以减少平常很多的工作量。了解其实现,可以避免一些错误的用法。 它提供的操作包括: 排序 so...

36912
来自专栏wannshan(javaer,RPC)

JDK PriorityBlockingQueue remove(Object o) 源码分析

先知道PriorityBlockingQueue 是利用数组存储二叉堆实现。最小值(最优先)放在queue[0]位置。 //删除某个元素 public bool...

3587
来自专栏开发之途

Java集合框架源码解析之LinkedList

1263
来自专栏韦弦的偶尔分享

Swift 有效的括号 - LeetCode

给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。

1532
来自专栏开发之途

Java集合框架源码解析之LinkedHashMap

1193

扫码关注云+社区