List、ArrayList与顺序表1
文章目录
- 1. 什么是List
- 2. 常见接口
- 3. List的使用
- 4. 线性表
- 5. 顺序表
- 5.1 接口的实现
1. 什么是List
在集合框架中，List是一个接口，继承与Collection接口，也继承于Iterable接口。
Collection接口中主要规范了后序容器中常用的一些方法
Iterable接口表示实现该接口的类是可以逐个元素进行遍历的
但是站在数据结构的角度来看，List是一个线性表，即n个具有相同类型元素的有限序列，在该序列上可以执行增删改查以及变量等操作。
2. 常见接口
常用方法如下
| 方法 | 解释 |
|---|---|
| boolean add( E e ) | 尾插e |
| void add( int index, E element ) | 将 e 插入到 index 的位置 |
| boolean addAll( Collection< ? extends E > c ) | 尾插 c 中的元素 |
| E remove( int index ) | 删除 index 位置元素 |
| boolean remove( Object o ) | 删除遇到的第一个 o |
| E get( int index ) | 获取 index 下标的元素 |
| E set( int index , E element ) | 将下标 index 的元素置为 element |
| void clear( ) | 清空 |
| boolean contains( Object o ) | 判断线性表中是否包含 o |
| int indexOf( Object o ) | 返回第一个出现的 o 的下标 |
| int lastIndexOf( Object o ) | 返回最后一个出现的 o 的下标 |
| ListsubList( int fromIndex,int toIndex ) | 截取部分List |
3. List的使用
注意：List只是个接口，并不能直接用来实例化。
如下图所示，集合框架中，ArrayList 和 LinkedList 都实现了 List 接口，我们可以实例化 ArrayList 和 LinkedList 。（下面就会学习）
4. 线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。常见的线性表：顺序表、链表、栈、队列。
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
5. 顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
5.1 接口的实现
public interface IList {
// 新增元素,默认在数组最后新增
void add(int data);
// 在 pos 位置新增元素
void add(int pos, int data);
// 判定是否包含某个元素
boolean contains(int toFind);
// 查找某个元素对应的位置
int indexOf(int toFind);
// 获取 pos 位置的元素
int get(int pos);
// 给 pos 位置的元素设为 value -> 更新
void set(int pos, int value);
//删除第一次出现的关键字key
void remove(int toRemove);
// 获取顺序表长度
int size();
// 清空顺序表
void clear();
// 打印顺序表，
// 注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
void display();
boolean isFull();
}
现在让我们根据上述接口来自己实现一个顺序表
1. 打印顺序表 （遍历即可）
@Override
public void display() {
for (int i = 0; i < usedSize; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
2. 新增元素,默认在数组最后新增
- 在新增元素之前，我们要判断顺序表是否满了，如果满了将无法新增，我们可以使用扩容的方法使其新增成功。
- 不要忘记当前长度要加一，usedSize++
- 将 isFull 方法也写入接口当中
- 先重写 isFull 方法
@Override
public boolean isFull() {
return usedSize == array.length;
}
- 重写 add 方法
//新增元素,默认在数组最后新增
@Override
public void add(int data) {
if(isFull()){
array = Arrays.copyOf(array,array.length*2);
}
this.array[usedSize] = data;
usedSize++;
}
- 在 pos 位置新增元素
- 首先，应该判断pos 位置是否合法，我们可以使用异常来处理，编写 PosNotLegalException的异常类和checkPosOfAdd 的方法
public class PosNotLegalException extends RuntimeException{
public PosNotLegalException(){
}
public PosNotLegalException(String msg){
super(msg);
}
}
private void checkPosOfAdd(int pos) throws PosNotLegalException{
if(pos < 0 || pos > usedSize){
throw new PosNotLegalException("Add时Pos位置不合法");
}
}
- 然后还要判断该顺序表是否满了，满了则扩容
@Override
public void add(int pos, int data) {
try {
checkPosOfAdd(pos);
}catch (PosNotLegalException e){
e.printStackTrace();
}
if(isFull()){
array = Arrays.copyOf(array,array.length*2);
}
for (int i = usedSize; i > pos ; i--) {
array[i] = array[i - 1];
}
array[pos] = data;
usedSize++;
}
4. 判定是否包含某个元素
- 遍历顺序表，找到返回 true ，没找到返回false
@Override
public boolean contains(int toFind) {
for (int i = 0; i < usedSize; i++) {
if(array[i] == toFind ){
return true;
}
}
return false;
}
5. 查找某个元素对应的位置
- 遍历顺序表，找到后返回该元素的下标
@Override
public int indexOf(int toFind) {
for (int i = 0; i < usedSize; i++) {
if(array[i] == toFind){
return i;
}
}
return -1;
}
6. 获取 pos 位置的元素
- 要记得判断 pos 的位置是否合法，写一个方法来判断（get 和 set 方法都能用到）
private void checkPosOfGetAndSet(int pos) throws PosNotLegalException{
if(pos <0 || pos >= usedSize){
throw new PosNotLegalException("get/set时pos不合法");
}
}
@Override
public int get(int pos) {
try{
checkPosOfGetAndSet(pos);
}catch (PosNotLegalException e){
e.printStackTrace();
}
return array[pos];
}
7. 给 pos 位置的元素设为 value
- 还是要先判断 pos 位置是否合法
@Override
public void set(int pos, int value) {
try{
checkPosOfGetAndSet(pos);
}catch (PosNotLegalException e){
e.printStackTrace();
}
array[pos] = value;
}
8. 删除第一次出现的关键字key
- 首先需要找到你想要删除的关键字的下标pos，才能删除，刚好用到我们上面写到的 indexOf 方法
- 不要忘记判断 pos 是否合法
- 删除元素
- 当前长度减一，即 usedSize - 1
@Override
public void remove(int toRemove) {
int pos = indexOf(toRemove);
if (pos == -1){
System.out.println("没有你要删除的数字");
return;
}
for (int i = pos; i < usedSize - 1; i++) {
array[i] = array[i + 1];
}
usedSize--;
}
9. 获取顺序表长度
- 当前 usedSize 的值就是顺序表的长度。
public int size() {
return usedSize;
}
10. 清空顺序表
- 直接将 usedSize 置为 0 即可，如果该顺序表当中存储的引用类型，那么需要遍历顺序表，将每个下标都指向null
@Override
public void clear() {
//如果为引用类型
/*for (int i = 0; i < usedSize; i++) {
array[i] == null;
}*/
usedSize = 0;
}
全部代码如下
package project1;
public interface IList {
// 新增元素,默认在数组最后新增
void add(int data);
// 在 pos 位置新增元素
void add(int pos, int data);
// 判定是否包含某个元素
boolean contains(int toFind);
// 查找某个元素对应的位置
int indexOf(int toFind);
// 获取 pos 位置的元素
int get(int pos);
// 给 pos 位置的元素设为 value
void set(int pos, int value);
//删除第一次出现的关键字key
void remove(int toRemove);
// 获取顺序表长度
int size();
// 清空顺序表
void clear();
// 打印顺序表，
void display();
boolean isFull();
}
package project1;
public class PosNotLegalException extends RuntimeException{
public PosNotLegalException(){
}
public PosNotLegalException(String msg){
super(msg);
}
}
package project1;
import java.util.Arrays;
public class MyArrayList implements IList{
private int[] array;
private int usedSize;
public MyArrayList(){
this.array = new int[10];
}
//新增元素,默认在数组最后新增
@Override
public void add(int data) {
if(isFull()){
array = Arrays.copyOf(array,array.length*2);
}
this.array[usedSize] = data;
usedSize++;
}
private void checkPosOfAdd(int pos) throws PosNotLegalException{
if(pos < 0 || pos > usedSize){
throw new PosNotLegalException("Add时Pos位置不合法");
}
}
@Override
public void add(int pos, int data) {
try {
checkPosOfAdd(pos);
}catch (PosNotLegalException e){
e.printStackTrace();
}
if(isFull()){
array = Arrays.copyOf(array,array.length*2);
}
for (int i = usedSize; i > pos ; i--) {
array[i] = array[i - 1];
}
array[pos] = data;
usedSize++;
}
@Override
public boolean contains(int toFind) {
for (int i = 0; i < usedSize; i++) {
if(array[i] == toFind ){
return true;
}
}
return false;
}
@Override
public int indexOf(int toFind) {
for (int i = 0; i < usedSize; i++) {
if(array[i] == toFind){
return i;
}
}
return -1;
}
private void checkPosOfGetAndSet(int pos) throws PosNotLegalException{
if(pos <0 || pos >= usedSize){
throw new PosNotLegalException("get/set时pos不合法");
}
}
@Override
public int get(int pos) {
try{
checkPosOfGetAndSet(pos);
}catch (PosNotLegalException e){
e.printStackTrace();
}
return array[pos];
}
@Override
public void set(int pos, int value) {
try{
checkPosOfGetAndSet(pos);
}catch (PosNotLegalException e){
e.printStackTrace();
}
array[pos] = value;
}
@Override
public void remove(int toRemove) {
int pos = indexOf(toRemove);
if (pos == -1){
System.out.println("没有你要删除的数字");
return;
}
for (int i = pos; i < usedSize - 1; i++) {
array[i] = array[i + 1];
}
usedSize--;
}
@Override
public int size() {
return usedSize;
}
@Override
public void clear() {
//如果为引用类型
/*for (int i = 0; i < usedSize; i++) {
array[i] == null;
}*/
usedSize = 0;
}
@Override
public void display() {
for (int i = 0; i < usedSize; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
@Override
public boolean isFull() {
return usedSize == array.length;
}
}
package project1;
import java.util.List;
public class Test {
public static void main(String[] args) {
IList iList = new MyArrayList();
iList.add(1);
iList.add(2);
iList.add(3);
iList.add(4);
iList.add(5);
iList.add(2,6);
boolean flag1 = iList.contains(6);
System.out.println(flag1);
iList.remove(6);
boolean flag2 = iList.contains(6);
System.out.println(flag2);
//iList.clear();
iList.display();
}
}
ArrayList 自己也有这些方法，下一篇学习 ArrayList 自己的方法。
写了这么多，我真牛，要好好奖励奖励自己了
