线性表
线性表性质
当插入元素时，需要将插入位置给腾出来，也就是将后面的所有元素向后移，同样的，如果要删除元素，那么也需要将所有的元素向前移动，顺序表是紧凑的，不能出现空位
线性表的基本属性
public class ArrayList<E>泛型E，因为表中要存的具体数据类型待定
capacity'当前线性表的的容量
public int getCapacity() { //获取当前存放的元素数量
return capacity;
}
size当前已存放的元素数量
public int size() { //获取当前存放的元素数量
return size;
}
private Object[] arr = new Object[capacity]; 底层存放数据的数组;使用Object是因为线性表的存储数据类型都不确定
线性表插入
- 插入方法需要"插入的值"和"索引位置"
- 利用for循环进行线性表的移位; 从已存放的最后元素的索引号开始移后1位,直到index位后,插入element
public void add(E element, int index) { //插入方法需要支持在指定下标位置插入
for (int i = size; i > index; i--) //从后往前，一个一个搬运元素
arr[i] = arr[i - 1];
arr[index] = element; //腾出位置之后，直接插入元素放到对应位置上
size++; //插入完成之后，记得将size自增
}
- 插入element时,我们需要判断是否在0~size(因为线性表是紧凑的;允许插入的位置只能是 [0, size] 这个范围内)
public void add(E element, int index) {
if (index < 0 || index > size) //插入之前先判断插入位置是否合法
throw new IndexOutOfBoundsException("插入位置非法，合法的插入位置为：0 ~ " + size);
for (int i = size; i > index; i--)
arr[i] = arr[i - 1];
arr[index] = element;
size++;
}
- 为了让线性表更智能, 加入了扩容功能
capacity>>1移1位;是除2arraycopy快速拷贝原数组内容到新的数组
public void add(E element, int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("插入位置非法，合法的插入位置为：0 ~ " + size);
if (capacity == size) {
int newCapacity = capacity + (capacity >> 1); //扩容规则就按照原本容量的1.5倍来吧 右移1位==除2
Object[] newArray = new Object[newCapacity]; //创建一个新的数组来存放更多的元素
System.arraycopy(arr, 0, newArray, 0, size); //使用arraycopy快速拷贝原数组内容到新的数组
arr = newArray; //更换为新的数组
capacity = newCapacity; //容量变成扩容之后的
}
for (int i = size; i > index; i--)
arr[i] = arr[i - 1];
arr[index] = element;
size++;
}
线性表删除
-
E e = (E) arr[index];是将要删除的元素赋值给e,最后return回给我们,让我们知道删除元素的值 -
利用for循环进行线性表的移位; 从参数的索引号开始移前1位,直到size位
-
删除元素时,我们需要判断是否在0~size-1(因为线性表是紧凑的;删除的位置只能是 [0, size-1] 这个范围内,需要往前移位所以不用到size)
public E remove(int index) {
if (index < 0 || index > size - 1)
throw new IndexOutOfBoundsException("删除位置非法，合法的插入位置为：0 ~ " + (size - 1));
E e = (E) arr[index];
for (int i = index; i < size; i++)
arr[i] = arr[i + 1];
size--;
return e;
}
线性表更新
arr[index] = element;直接对线性表中的索引号进行重新赋值
public void setarray(int index, E element) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("更新位置非法，合法的插入位置为：0 ~ " + (size));
arr[index] = element;
}
线性表查找
- 直接返回线性表index对应的元素
public E getElement(int index) {
if (index < 0 || index > size) //在查找之前同样要进行范围检查
throw new IndexOutOfBoundsException("非法的位置，合法的位置为：0 ~ " + (size));
return (E) arr[index]; //直接返回就完事
}
线性表toString
- 使用Builder模式, 但也可以使用普通的"sout"
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("当前顺序表元素长度: ").append(size()).append(" ").append("\n");
builder.append("当前顺序表全部长度: ").append(getCapacity()).append(" ").append("\n");
builder.append('[');
for (int i = 0; i < size; i++) builder.append(' ').append(arr[i]).append(" ");
builder.append(']');
return builder.toString();
}
总代码
-
Main代码
import ClassStudy.ArrayList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
ArrayList<Integer> list = new ArrayList<>();
//list.add(10, 1); 一上来只能在第一个位置插入，第二个位置肯定是非法的
System.out.print("输入顺序表的长度: ");
int lengthOflist = input.nextInt();
System.out.println("输入元素(以空格隔开元素): ");
for (int i = 0; i < lengthOflist; i++) {
list.add(input.nextInt(), i);
if (i == lengthOflist - 1) System.out.println("已输入完毕");
}
System.out.println(list);
System.out.println("===================================================");
System.out.print("选择是否删除顺序表中的元素(Yy/Nn): ");
Scanner scanner = new Scanner(System.in);
String Choice = scanner.nextLine();
if (Choice.equals("Y") || Choice.equals("y")) {
System.out.print("输入需要删除的索引位置(以0号开始): ");
list.remove(scanner.nextInt());
}
System.out.println(list);
System.out.println("===================================================");
System.out.print("选择是否更新顺序表中的元素(Yy/Nn): ");
Scanner choice_Put = new Scanner(System.in);
String choicePut = choice_Put.nextLine();
if (choicePut.equals("Y") || choicePut.equals("y")) {
System.out.print("输入需要更新的索引位置(以0号开始)和元素: ");
list.setarray(choice_Put.nextInt(), choice_Put.nextInt());
}
System.out.println("===================================================");
System.out.print("选择是否查询顺序表中的元素(Yy/Nn): ");
Scanner choice_1 = new Scanner(System.in);
String choice_2OB = choice_1.nextLine();
if (choice_2OB.equals("Y") || choice_2OB.equals("y")) {
System.out.print("输入需要查询的索引位置(以0号开始): ");
System.out.println(list.getElement(choice_1.nextInt()));
}
}
}
-
ArrayList类
package ClassStudy;
public class ArrayList<E> { //泛型E，因为表中要存的具体数据类型待定
int capacity = 10; //当前顺序表的容量
int size = 0; //当前已经存放的元素数量
private Object[] arr = new Object[capacity]; //底层存放数据的数组
//插入
public void add(E element, int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("插入位置非法，合法的插入位置为：0 ~ " + size);
if (capacity == size) {
int newCapacity = capacity + (capacity >> 1); //扩容规则就按照原本容量的1.5倍来吧 右移1位==除2
Object[] newArray = new Object[newCapacity]; //创建一个新的数组来存放更多的元素
System.arraycopy(arr, 0, newArray, 0, size); //使用arraycopy快速拷贝原数组内容到新的数组
arr = newArray; //更换为新的数组
capacity = newCapacity; //容量变成扩容之后的
}
for (int i = size; i > index; i--)
arr[i] = arr[i - 1];
arr[index] = element;
size++;
}
//删除
@SuppressWarnings("unchecked")//屏蔽未经检查警告
public E remove(int index) {
if (index < 0 || index > size - 1)
throw new IndexOutOfBoundsException("删除位置非法，合法的插入位置为：0 ~ " + (size - 1));
E e = (E) arr[index];
for (int i = index; i < size; i++)
arr[i] = arr[i + 1];
size--;
return e;
}
//更新
public void setarray(int index, E element) {
if (index < 0 || index > size )
throw new IndexOutOfBoundsException("更新位置非法，合法的插入位置为：0 ~ " + (size));
arr[index] = element;
}
//查找
@SuppressWarnings("unchecked")//屏蔽未经检查警告
public E getElement(int index) {
if (index < 0 || index > size) //在查找之前同样要进行范围检查
throw new IndexOutOfBoundsException("非法的位置，合法的位置为：0 ~ " + (size));
return (E) arr[index]; //直接返回就完事
}
public int size() { //获取当前存放的元素数量
return size;
}
public int getCapacity() { //获取当前存放的元素数量
return capacity;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("当前顺序表元素长度: ").append(size()).append(" ").append("\n");
builder.append("当前顺序表全部长度: ").append(getCapacity()).append(" ").append("\n");
builder.append('[');
for (int i = 0; i < size; i++) builder.append(' ').append(arr[i]).append(" ");
builder.append(']');
return builder.toString();
}
}