静态数组与动态数组
线性表的定义
List接口的定义
ArrayList及其方法的实现
属性
构造器
把数组转换为线性表的方法
判断是否需要扩容和缩容问题
添加元素的方法
删除元素的方法
修改元素的值
获取元素的值
获取线性表元素个数
获取线性表中数组容量
获取元素在线性表下标
判断是否包含某个元素
判断线性表是否为空
清空线性表
返回子线性表
判断两个线性表是否相等
打印线性表的不同方式
测试

📃个人主页:不断前进的皮卡丘
🌞博客描述:梦想也许遥不可及，但重要的是追梦的过程，用博客记录自己的成长，记录自己一步一步向上攀登的印记
🔥网站推荐：千里之行，始于足下。每天坚持刷题，巩固所学知识，也为将来找工作，面试做好准备-----刷题神器

静态数组与动态数组

在这里插入图片描述

增删元素的话，线性结构要保证元素的连续性
在这里插入图片描述

动态数组是顺序存储结构具体实现的核心思想
在这里插入图片描述

线性表的定义

在这里插入图片描述

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(E  element);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++];}}