1.向量介绍 　　计算机程序主要运行在内存中，而内存在逻辑上可以被看做是连续的地址。为了充分利用这一特性，在主流的编程语言中都存在一种底层的被称为数组(Array)的数据结构与之对应。在使用数组时需要事先声明固定的大小以便程序在运行时为其开辟内存空间；数组通过下标值计算出地址偏移量来对内部元素进行访问。 　　可以看到，原始的数组很基础，所以运行效率非常的高。但同时也存在着严重的问题： 　　1.由于数组的大小需要在创建时被固定下来，但大多数程序在编写时无法很好的预测到可能的数据量大小，因而也就无法在创建时设置合适的数组大小，过大则浪费内存空间；过小则会出现上溢，需要编程人员进行特别的处理。 　　2.访问数组时，很容易出现数组下标越界的情况。由于数组的访问是非常频繁的，因而在追求性能的语言中(如C语言)，编译器都没有对数组下标越界进行额外的检查，当程序出现了意外的数组下标越界时，依然允许程序访问和修改数组外部的内存地址，这很容易造成古怪的，难以复现的bug。(Java，python等较为高级的语言为了安全起见，即使舍弃掉一定的性能也要对数组下标越界进行检查)。 　　针对上述问题，我们需要对原始的数组进行一定程度的封装，在不改变基本使用方式的前提下，使其在运行过程中能够针对所存储的数据量大小自适应的扩容；对数组下标的越界访问进行检查，同时提供一系列的常用接口供用户使用。 　　而这个基于数组封装之后的数据结构，我们一般称之为"向量(vector)"或者"顺序表(sequence list)"。 2.向量主要ADT接口介绍 　　由于是使用java作为实现的语言，因此在设计上参考了jdk自带的向量数据结构：java.util.ArrayList类。 　　1.size() 　　　　接口定义：int size(); 　　　　接口描述：返回当前列表中元素的个数。 　　2.isEmpty() 　　　　接口定义：boolean isEmpty(); 　　　　接口描述：如果当前列表中元素个数为0，返回true；否则，返回false。 　　3.indexOf() 　　　　接口定义：int indexOf(E e); 　　　　接口描述：判断元素"e"是否存在于列表中 　　4.contains() 　　　　接口定义：boolean contains(E e); 　　　　接口描述: 判断元素"e"是否存在于列表中 　　5.add() 　　　　接口定义：boolean add(E e); 　　　　接口描述：在列表的最后插入元素"e"。 　　　　接口定义：void add(int index,E e); 　　　　接口描述：在列表的下标为"index"位置处插入元素"e"。 　　6.remove() 　　　　接口定义：boolean remove(E e); 　　　　接口描述：从列表中找到并且移除"e"对象，找到并且成功移除返回true；否则返回false。 　　　　 　　　　接口定义：E remove(int index); 　　　　接口描述：移除列表中下标为"index"位置处的元素，返回被移除的元素。 　　7.set() 　　　　接口定义：E set(int index,E e); 　　　　接口描述：将列表中下标为"index"位置处的元素替代为"e",返回被替代的元素。 　　8.get() 　　　　接口定义：E get(int index); 　　　　接口描述：返回列表中下标为"index"位置处的元素。 3.向量实现细节 3.1 向量属性 　　向量作为数组的进一步封装，内部持有着一个数组，首先我们有以下属性： 复制代码 public class ArrayList implements List { //===============================================成员变量====================================================== /** * 内部封装的数组 */ private Object[] elements; /** * 线性表默认的容量大小 * */ private static final int DEFAULT_CAPACITY = 16; /** * 扩容翻倍的基数 * */ private static final double EXPAND_BASE = 1.5; /** * 内部数组的实际大小 * */ private int capacity; /** * 当前线性表的实际大小 * */ private int size; //=================================================构造方法====================================================== /** * 默认的无参构造方法 * */ public ArrayList() { this.capacity = DEFAULT_CAPACITY; size = 0; //:::设置数组大小为默认 elements = new Object[capacity]; } /** * 设置内部数组初始大小的构造方法 * @param capacity 内部数组初始大小 * */ public ArrayList(int capacity) { this.capacity = capacity; size = 0; //:::设置数组大小 elements = new Object[capacity]; } } 复制代码 3.2 较为简单的 size()，isEmpty()，indexOf()，contains()方法实现： 复制代码 @Override public int size() { return this.size; } @Override public boolean isEmpty() { return (this.size == 0); } @Override public int indexOf(E e) { //:::判断当前参数是否为null if(e != null){ //::::参数不为null //:::从前到后依次比对 for(int i=0; i this.size || index < 0){ throw new RuntimeException("index error index=" + index + " size=" + this.size) ; } } /** * 下标越界检查 * @param index 下标值 */ private void rangeCheck(int index){ //:::如果下标小于0或者大于等于size的值，抛出异常 if(index >= this.size || index < 0){ throw new RuntimeException("index error index=" + index + " size=" + this.size) ; } } 复制代码 3.3.2 插入方法实现： 复制代码 @Override public boolean add(E e) { //:::插入新数据前进行扩容检查 expandCheck(); //;::在末尾插入元素 this.elements[this.size] = e; //:::size自增 this.size++; return true; } @Override public void add(int index, E e) { //:::插入时，数组下标越界检查 rangeCheckForAdd(index); //:::插入新数据前进行扩容检查 expandCheck(); //:::插入位置下标之后的元素整体向后移动一位(防止数据被覆盖，并且保证数据在数组中的下标顺序) //:::Tips: 比起for循环，System.arraycopy基于native的内存批量复制在内部数组数据量较大时具有更高的执行效率 for(int i=this.size; i>index; i--){ this.elements[i] = this.elements[i-1]; } //:::在index下标位置处插入元素"e" this.elements[index] = e; //:::size自增 this.size++; } 复制代码 插入方法——时间复杂度: 　　可以看到，向量的插入操作会导致插入位置之后的数据整体向后平移一位。 　　在这里，使用了for循环将数据一个一个的进行复制。事实上，由于数组中下标连续的数据段在内存中也是连续成片的(逻辑意义上的)，因此操作系统可以通过批量复制内存的方法来优化这种"数组中一片连续数据复制"的操作。java在jdk中自带的向量实现中采用了native的System.arraycopy()方法来实现这个优化操作。 　　在我的向量实现中，有多处这种"数组中一片连续数据复制"的操作，为了增强代码的可理解性，都使用了for循环这种较低效率的实现方式，希望能够理解。 　　虽然System.arraycopy能够优化这一操作的效率，但是在渐进的意义上，向量插入操作的时间复杂度为O(n)。 动态扩容： 　　前面我们提到，向量相比数组的一大改进就是向量能够在数据新增时根据存储的数据量进行动态的扩容，而不需要人工的干预。 向量扩容方法的实现： 复制代码 /** * 内部数组扩容检查 * */ private void expandCheck(){ //:::如果当前元素个数 = 当前内部数组容量 if(this.size == this.capacity){ //:::需要扩容 //:::先暂存之前内部数组的引用 Object[] tempArray = this.elements; //:::当前内部数组扩充 一定的倍数 this.capacity = (int)(this.capacity * EXPAND_BASE); //:::内部数组指向扩充了容量的新数组 this.elements = new Object[this.capacity]; //:::为了代码的可读性，使用for循环实现新老数组的copy操作 //:::Tips: 比起for循环，System.arraycopy基于native的内存批量复制在内部数组数据量较大时具有更高的执行效率 for(int i=0; i链表) ，意味着大量代码的推倒重写。 　　2. 缺少对容器遍历行为的抽象，导致重复代码的出现。这一问题必须在实现了多个数据结构容器之后才会体现出来。例如，上面提到的向量的toString方法中，如果将遍历内部数组的行为抽象出来，则可以使得多种不同的类型的数据结构容器复用同一个toString方法。 　　为此java在设计数据结构容器架构时，抽象出了Iterator接口，用于整合容器遍历的行为，并要求所有的容器都必须提供对应的Iterator接口。 Iterator接口设计： 　　1. hasNext() 　　　　接口定义：boolean hasNext(); 　　　　接口描述：当前迭代器 是否存在下一个元素。 　　2. next() 　　　　接口定义：E next(); 　　　　接口描述：获得迭代器 迭代的下一个元素。 　　3. remove() 　　　　接口定义：void remove(); 　　　　接口描述: 移除迭代器指针当前指向的元素 　　个人认为迭代器之所以加上了remove接口，是因为很多时候迭代的操作都伴随着删除容器内部元素的需求。由于删除元素会导致内部数据结构的变化，导致无法简单的完成遍历，需要使用者熟悉容器内部实现原理，小心谨慎的实现遍历代码。 　　而Iterator接口的出现，将这一问题带来的复杂度交给了容器的设计者，降低了用户使用数据结构容器的难度。 向量Iterator实现： 复制代码 /** * 向量 迭代器内部类 * */ private class Itr implements Iterator{ /** * 迭代器下一个元素 指针下标 */ private int nextIndex = 0; /** * 迭代器当前元素 指针下标 * */ private int currentIndex = -1; @Override public boolean hasNext() { //:::如果"下一个元素指针下标" 小于 "当前向量长度" ==> 说明迭代还未结束 return this.nextIndex < ArrayList.this.size; } @Override @SuppressWarnings("unchecked") public E next() { //:::当前元素指针下标 = 下一个元素指针下标 this.currentIndex = nextIndex; //:::下一个元素指针下标自增,指向下一元素 this.nextIndex++; //:::返回当前元素 return (E)ArrayList.this.elements[this.currentIndex]; } @Override public void remove() { //:::删除当前元素 ArrayList.this.remove(this.currentIndex); //:::由于删除了当前下标元素，数据段整体向前平移一位，因此nextIndex不用自增 //:::为了防止用户在一次迭代(next调用)中多次使用remove方法，将currentIndex设置为-1 this.currentIndex = -1; } } 复制代码 5.向量总结 　　5.1 向量的性能 　　　　空间效率：向量中空间占比最大的就是一个随着存储数据规模增大而不断增大的内部数组。而数组是十分紧凑的，因此向量的空间效率非常高。 　　　　时间效率：评估一个数据结构容器的时间效率，可以从最常用的增删改查接口来进行衡量。 　　　　我们已经知道，向量的增加、删除操作的时间复杂度为O(n)，效率较低；而向量的随机修改、查询操作效率则非常高，为常数的时间复杂度O(1)。对于有序向量，其查找特定元素的时间复杂度也能够被控制在O(logn)对数时间复杂度上。 　　　　因此向量在随机查询较多，而删除和增加较少的场景表现优异，但是并不适合频繁插入和删除的场景。 　　5.2 当前向量实现存在的缺陷 　　　　到这里，我们已经完成了一个最基础的向量数据结构。限于个人水平，以及为了代码尽可能的简单和易于理解，所以并没有做进一步的改进。 　　　　下面是我认为当前实现版本的主要缺陷： 　　　　1.不支持并发 　　　　java是一门支持多线程的语言，因此容器也必然会在多线程并发的环境下运行。 　　　　jdk的向量数据结构，Vector主要通过对方法添加synchronized关键字，用悲观锁来实现线程安全，效率较低。而另一个向量的实现，ArrayList则是采用了快速失败的，基于版本号的乐观锁对并发提供一定的支持。 　　　　2.没有站在足够高的角度构建数据结构容器的关系 　　　　java在设计自身的数据结构容器的架构时，高屋建瓴的设计出了一个庞大复杂的集合类型关系。这使得java的数据结构容器API接口非常的灵活，各种内部实现迥然不同的容器可以很轻松的互相转化，使用者可以无负担的切换所使用的数据结构容器。同时，这样的设计也使编写出抽象程度很高的API接口成为可能，减少了大量的重复代码。 　　　　3.接口不够丰富 　　　　限于篇幅，这里仅仅列举和介绍了主要的向量接口，还有许多常见的需求接口没有实现。其实，在理解了前面内容的基础之上，实现一些其它常用的接口也并不困难。 　　　　4.异常处理不够严谨 　　　　在当前版本的下标越界校验中，没有对容器可能产生的各种异常进行仔细的归类和设计，抛出的是最基础的RunTimeException，这使得用户无法针对容器抛出的异常类型进行更加细致的处理。 　　5.3 "自己动手实现java数据结构"系列博客后续 　　这是"自己动手实现java数据结构"系列的第一篇博客，因此选择了相对比较简单的"向量"数据结构入手。 　　我的目标并不在于写出非常完善的数据结构实现，而是尝试着用最易于接受的方式使大家熟悉常用的数据结构。如果读者能够在阅读这篇博客之后，在理解思路，原理的基础之上，自己动手实现一个初级，原始的向量数据结构，以及在此基础上进行优化，那么这篇博客的目标就完美达成啦。 　　本系列博客的代码在我的 github上：https://github.com/1399852153/DataStructures ，欢迎交流 0https://www.cnblogs.com/xiaoxiongcanguan/p/9977275.html