文档章节

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

火云
 火云
发布于 2015/06/12 11:43
字数 1835
阅读 7
收藏 0
点赞 0
评论 0


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


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


我们大多数情况下都是在关注 什么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  二叉树 等等的博文。希望大家共同努力,看到此文的同学或者大牛能给一点建议也行! 


本文转载自:http://www.cnblogs.com/android007/archive/2012/05/12/2497379.html

共有 人打赏支持
火云
粉丝 4
博文 69
码字总数 7378
作品 0
西城
Android工程师
Java容器类框架分析(2)LinkedList源码分析

概述 在分析LinkedList的源码之前,先看一下ArrayList在数据结构中的位置,常见的数据结构按照逻辑结构跟存储结构可以做如下划分: 数据结构分类 先看看源码的注释: Doubly-linked list imp...

wustor ⋅ 2017/11/06 ⋅ 0

ArrayList、linklist、list的区别

List是一个接口,ArrayList和LinkedList是两个实现类,他们实现的方式不一样,其实LinkedList才是真正的链表(如果不清楚什么是链表,需要了解一下相关数据结构的知识,这不是一两句话能说清楚...

随智阔 ⋅ 2014/03/04 ⋅ 0

记录转化为有层次结构的树状列表的通用算法

问题说明: 访问数据库记录次数随着记录的增多而增多 由于需要多次访问数据库, 因此访问速度受影响 需要数据库访问层的支持, 并对记录进行转化, 耦合性太强 通用性不好, 每次需要一个新的类型...

walb呀 ⋅ 2017/12/04 ⋅ 0

ArrayList和LinkedList

ArrayList和LinkedList都实现了List接口,但是他们的实现原理却不一样,其数据结构也不相同。 ArrayList是一个大小可变的数组,当有更多的元素添加进ArrayList中时,其大小会动态的增长。 Link...

油焖菠菜 ⋅ 2016/09/13 ⋅ 1

Java集合框架简单复习

Java集合框架复习 Collection:首先,根接口为Collection接口。首先,所有的集合的根接口是Collection,Collection接口继承了Iterable接口,因此,所有的集合子类都可以当做迭代器来使用。 对于...

断桥残雪断桥残雪 ⋅ 2015/08/05 ⋅ 0

ArrayList、Vector、HashMap、HashSet的默认初始容量、加载因子、扩容增量

这里要讨论这些常用的默认初始容量和扩容的原因是: 当底层实现涉及到扩容时,容器或重新分配一段更大的连续内存(如果是离散分配则不需要重新分配,离散分配都是插入新元素时动态分配内存)...

小萝卜_ ⋅ 2016/12/10 ⋅ 0

LinkedList浅析

LinkedList和ArrayList都实现了List,但是两者的存储结构不一样:LinkedList是链表,ArrayList是数组,那就决定了两者特性不一样: LinkedList插入删除方便效率高,但是根据索引查找就需要遍...

清尘V ⋅ 2016/05/08 ⋅ 0

Java 复习 —— 集合

1、类的基本结构 Collection ├List │├LinkedList │├ArrayList │└Vector │ └Stack └Set |-HashSet |-TreeSet Map ├Hashtable ├HashMap └WeakHashMap 2、基本概念 0)Collection ......

learn_more ⋅ 2015/08/05 ⋅ 0

Java集合之ArrayList源码解析

ArrayList是我们在开发中经常使用的一个集合,继续按照以前的风格来解析源码(JDK1.7)。 ArrayList简要概括: 1.ArrayList的底层数据结构是一个数组,确切地说是一个动态数组,每次扩容的时...

GeneralAndroid ⋅ 2017/11/30 ⋅ 0

Java:ArrayList和LinkedList区别

一般大家都知道ArrayList和LinkedList的大致区别: 1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。 2.对于随机访问get和set,ArrayList觉得优于LinkedList,因...

heiyexue ⋅ 2014/09/09 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

zblog2.3版本的asp系统是否可以超越卢松松博客的流量[图]

最近访问zblog官网,发现zlbog-asp2.3版本已经进入测试阶段了,虽然正式版还没有发布,想必也不久了。那么作为aps纵横江湖十多年的今天,blog2.2版本应该已经成熟了,为什么还要发布这个2.3...

原创小博客 ⋅ 42分钟前 ⋅ 0

聊聊spring cloud的HystrixCircuitBreakerConfiguration

序 本文主要研究一下spring cloud的HystrixCircuitBreakerConfiguration HystrixCircuitBreakerConfiguration spring-cloud-netflix-core-2.0.0.RELEASE-sources.jar!/org/springframework/......

go4it ⋅ 今天 ⋅ 0

二分查找

二分查找,也称折半查找、二分搜索,是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于...

人觉非常君 ⋅ 今天 ⋅ 0

VS中使用X64汇编

需要注意的是,在X86项目中,可以使用__asm{}来嵌入汇编代码,但是在X64项目中,再也不能使用__asm{}来编写嵌入式汇编程序了,必须使用专门的.asm汇编文件来编写相应的汇编代码,然后在其它地...

simpower ⋅ 今天 ⋅ 0

ThreadPoolExecutor

ThreadPoolExecutor public ThreadPoolExecutor(int corePoolSize, int maximumPoolSize, long keepAliveTime, ......

4rnold ⋅ 昨天 ⋅ 0

Java正无穷大、负无穷大以及NaN

问题来源:用Java代码写了一个计算公式,包含除法和对数和取反,在页面上出现了-infinity,不知道这是什么问题,网上找答案才明白意思是负的无穷大。 思考:为什么会出现这种情况呢?这是哪里...

young_chen ⋅ 昨天 ⋅ 0

前台对中文编码,后台解码

前台:encodeURI(sbzt) 后台:String param = URLDecoder.decode(sbzt,"UTF-8");

west_coast ⋅ 昨天 ⋅ 0

实验楼—MySQL基础课程-挑战3实验报告

按照文档要求创建数据库 sudo sercice mysql startwget http://labfile.oss.aliyuncs.com/courses/9/createdb2.sqlvim /home/shiyanlou/createdb2.sql#查看下数据库代码 代码创建了grade......

zhangjin7 ⋅ 昨天 ⋅ 0

一起读书《深入浅出nodejs》-node模块机制

node 模块机制 前言 说到node,就不免得提到JavaScript。JavaScript自诞生以来,经历了工具类库、组件库、前端框架、前端应用的变迁。通过无数开发人员的努力,JavaScript不断被类聚和抽象,...

小草先森 ⋅ 昨天 ⋅ 0

Java桌球小游戏

其实算不上一个游戏,就是两张图片,不停的重画,改变ball图片的位置。一个左右直线碰撞的,一个有角度碰撞的。 左右直线碰撞 package com.bjsxt.test;import javax.swing.*;import j...

森林之下 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部