1. 线性表
线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列…
线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。
2. 顺序表
顺序表是一段物理空间连续的线性表,在底层一般使用数组来实现,在数组的基础上完成增删查改.下面是顺序表的一些接口.
2.1 接口
public interface Ilist { void add(int data);//为顺序表的尾部增加元素 void add(int data ,int pos);//为指定位置添加元素 void display();//打印顺序表 int size ();//检测顺序表中元素的个数 boolean contains(int toFind);//检测顺序表中是否包含该元素 int indexOf(int toFind);//返回所要寻找第一个元素的下标 int get(int index);//获取指定下标的元素 void set(int index,int val);//把指定下标的元素指定为指定元素 void remove(int toRomve);//移除第一个指定的元素 void clear();//清空顺序表 }
下面我们来实现这些接口:
import java.util.Arrays; /** * 顺序表底层是用数组来实现的 */ public class MyArrayList implements Ilist { private int[] elem; private int size;//记录有效数据 public static final int DEFAULT_CAPACITY = 5;//默认容量 private boolean isFull(){ return size == elem.length;//判断顺序表的容量是否为满 } private void checkPos(int pos){ if (pos < 0 || pos >= size){ throw new PosException("pos is false");//判断插入位置是否合法 } } private boolean isEmpty(){ return this.size == 0; } public MyArrayList() { this.elem = new int[DEFAULT_CAPACITY];//默认容量为5 this.size = 0; }//无参数的构造方法 public void add(int data){//在末尾的位置添加元素 if (isFull()){ elem = Arrays.copyOf(elem,elem.length*2);//扩容 } elem [size] = data; size++; } public void add(int data ,int pos){//在指定位置添加元素 checkPos(pos); if (isFull()){ elem = Arrays.copyOf(elem,elem.length*2);//扩容 } for (int i = size-1; i >= pos ; i--) {//数组整体后移 elem [i+1] = elem [i]; } elem[pos] = data; size++; } public void display(){//打印顺序表 System.out.print("["+" "); for (int i = 0; i < size; i++) {//打印有效元素 System.out.print(elem[i]+" "); } System.out.print("]"); } public int size (){//返回当前顺序表大小 return this.size; } public boolean contains(int toFind){ for (int i = 0; i < size; i++) {//在这里不可以用elem.length,后面的扩容之后未赋值 if(elem[i] == toFind){ return true; } } return false; } public int indexOf(int toFind){//返回要找的元素第一个返回的下标 for (int i = 0; i < size; i++) {//在这里不可以用elem.length,后面的扩容之后未赋值 if(elem[i] == toFind){ return i; } } return -1; } public int get(int index){//获取index位置的值 checkPos(index); if (isEmpty()){//存在默认容量5,若没有此方法,可能会在未初始化的位置上直接获取元素,获取成功 //但是为0,不符合实际 throw new EmptyException("array is empty"); } return elem[index]; } public void set(int index,int val){//把index位置的值改为val checkPos(index); if (isEmpty()){//存在默认容量5,若没有此方法,可能会在未初始化的位置上直接添加元素, //添加成功,但是不符合实际 throw new EmptyException("array is empty"); } elem[index] = val; } public void remove(int toRomve){//移除第一次出现的元素 if (isEmpty()){ throw new EmptyException("array is empty"); } int index = indexOf(toRomve);//先找到下标的位置 for (int i = index+1; i < size; i++) { elem[i-1] = elem[i]; } elem[size-1] = 0; size --; } public void clear(){ size = 0; } } public class EmptyException extends NullPointerException{ public EmptyException(String s) { super(s); } } public class PosException extends ArrayIndexOutOfBoundsException{ public PosException(String s) { super(s); } }
下面通过一些测试用例;来测试:
public class Main { public static void main(String[] args) { MyArrayList list = new MyArrayList(); list.add(0); list.add(1); list.add(3); list.add(4); list.add(2,2); list.add(5); list.display(); System.out.println(list.size()); list.remove(2); list.display(); System.out.println(list.size()); } }
3.ArrayList简介
[说明]
- ArrayList是以泛型的方式实现的,使用时必须先实例化.
- ArrayList的底层是一段连续的存储空间,并且可以动态扩容,是一个动态类型的顺序表.
4.ArrayList的使用
4.1 ArrayList的构造方法
方法 | 解释 |
---|---|
public ArrayList() | 无参构造方法 |
public ArrayList(int initialCapacity) | 指定顺序表初始容量 |
public ArrayList(Collection extends E> c) | 利用Collection中的容器来构造 |
关于第三个构造方法,不太好理解,我们下面来解释一下:ArrayList已经传入了泛型的参数,就是E,这里用来构造ArrayList的Collection类中的元素必须是E的子类.
ArrayListlist = new ArrayList<>(); ArrayList list1 = new ArrayList<>(list); ArrayList list2 = new ArrayList<>(list); ArrayList list3 = new ArrayList<>(10);
4.2 ArrayList常见操作
方法 | 解释 |
---|---|
boolean add(E e) | 在尾部添加元素 |
void add(int index,E element) | 在指定位置添加元素 |
boolean addAll(Collection extends E> c) | 把c中的元素全部添加到顺序表尾部 |
E remove(int index) | 移除指定位置的元素 |
boolean remove(Object o) | 移除遇到的第一个元素o |
E get(int index) | 获取指定位置的元素 |
E set(int index,E element) | 把指定位置的元素设置为指定的值 |
void clear() | 清空顺序表 |
boolean contains(Object o) | 检测顺序表中是否包含o |
int indexOf(Object o) | 返回第一个指定元素所在的下标 |
int lastIndexOf(Object o) | 从后向前找,返回第一个元素所在的下标 |
List subList(int fromIndex,int toIndex) | 截取指定范围的字符串,左闭右开 |
在这里说明一下两个remove方法的区别,避免混淆,第一个remove方法时移除指定位置的元素,传入的元素类型为int类型的数据,而第二个remove方法移除的是第一个遇到的元素,这里传入的参数类型是和顺序表泛型相同的类型,当一个顺序表中存储的是Integer类型的数据的时候,要注意区分下标和元素.
下面对上述方法进行演示:
public static void main(String[] args) {Listlist = new ArrayList<>(); list.add("JavaSE"); list.add("JavaWeb"); list.add("JavaEE"); list.add("JVM"); list.add("测试课程"); System.out.println(list); // 获取list中有效元素个数 System.out.println(list.size()); // 获取和设置index位置上的元素,注意index必须介于[0, size)间 System.out.println(list.get(1)); list.set(1, "JavaWEB"); System.out.println(list.get(1)); // 在list的index位置插入指定元素,index及后续的元素统一往后搬移一个位置 list.add(1, "Java数据结构"); System.out.println(list); // 删除指定元素,找到了就删除,该元素之后的元素统一往前搬移一个位置 list.remove("JVM"); System.out.println(list); // 删除list中index位置上的元素,注意index不要超过list中有效元素个数,否则会抛出下标越界异常 list.remove(list.size()-1); System.out.println(list); // 检测list中是否包含指定元素,包含返回true,否则返回false if(list.contains("测试课程")){list.add("测试课程"); } // 查找指定元素第一次出现的位置:indexOf从前往后找,lastIndexOf从后往前找 list.add("JavaSE"); System.out.println(list.indexOf("JavaSE")); System.out.println(list.lastIndexOf("JavaSE")); // 使用list中[0, 4)之间的元素构成一个新的SubList返回,但是和ArrayList共用一个elementData数组 List ret = list.subList(0, 4); System.out.println(ret); list.clear(); System.out.println(list.size()); }
4.3 ArrayList的遍历
ArrayList有四种遍历方式,一种是通过sout直接输出,一种是for-i,一种是for-each,一种是使用迭代器.
import java.util.ArrayList; import java.util.Iterator; public class TestArrayList { public static void main(String[] args) { ArrayListlist = new ArrayList<>(); list.add(1); list.add(2); list.add(3); list.add(4); list.add(5); //通过sout去遍历ArrayList System.out.println(list); //通过fori遍历 for (int i = 0; i < list.size(); i++) { System.out.print(list.get(i)+" "); } System.out.println(); //通过foreach遍历 for (int x:list) { System.out.print(x+" "); } System.out.println(); //通过迭代器遍历 Iterator iterator = list.iterator(); while (iterator.hasNext()){ System.out.print(iterator.next()+" "); } System.out.println(); } }
4.4 ArrayList扩容机制
ArrayList是动态的顺序表,在顺序表的容量不够的时候会自动扩容,下面是底层代码对ArrayList的扩容机制.
public boolean add(E e) { modCount++;//底层是C/C++代码 add(e, elementData, size);//调用另一个重载的add方法,指定添加容积 return true; } private void add(E e, Object[] elementData, int s) { if (s == elementData.length)//容器满的时候需要扩容 elementData = grow();//调用grow方法扩容 elementData[s] = e; size = s + 1; } private Object[] grow() { return grow(size + 1);//最小容积是size+1,就是指定的添加容积+1 } private Object[] grow(int minCapacity) {//传入指定的最小容积 int oldCapacity = elementData.length; if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { int newCapacity = ArraysSupport.newLength(oldCapacity,//对数组扩容 minCapacity - oldCapacity, /* minimum growth */ //计算原容量和最小容积的差值 oldCapacity >> 1 //原容量的一半 /* preferred growth */); return elementData = Arrays.copyOf(elementData, newCapacity);//正式扩容 } else { return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)]; } } public static int newLength(int oldLength, int minGrowth, int prefGrowth) { // preconditions not checked because of inlining // assert oldLength >= 0 // assert minGrowth > 0 int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow //若pre大,1.5被扩容,若是min大,直接加上指定的最小容积 if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) { return prefLength; } else { // put code cold in a separate method return hugeLength(oldLength, minGrowth); } }
[总结]
- 预估要扩容的大小
- 初步预估按照1.5倍扩容.
- 如果用户所需大小预估超过1.5,则按照用户所需大小扩容.
- 使用copyOf扩容.