数组线性表ArrayList的内部实现

线性表是按顺序存储数据是常用的一种数据结构。大多数线性表的典型操作是：

1，初始化线性表

2，判断表是否为空

3，求线性表的长度

4，读取线性表中的第i个元素

5，查找满足条件的数据元素

6，在线性表的第i个位置之前插入一个新的数据元素

7，删除线性表中的第i个数据元素

8，表置空

9，查找第i个元素的前驱或后继

10，按一个或多个数据项递增或递减重新排列数据元素

数组线性表是顺序存储结构，是最简单，最常用的数据结构。是在内存中开辟一片连续的存储空间，用一组连续的存储单元一次存放数据元素。顺序存储的特点是逻辑上相邻的数据元素，它们物理位置也是相连的。

优点是：简单，直观，随机存取元素十分容易实现，根据定位公式很容易找到表中每个元素的存储位置，所以指定第i个结点很方便

缺点是：插入和删除结点困难，算法效率不高。因为结点是顺序存放的，所以插入或删除一个结点时，必须将该结点以后的所有元素依次向后移动，或者依次向前移动。

JDK1.5以后ArrayList开始引入泛型

接口MyList<E>有操作线性表的基本方法，MyAbstractList<E>抽象类实现了MyList<E>接口，但是该抽象类只是实现了接口中的部分方法，MyArrayList<E>继承扩展抽象类MyAbstractList<E>抽象类

接口MyList<E>

public interface MyList<E> {//添加一个元素public void add(E e);//在index处添加一个元素public void add(int index,E e);//清楚一个list列表public void clear();//删除一个元素public boolean remove(E e);//删除并返回index处的元素public E remove(int index);//index处的元素设置为元素epublic Object set(int index,E e);//判断是否包含元素epublic boolean contains(E e);//返回index处的元素public E get(int index);//返回列表中第一个与元素e匹配的下标indexpublic int indexOf(E e);//返回列表中最后一个与元素e匹配的元素下标indexpublic int lastIndeOf(E e);//判断列表是否为空public boolean isEmpty();//返回列表的大小public int size(); } MyAbstractList<E>抽象类

public abstract class MyAbstractList<E> implements MyList<E> {//部分实现MyList接口protected int size=0; protected MyAbstractList(){}protected MyAbstractList(E[] objects){for(int i=1;i<objects.length;i++)add(objects[i]);}@Overridepublic void add(E e){add(size,e);}@Overridepublic void add(int index,E e){}@Overridepublic boolean isEmpty(){return size==0;}@Overridepublic int size(){return size;}@Overridepublic boolean remove(E e){if(indexOf(e)>=0){remove(indexOf(e));return true;}else return false;}@Overridepublic E remove(int index){return null;}@Overridepublic void clear() {// TODO Auto-generated method stub}@Overridepublic Object set(int index, E e) {// TODO Auto-generated method stubreturn null;}@Overridepublic boolean contains(E e) {// TODO Auto-generated method stubreturn false;}@Overridepublic E get(int index) {// TODO Auto-generated method stubreturn null;}@Overridepublic int indexOf(E e) {// TODO Auto-generated method stubreturn 0;}@Overridepublic int lastIndeOf(E e) {// TODO Auto-generated method stubreturn 0;} } MyArrayList<E>
public class MyArrayList<E> extends MyAbstractList<E> {public static final int INITIAL_CAPACITY=16;private E[] data=(E[])new Object[INITIAL_CAPACITY];public MyArrayList(){}public MyArrayList(E[] objects){for(int i=0;i<objects.length;i++)add(objects[i]);}public void add(int index,E e){ensureCapacity();for(int i=size-1;i>=index;i--)data[i+1]=data[i];data[index]=e;size++; }private void ensureCapacity() {if(size>=data.length){E[] newData=(E[])(new Object[size*2+1]);System.arraycopy(data, 0, newData, 0, size);data=newData;}}public void clear(){data=(E[])new Object[INITIAL_CAPACITY];size=0;}public boolean contains(E e){for(int i=0;i<size;i++){if(e.equals(data[i])) return true; }return false;}public E get(int index){return data[index];}public int indexOf(E e){for(int i=0;i<size;i++)if(e.equals(data[i])) return i;return -1;}public int lastIndexOf(E e){for(int i=size-1;i>=0;i--)if(e.equals(data[i])) return i;return -1;}public E remove(int index){E e=data[index];for(int j=index;j<size-1;j++)data[j]=data[j+1];data[size-1]=null;size--;return e;}public E set(int index,E e){E old=data[index];data[index]=e;return old;}public String toString(){StringBuilder result=new StringBuilder("[");for(int i=0;i<size;i++){result.append(data[i]);if(i<size-1) result.append(",");}return result.toString()+"]";}public void trimToSize(){if(size!=data.length){E[] newData=(E[])new Object[size];System.arraycopy(data, 0, newData, 0, size);data=newData;}} }

总结

以上是生活随笔为你收集整理的数组线性表ArrayList的内部实现的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。