文档章节

重新复习数据结构-------ArrayList

火云
 火云
发布于 2015/06/12 11:43
字数 1835
阅读 30
收藏 0

精选30+云产品,助力企业轻松上云!>>>


对于数据结构,我想做我们这一行的人都不陌生,数据结构 是我们计算机的基础。坦白的讲觉得他很重要,但是在实际的企业及开发过程中我们确实很少用到自己的数据结构(当然了,每一个类 都是一个 数据结构 这个我不否认,这里我指的是我们自己为了满足需求而建立的数据结构)。 在国内的开发中我感觉确实如我上面所说的那样 很少时候需要我们自己去建立数据结构,除非某些情况下因为数据结构影响了性能 我们才会这么去做。


介于此我们就是少关注数据结构(我说这话可能有些牵强,不过自己回想一下是不是这样的!扪心自问一下!)


我们大多数情况下都是在关注 什么spring  hibernate 诸如此类的框架,我只能说这是一个浮躁的时代(我并不是说框架没有技术含量),我们大多数时候都是 “忘本”的。敢问数据结构、 算法分析、编译原理 在这个浮躁的年代谁还在看,谁还在复习!


 


算了上面扯了那么多,入正题吧!


进来感到自己要学的东西很多,譬如数据结构吧,算法分析吧,虽然之前看过,但都是一掠而过,本身做java 和android 开发的,加上java 里面本身内置的一些结构在大多数情况都能满足我们正常的需求,所以也就很少关注自己能否建立一个数据结构。所以有时候也就浑浑噩噩额的过生活以至于工作两年了感觉自己还是一无所获。(票子  房子  车子 妻子  孩子 都没有啊,好歹也两年了啊!惭愧啊)于是想自己学习一下数据结构,并且总结一下 在深入看看一些源码!


我们这里先看jdk 中的ArrayList


还是老样子看源码先看 源码注释,注视里面一般包含了大部分的介绍.


 

Resizable-array implementation of the <tt>List</tt> interface.  Implements
 * all optional list operations, and permits all elements, including
 * <tt>null</tt>.  In addition to implementing the <tt>List</tt> interface,
 * this class provides methods to manipulate the size of the array that is
 * used internally to store the list.  (This class is roughly equivalent to
 * <tt>Vector</tt>, except that it is unsynchronized.)<p>

(我们一段一段的看,等等你可能觉得这样很烦 很浪费时间,朋友请不要这里认为 不然sun 的人也就不会 写这么长的注释了) 


好了 如果您能够看懂这些注释最好,不能看懂 没关系我帮你翻译(尽管的英语很烂,呵呵!)


翻译如下:“该类 实现List 接口,他用于List里面所有的方法 并且允许元素 为空,另外呢 除了实现了 List接口之外 他还提供了一些可以改变数组大小的方法,大致上和Vector 是类似的,只不过他是不同步的(也就是我们所说的线程不安全的) ”


(咳咳,翻译的不好别见怪)还是接着看注释 ,注释真多啊

The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
* <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant
* time.  The <tt>add</tt> operation runs in <i>amortized constant time</i>,
* that is, adding n elements requires O(n) time.  All of the other operations
* run in linear time (roughly speaking).  The constant factor is low compared
* to that for the <tt>LinkedList</tt> implementation.<p>

 翻译:


下面的 方法 如size isEmpty get set iterator  和 listIterator 这些操作他们的运行时 消耗的时间复杂度 是常数,但是add 方法的操作 就不是常数,添加的一个元素需要  n 倍的时间,其他的一些操作是一个 线性的他的这些 操作的复杂度相比较于 LinkedList 要低一些,(add 的就除外)


很明显 这两段 注释 上面一段说 线程问题,下面语段说明 效率的问题以及包含的一些 常用的方法 注释很有用的对吧!


 


其他的注释 我们就不在这一一的说了说说 我们自己 建立ArrayList吧 


首先我们要考虑自己的 arraylist 需要哪些方法。。。(set  get isEmpty  add remove ) 这些都是需要的,不然我们的数据结构存在也就没有意义了


