【数据结构】ArrayList与顺序表

目录

1.List是什么

2.线性表

3.顺序表

3.1接口的实现

4.ArrayList简介

4.ArrayList的使用

  4.1构造方法

4.2ArrayList的一些常见操作

4.3 ArrayList的遍历

---

---

   本章内容我们将详细介绍Arraylist相关以及顺序表的使用，ArrayList实现了List接口。

1.List是什么

   在集合框架中，List是一个接口，继承自Collection。Collection也是一个接口，

该接口规范了后续容器中常用的一些方法，具体如下所示：

Iterable也是一个接口，表示该接口的类是可以逐个元素进行遍历的，具体如下：

站在数据结构的角度来看，List就是一个线性表，即n个具有相同类型元素的有限序列，在该序列上可以执行增删改查以及变量等操作。

List接口也提供了很多方法，具体如下：

虽然提供了很多的方法，但是经常使用的方法是以下这些：

注：List是一个接口，并不能直接实例化。如果要使用，必须要去实例化List的实现类，在集合框架中，ArrayList和LinkedList实现了List接口。

2.线性表

  线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列...
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

3.顺序表

   顺序表是一段物理地址连续的存储单元依次存储数据元素的线性结构，一般采用数组存储，在数组上面完成增删改查。

3.1接口的实现

  我们可以自己通过数组来自定义一个顺序表。以下是个人写的关于顺序表的各种方法：

import java.util.Arrays;
 
public class SeqList {
    private int[] tmie;
    private int size;
    //构造方法
    public SeqList(){
        tmie=new int[10];
    }
    //默认插入到数组后面的位置
    public void add(int date){
        tmie[size]=date;
        size++;
    }
    //打印
    public void disPlay(){
        StringBuffer ret= new StringBuffer("{");
        //System.out.print(ret);
        for (int i = 0; i < size; i++) {
            ret.append(tmie[i]);
            if(i1){
                ret.append(",");
            }
        }
        ret.append("}");
        System.out.println(ret);
    }
    //在指定位置插入元素
    public void add(int pos, int data) {
        for (int i = pos; i 1 ; i++) {
            tmie[pos+1]=tmie[pos];
        }
        for (int i = pos; i 
            tmie[pos]=data;
        }
        size++;
    }
    // 判定是否包含某个元素
    public boolean contains(int toFind) {
        for (int i = 0; i < size; i++) {
            if(tmie[i]==toFind){
                return true;
            }
        }
        return false;
    }
    // 获取 pos 位置的元素
    public int get(int pos) {
        for (int i = 0; i < size; i++) {
            if(tmie[i]==pos){
                return i;
            }
        }
        return -1;
    }
    // 给 pos 位置的元素设为 value
    public void set(int pos, int value) {
        tmie[pos]=value;
    }
    //删除第一次出现的关键字key
    public void remove(int toRemove) {
        int a=get(toRemove);
        for (int i = a; i 1 ; i++) {
            tmie[i]=tmie[i+1];
        }
        size--;
    }
    // 清空顺序表
    public void clear() {
       size=0;
    }
 
 
 
 
 
}

4.ArrayList简介

在集合框架中，ArrayList是一个普通的类，实现了List接口，具体框架如下：

[说明]

1.ArrayList 是以泛型方法实现的，使用时必须要先实例化。

2。ArrayList实现了RandomAccess接口，表明它支持随机访问。

3.ArrayList实现了Cloneable接口，表明它是可以clone的。

4.ArrayList实现了Serializable接口，表妹它是支持序列化的。

5.它的底层是一段连续的空间，并且可以多态扩容，是一个多态类型的顺序表。

4.ArrayList的使用

  4.1构造方法

public class Test {
    public static void main(String[] args) {
        //初始就给了ArrayList一个初始空间
        ArrayList arrayList1=new ArrayList<>(2);
        //使用其它Collection创建
        List arrayList2=new ArrayList<>();
        //无参构造
        ArrayList arrayList3=new ArrayList<>();
    }
}

4.2ArrayList的一些常见操作

ArrayList提供的方法很多，我们着重介绍一些常用的方法；

4.3 ArrayList的遍历

ArrayList 可以使用三方方式遍历：for循环+下标、foreach、使用迭代器

public static void main(String[] args) {
        List list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        //使用for循环遍历
        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 it = list.listIterator();
        while (it.hasNext()){
            System.out.print(it.next() +" ");
        }
    }

注意：
1. ArrayList最长使用的遍历方式是：for循环+下标 以及 foreach
2. 迭代器是设计模式的一种。