文档章节

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

火云
 火云
发布于 2015/06/12 11:43
字数 1835
阅读 7
收藏 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
博文 80
码字总数 9139
作品 0
西城
Android工程师
Java容器类框架分析(2)LinkedList源码分析

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

wustor
2017/11/06
0
0
java_面试_01_一个月的面试总结(java)

重点知识 由于我面试的JAVA开发工程师,针对于JAVA,需要理解的重点内容有: JVM内存管理机制和垃圾回收机制(基本每次面试都会问,一定要搞得透彻) JVM内存调优(了解是怎么回事,一般做项...

rayner
03/07
0
0
ArrayList、linklist、list的区别

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

随智阔
2014/03/04
0
0
记录转化为有层次结构的树状列表的通用算法

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

walb呀
2017/12/04
0
0
ArrayList和LinkedList

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

油焖菠菜
2016/09/13
46
1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

OSChina 周日乱弹 —— 种族不同,禁止交往

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @小小编辑:推荐歌曲《苏菲小姐》- 鱼果 《苏菲小姐》- 鱼果 手机党少年们想听歌,请使劲儿戳(这里) @貓夏:下大雨 正是睡觉的好时候 临睡前...

小小编辑
33分钟前
32
5
Python 搭建简单服务器

Python动态服务器网页(需要使用WSGI接口),基本实现步骤如下: 1.等待客户端的链接,服务器会收到一个http协议的请求数据报 2.利用正则表达式对这个请求数据报进行解析(请求方式、提取出文...

代码打碟手
35分钟前
0
0
Confluence 6 删除垃圾内容

属性(profile)垃圾 属性垃圾的定义为,一个垃圾用户在 Confluence 创建了用户,但是这个用户在自己的属性页面中添加了垃圾 URL。 如果你有很多垃圾用户在你的系统中创建了属性,你可以使用...

honeymose
今天
0
0
qduoj~前端~二次开发~打包docker镜像并上传到阿里云容器镜像仓库

上一篇文章https://my.oschina.net/finchxu/blog/1930017记录了怎么在本地修改前端,现在我要把我的修改添加到部署到本地的前端的docker容器中,然后打包这个容器成为一个本地镜像,然后把这...

虚拟世界的懒猫
今天
1
0
UML中 的各种符号含义

Class Notation A class notation consists of three parts: Class Name The name of the class appears in the first partition. Class Attributes Attributes are shown in the second par......

hutaishi
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部