当然了 我们设计写方法的时候要去考虑一系列的问题,比如 下标越界 之类的。那么我们这个 类里面需要一个size 的东西 来记录。我们都知道ArrayList 的底层实现 是array 来做的,这个时候考虑这些 下标越界 就是必须的,所以当然了 这个类里面我们需要包含一个 数组Object[]  (可以是泛型的),还有就是我们 的add 方法, 考虑的数组的短处,长度是一定的没办法动态的修改大小,就需要我们在add 时候 做判断,如果现在的add 的对象之后,array size 等于了数组的长度,那么这个时候我们就需要 对重新产生数组了(简称扩容吧),正是这个时候影响我们的性能,仔细想想难道不是么?


好了写到这一步我们的ArrayList 也就算完成了(其他的一些方法 比如 Iterator 自己可以区实现的),那么到目前为止你应该对ArrayList 有了一个深度的了解了,具体的还是要看JDK源码,下面我们给出上面我们自己建立的ArrayList源码:

package com.algorithm;
 
import java.util.Iterator;
 
public class MyArrayList<AnyType> implements Iterator<AnyType>{
 
    private static final int DEFAULT_CAPACITY = 10;
    private int    theSize;
    private AnyType[] theItems;
     
    public MyArrayList(){
        clear();
    }
    public void clear(){
        theSize = 0;
        ensureCapacity(DEFAULT_CAPACITY);
    }   
    public int size(){
        return theSize;
    }
    public boolean isEmpty(){
        return size() == 0;
    }
    public void trimToSize(){
        ensureCapacity(size());
    }
    public AnyType get(int index){
        if(index < 0 || index >= theSize )
            throw new ArrayIndexOutOfBoundsException();
        return theItems[index];
    }
    public AnyType set(int index,AnyType newVal){
        if(index < 0 || index >= theSize)
            throw new ArrayIndexOutOfBoundsException();
        AnyType oldVal = theItems[index];
        theItems[index] = newVal;
        return oldVal;
    }
    @SuppressWarnings("unchecked")
    public void ensureCapacity(int newCapacity){
        if(newCapacity < theSize)
            return;
        AnyType[] old = theItems;
        theItems      =(AnyType[])new Object[newCapacity];
        for(int i = 0 ; i < size() ; i ++){
            theItems[i] = old[i];
        }
    }
    public boolean add(AnyType x){
        add(size(),x);
        return true;
    }
    public void add(int index,AnyType x){
        if(theItems.length == size())
            ensureCapacity(size()*2 + 1);
        for(int i = theSize ; i > index ; i--)
            theItems[i] = theItems[i - 1];
        theItems[index] = x;
        theSize ++ ;
    }
    public AnyType remove(int index){
        AnyType removedItem = theItems[index];
        for(int i = index ; i < size() ; i ++)
            theItems[i] = theItems[i+1];
        theSize --;
        return removedItem;
    }
     
    public java.util.Iterator<AnyType> iterator(){
        return new ArrayListIterator();
    }
    private class ArrayListIterator implements java.util.Iterator<AnyType>{
 
        private int current = 0;
         
        @Override
        public boolean hasNext() {
            return current < size();
        }
 
        @Override
        public AnyType next() {
            if(!hasNext())
                throw new java.util.NoSuchElementException();
            return theItems[current++];
        }
 
        @Override
        public void remove() {
            MyArrayList.this.remove(--current);
        }
         
    }
    @Override
    public boolean hasNext() {
        // TODO Auto-generated method stub
        return false;
    }
    @Override
    public AnyType next() {
        // TODO Auto-generated method stub
        return null;
    }
    @Override
    public void remove() {
        // TODO Auto-generated method stub
         
    }
     
    public static void main(String[] args) {
         
        MyArrayList  array =  new MyArrayList();
        array.add(1);
        array.add(2);
        array.add(3);
        array.add(4);
        System.out.println(array.size());
    }
}

 


