静态数组与动态数组

增删元素的话，线性结构要保证元素的连续性

动态数组是顺序存储结构具体实现的核心思想

线性表的定义

• a1是a2的直接前驱
• a2是a1的直接后继
• 除了第一个元素a1以外，其他元素都有唯一的直接前驱
• 除了最后一个元素an以外，其他元素都有唯一的直接后继
• n表示线性表的长度，当n=0，称为空表

List接口的定义

因为线性结构可以有顺序存储结构和链式存储结构实现，那么我i吗就可以把对线性结构的共同操作进行抽取，定义出线性结构的接口

public interface List <E> extends Iterable<E>{public void add(E element);public void add(int index,E element);public void remove(E element);public E remove(int index);public E set(int index,E element);public E get(int index);//获取元素个数public int size();public int indexOf(Eelement);public boolean contains(E element);public boolean isEmpty();public void clear();/** * 根据比较器定义的比较规则来进行比较大小 */public void sort(Comparator<E> c);public List<E> subList(int fromIndex,int toIndex);}

ArrayList及其方法的实现

属性

构造器

把数组转换为线性表的方法

判断是否需要扩容和缩容问题

扩容

缩容

添加元素的方法

删除元素的方法

修改元素的值

@Overridepublic E set(int index, E element) {if (index < 0 || index >= size) {throw new IllegalArgumentException("set index out of bounds");}E old = data[index];data[index] = element;return old;}

获取元素的值

 @Overridepublic E get(int index) {if (index < 0 || index >= size) {throw new IllegalArgumentException("get index out of bounds");}return data[index];}

获取线性表元素个数

@Overridepublic int size() {return size;}

获取线性表中数组容量

public int getCapacity() {return data.length;}

获取元素在线性表下标

@Overridepublic int indexOf(E element) {for (int i = 0; i < size; i++) {if (element.equals(data[i])) {return i;}}return -1;}

判断是否包含某个元素

@Overridepublic boolean contains(E element) {return indexOf(element) != -1;}

判断线性表是否为空

@Overridepublic boolean isEmpty() {return size == 0;}

清空线性表

@Overridepublic void clear() {for (int i = 0; i < data.length; i++) {data[i] = null;}size = 0;}

返回子线性表

 /** * [formIndex,toIndex] * 要判断索引是否有效 * 根据索引，来返回子线性表 * * @param fromIndex * @param toIndex * @return */@Overridepublic List<E> subList(int fromIndex, int toIndex) {if (fromIndex < 0 || fromIndex >= size) {throw new IllegalArgumentException("角标越界");}if (toIndex < 0 || toIndex >= size) {throw new IllegalArgumentException("角标越界");}if (fromIndex > toIndex) {throw new IllegalArgumentException("角标越界");}ArrayList<E> subList = new ArrayList<>();for (int i = fromIndex; i < toIndex; i++) {subList.add(data[i]);}return subList;}

判断两个线性表是否相等

打印线性表的不同方式

@Overridepublic String toString() {StringBuilder builder = new StringBuilder(String.format("ArrayList:%d/%d[", size, data.length));if (isEmpty()) {builder.append("]");//ArrayList:0/10;} else {for (int i = 0; i < size; i++) {builder.append(data[i]);if (i != size - 1) {builder.append(",");} else {builder.append("]");}}}return builder.toString();}/** * 获取ArrayList的迭代器，foreach遍历线性表it.hasNext(),it.next()来遍历 * * @return */@Overridepublic Iterator<E> iterator() {return new ArrayListIterator();}class ArrayListIterator implements Iterator<E>{/** * 判断之后是否有元素 * @return */private int cur=0;@Overridepublic boolean hasNext() {return cur<size;}/** * 如果后面一个元素存在，则先把元素返回再把指针后移 * @return */@Overridepublic E next() {return data[cur++];}}

测试