- List接口是由多个类实现的：1、ArrayList类 2、LinkedList类 3、Vector类（通过Stack类实现）
- 学习List接口：1、学习ArrayList类 -> 2、学习顺序表 -> 3、学习线性表
1、线性表
- 定义：相同特性数据元素的有限序列，线性表就是一种数据结构；
- 常见的线性表：顺序表、链表、栈、队列…
- 线性表在逻辑上是线性结构，也就是说在逻辑上是连续存储的；但是在物理结构上就不一定连续存储；
2、顺序表
- 顺序表就是在物理结构上连续存储的一种线性结构；
- 顺序表是采用数组进行存储数据的，所以是连续存储；
- 顺序表中主要实现的功能就是对数据进行增删改查，也就是对数组进行增删改查；
-> 为什么不直接使用数组进行存储呢？
- 数组并不能实现一些特有功能
- 顺序表就是在数组的基础上增加一些特有的功能和方法
- 将带有特有功能的数组，组织成一种新的数据类型，这个新数据类型就是顺序表
- 顺序表是一种新的数据类型，这种新的类型是用来操作数组的；
顺序表的实现（MyArrayList）
- 我们在写这个顺序表时，首先要明白顺序表是什么；
- 顺序表中主要实现的功能就是对数据进行增删改查，也就是对数组进行增删改查；
- 我们需要通过三方面进行编写代码：1、MyArrayList类（也就是顺序表类） 2、ArrayListInterface接口（也就是功能接口） 3、异常类，所以代码大的分为了这三部分；
1、MyArrayList类
重点、难点：新增方法
重点、难点：删除方法
MyArrayList代码：
package ArrayList;
import java.util.Arrays;
/**
* 顺序表就是使用数组实现的，只是有一些特有的功能
* 1、先要有一个数组
* 2、获取到顺序表的长度->这个长度就是数组使用长度
* 3、打印顺序表->遍历数组
* 4、新增元素->注意：新增完元素后一定要将useSize++
* 5、判断当前位置是否合法->不合法应该抛出异常
* 6、查找元素、获取元素下标、获取元素
* 7、删除元素->1、判断顺序表是否为空；2、查找元素下标；3、从前向后依次覆盖
* 8、清空顺序表
*/
public class MyArrayList implements ArrayListInterface{
public int[] array; // 定义的数组
public int useSize; // 数组使用的大小
public static final int DEFAULT_CAPACITY = 10; // 数组默认大小10
// 初始化
public MyArrayList() {
// 将数组初始化
this.array = new int[DEFAULT_CAPACITY]; // 初始化数组
}
@Override
public int size() {
// 因为是数组使用长度，并且使用长度是公开的,所以直接返回
return useSize;
}
@Override
public void display() {
// 打印顺序表
// 也就是遍历顺序
for (int i = 0; i < size(); i++) {
// 将数组中的所有元素打印出来
System.out.print(array[i] + " ");
}
System.out.println();
}
@Override
public void add(int data) {
// 增加元素，默认增加到数组的最后位置
// 1、数组是否满 -> 所以先写isFull
if(isFull()) {
// 满了进行扩容
array = Arrays.copyOf(array,array.length);
}
// 满了之后会进行新增元素,没满也会进行新增元素,所以新增元素写在外面
// 将useSize位置放上这个元素
array[useSize] = data;
// 新增一个元素之后需要将useSize++
useSize++;
}
@Override
public boolean isFull() {
// 判断一下，数组是否满
// 满了并不代表数组越界，所以这里的判断应该是==
// 我最开始写的是>=
if(useSize == array.length) {
return true; // 如果满了，返回true
}
return false; // 没满返回false
}
@Override
public boolean isEmpty() {
// 判断是否为空
// 顺序表中没有任何元素时则为空
if(useSize == 0) {
return true;
}
return false;
}
@Override
public void checkPosInAdd(int pos) {
// 判断当前位置是都合法
// 当前的下标小于0，大于数组长度 -> 这样考虑是有缺陷的，如果当前位置前面是null，那么就不能新增元素的；
// 所以当前位置大于的不是数组长度，而是大于useSize+1处就不能新增元素了
if(pos < 0 || pos > size()) {
// 其实不合法应该抛出异常的
// System.out.println(pos + "当前位置不合法");
throw new PosException(pos + "当前位置不合法");
}
System.out.println(pos + "当前位置合法");
}
@Override
public void add(int pos, int data) {
// 在特定位置新增元素
// 当前位置是否合法?
// 如果数组是满的呢？
checkPosInAdd(pos);
if(isFull()) {
array = Arrays.copyOf(array,array.length);
}
// 位置合法情况下
// 在此位置处，需要先将元素向后移动
// 这里有一个细节useSize-1，下标比长度少1
for (int i = useSize-1; i >= pos; i--) {
// 从后向前移动元素
// 将前一个元素放到后一个元素的位置
array[i+1] = array[i];
}
// 新增元素
// 最后useSize++
array[pos] = data;
useSize++;
}
@Override
public boolean contains(int data) {
// 查找当前元素是否存在
for (int i = 0; i < size(); i++) {
if(array[i] == data) {
return true;
}
}
return false;
}
@Override
public int indexOf(int data) {
// 返回的是当前值的下标
for (int i = 0; i < size(); i++) {
if(array[i] == data) {
return i; // 存在返回下标
}
}
return -1; // 不存在返回-1
// 数组中没有-1这个下标
}
@Override
public int get(int pos) {
// 获取特定位置的元素
// 判断位置是否合法
checkPosInAdd(pos);
// 最开始我写的时候，少了一个判断条件
// 如果这个顺序表为空，就没有获取到任何元素
if(isEmpty()) {
// 如果顺序表为空，抛出异常
throw new EmptyException("顺序表为空");
}
// 合法情况,直接返回该位置元素
return array[pos];
}
@Override
public void set(int pos, int value) {
// 给特定位置更新元素值
// 判断位置是否合法
checkPosInAdd(pos);
// 这是给已经有值的位置更新值
// 如果顺序表为空就没法更新
if(isEmpty()) {
// 如果顺序表为空，抛出异常
throw new EmptyException("顺序表为空");
}
// 合法情况,直接返回该位置元素
array[pos] = value;
}
@Override
public void remove(int key) {
// 1、顺序表是否为空
// 2、查找要删除数的下标
// 3、从前向后一次覆盖
if(isEmpty()) {
throw new EmptyException("顺序表为空");
}
int pos = indexOf(key); // 查找key元素的下标
// 找到key元素下标后，进行删除元素
// 删除元素：当前下标，从前向后依次覆盖
for (int i = pos; i < size()-1; i++) {
// 后一个元素覆盖前一个元素
array[i] = array[i+1];
}
// 删除之后useSize--
useSize--;
}
@Override
public void clear() {
// 清空顺序表，防止内存泄漏
// 将每一个对象都置为null
// 因为这里的对象全都是int类型
// 所以只需要将useSize置为0
useSize = 0;
}
}
2、 ArrayListInterface接口
size() -> 获取顺序表的长度，这个长度是顺序表的使用长度
display() -> 打印顺序表
add() -> 新增元素，默认新增到顺序表的最后
isFull() -> 判断当前顺序表是否满
isEmpty() -> 判断当前顺序表是否为空
checkPosInAdd() -> 判断当前位置是否合法
contains() -> 查看顺序表中是否包含某个元素
indexOf() -> 根据元素返回下标
get() -> 根据位置返回元素
set() -> 更新某个下标的值
remove() -> 删除第一次出现的某个元素
clear() -> 清空顺序表
ArrayListInterface代码：
package ArrayList;
/**
* 顺序表中的功能
* 这些接口中的功能都需要类去实现
*/
public interface ArrayListInterface {
// 获取顺序表的长度->这个长度是使用长度
int size();
// 打印顺序表
// 根据useSize判断
void display();
// 新增元素
// 默认新增到数组的最后
void add(int data);
// 判断当前顺序表是否满
boolean isFull();
// 判断当前顺序小是否为空
boolean isEmpty();
// 判断当前位置是否合法
void checkPosInAdd(int pos);
// 在特定位置新增元素
// 实现了方法的重载
void add(int pos, int data);
// 查找是否包含某个元素
boolean contains(int data);
// 查找某个元素对应位置
int indexOf(int data);
// 获取特定位置的元素
int get(int pos);
// 给特定位置元素更新新值
void set(int pos, int value);
// 删除第一次出现的某个值
void remove(int key);
// 清空顺序表
void clear();
}
3、异常类
1、PosException代码：
package ArrayList;
public class PosException extends RuntimeException{
// PosException是一个运行时异常
// 写一个构造方法(有参数、无参数)
public PosException(){
}
public PosException(String message){
super(message); // 调用父类
}
}
2、EmptyException代码：
package ArrayList;
public class EmptyException extends RuntimeException{
public EmptyException(){
}
public EmptyException(String message){
super(message);
}
}
认识顺序表 （ArrayList）
ArrayList的构造方法
// 在学习一个类时，首先学习这个类的构造方法
ArrayList<Integer> arrayList = new ArrayList<>(); // 实例化不带参数的构造方法
System.out.println("实例化不带参数的构造方法");
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
System.out.println("--------------------------------------------------------------------------");
ArrayList<Integer> arrayList1 = new ArrayList<>(10); // 这是实例化带参数的构造方法
System.out.println("实例化带参数的构造方法，为内存分配空间");
arrayList.add(10);
arrayList.add(20);
arrayList.add(30);
System.out.println("--------------------------------------------------------------------------");
ArrayList<Integer> arrayList2 = new ArrayList<>(arrayList);
System.out.println("这是带参数的构造方法");
System.out.println("可以这样实例化的原因是：");
System.out.println("1、后面括号中arrayList这个类是Collection的子类；");
System.out.println("2、arrayList这个类的类型是Integer;");
System.out.println("3、E是Integer类型，arrayList这个类的类型是E这个类或这个是E的子类都可以");
System.out.println("--------------------------------------------------------------------------");ArrayList的输出
// 顺序表的输出
System.out.println("顺序表没有具体的方法实现顺序表的输出，可以通过以下方法进行输出：");
// sout
System.out.println("sout输出顺序表");
System.out.println(arrayList2);
System.out.println("--------------------------------------------------------------------------");
// fori
System.out.println("fori输出顺序表");
for (int i = 0; i < arrayList2.size(); i++) {
// 这样输出是错的，这是顺序表，不是数组；顺序表是使用数组实现的
// System.out.println(arrayList2[i]);
System.out.print(arrayList2.get(i) + " ");
}
System.out.println();
System.out.println("--------------------------------------------------------------------------");
// foreach
System.out.println("foreach输出顺序表");
for (Integer x:arrayList2) {
System.out.print(x + " ");
}
System.out.println();
System.out.println("--------------------------------------------------------------------------");
// 迭代器输出顺序表
System.out.println("迭代器输出顺序表");
System.out.println("因为：顺序表是Iterable这个接口的子类，所以可以使用迭代器进行输出");
System.out.println("iterator()这个方法的返回值是Iterator<E>");
Iterator<Integer> y = arrayList2.iterator();
while(y.hasNext()) {
// 判断y的下一个位置是否有值
System.out.print(y.next() + " "); // 输出y的下一个值
}
System.out.println();
System.out.println("listIterator()这个方法的返回值是ListIterator<E>");
ListIterator<Integer> z = arrayList2.listIterator();
while(z.hasNext()) {
// 判断z的下一个位置是否有值
System.out.print(z.next() + " "); // 输出z的下一个值
}
System.out.println();
System.out.println("--------------------------------------------------------------------------");ArrayList的方法（subList）
// ArrayList中的subList方法
System.out.println("subList：左闭右开的方法，实现的是顺序表的截取");
System.out.println("但是subList这个方法并没有开辟新的空间，而是指向所截取顺序表的空间");
System.out.println("subList()这个方法的返回值是List<E>, 所以需要使用List<E>接收");
System.out.println();
System.out.print("这是从arrayList2这个顺序表截取的值，输出list：");
List<Integer> list = arrayList2.subList(0,2);
System.out.println(list);
System.out.print("修改截取后的值，将下标为0处修改为111，输出修改后的list：");
list.set(0,111);
System.out.println(list);
System.out.print("输出顺序表arrayList2：");
System.out.println(arrayList2);
System.out.println("说明：subList这个方法并没有开辟新的空间，而是指向所截取顺序表的空间");
System.out.println("--------------------------------------------------------------------------");3、链表
- 链表就是在逻辑上连续，但是物理结构上不一定连续的一种线性结构；
- 链表是通过每个结点组成，每个结点都有地址，说明结点是一个对象；
- 链表元素的逻辑顺序是通过链表中的引用链接实现的；
-> 链表的分类
- 单向带头非循环
- 单向不带头非循环
- 单向带头循环
- 单向不带头循环
- 双向带头非循环
- 双向不带头非循环
- 双向带头循环
- 双向不带头循环
- 链表也是一种数据结构，数据结构的最终目的是为了存储数据；
链表的实现（MyLinkedList）
单向不带头非循环链表
1、MyLinkedList类
2、LinkedListInterface接口
addFirst -> 头插法 addLast -> 尾插法 addIndex -> 在指定位置插入元素 contains -> 指定元素是否存在于链表中 remove -> 删除指定元素 removeAllKey -> 删除所有指定元素 size-> 求链表的结点数 clear-> 清空链表 display-> 打印链表
LinkedListInterface代码：
package linkedlist;
public interface LinkedListInterface {
// 头插法
void addFirst(int data);
// 尾插法
void addLast(int data);
// 在指定位置插入元素
void addIndex(int index, int data);
// 指定元素是否存在于链表中
boolean contains(int data);
// 删除指定元素
void remove(int key);
// 删除所有指定元素
void removeAllKey(int key);
// 求链表长度
int size();
// 清空链表
void clear();
// 打印链表
void display();
}
文章出处登录后可见！
已经登录？立即刷新