note:写这篇文章我也是因为这一段再复习数据结构和算法分析,感触良多,想来想去觉得有必要一记!仅此鼓励自己努力看下去,让我在这个浮躁的社会能沉下心来学习!


接下来的日子我会努力去做写一些建立 Map  二叉树 等等的博文。希望大家共同努力,看到此文的同学或者大牛能给一点建议也行! 


火云
粉丝 5
博文 105
码字总数 15276
作品 0
西城
Android工程师
私信 提问
java源码

Java 集合深入理解:ArrayList 回归基础,Java 集合深入理解系列,持续更新~ JVM 源码分析之 System.currentTimeMillis 及 nanoTime 原理详解 JVM 源码分析之 System.currentTimeMillis 及 ...

掘金官方
2017/12/18
0
0
Java集合类的概述

前述   复习一下Java中的集合类,是面试笔试中常考察的一个点,特地做的整理。 什么是集合类?   集合类,也叫容器类。Java集合类可以用来存储数量庞大的对象。   我们和数组进行对比:...

osc_tzh2wzwm
04/16
3
0
Java原来还可以这么学:如何搞定面试中必考的集合类

原创声明 本文首发于微信公众号【程序员黄小斜】 本文作者:黄小斜 转载请务必在文章开头注明出处和作者。 系列文章介绍 本文是《五分钟学Java》系列文章的一篇 本系列文章主要围绕Java程序员...

程序员黄小斜
03/12
0
0
Java原来还可以这么学:如何搞定面试中必考的集合类

原创声明 本文首发于微信公众号【程序员黄小斜】 本文作者:黄小斜 转载请务必在文章开头注明出处和作者。 系列文章介绍 本文是《五分钟学Java》系列文章的一篇 本系列文章主要围绕Java程序员...

黄小斜
03/12
22
0
Java原来还可以这么学:如何搞定面试中必考的集合类

原创声明 本文作者:黄小斜 转载请务必在文章开头注明出处和作者。 系列文章介绍 本文是《五分钟学Java》系列文章的一篇 本系列文章主要围绕Java程序员必须掌握的核心技能,结合我个人三年多...

黄小斜
03/19
20
0

没有更多内容

加载失败,请刷新页面

加载更多

FusionConputer热迁移过程记录

一、迁移原因   云平台集群内存资源不足,已超过设定阈值,内存资源已紧急告警。 二、解决思路   启用新集群,并将老集群中部分虚拟机热迁移至新集群 三、迁移的前提条件   1.被迁移虚...

osc_flwkfqx5
43分钟前
13
0
使用 ServerLess 实现云原生

笔者有幸经历了 IaaS(OS)、CaaS(Container),在这两年又听到了 FaaS(Funtion),这也是运维开发领域里的第三个阶段了吧,今天我将从一个不懂得开发的系统工程师视角以及结合之前的几篇系...

osc_t59f3rc0
45分钟前
18
0
作为软件测试的前辈你能不能给迷茫中的我一点建议?

一、为什么迷茫? 假如前面迷雾一片,作为司机的你,敢踩油门往前冲吗? 大多数人是不敢的。 因为你看不清自己的位置和发展的方向。 同理,一切对未来的恐慌、畏惧、纠结、迷茫,也是因为你看...

osc_auwur47t
47分钟前
12
0
神经机器翻译的直观解释

作者|Renu Khandelwal 编译|VK 来源|Towards Data Science 什么是神经机器翻译? 神经机器翻译是一种将一种语言翻译成另一种语言的技术。一个例子是把英语转换成印地语。让我们想想,如果你在...

osc_u61lmlkv
47分钟前
0
0
用Tableau实现动画数据可视化

作者|PRANAV DAR 编译|VK 来源|Analytics Vidhya 概述 动画可视化是一种艺术,它很容易在Tableau中创造出来 我们将在这里使用开源数据集,并在Tableau中创建自己的动画可视化 介绍 我是动画视...

osc_1oqjcug0
48分钟前
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部