作者爱塔居的博客_CSDN博客-JavaSE,数据结构领域博主

专栏数据结构

作者简介大三学生希望一起进步

一、顺序表基本概念

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

顺序表接口实现代码

1. ArrayList是以泛型方式实现的使用时必须要先实例化
2. ArrayList实现了RandomAccess接口表明ArrayList支持随机访问

3. ArrayList实现了Cloneable接口表明ArrayList是可以clone的
4. ArrayList实现了Serializable接口表明ArrayList是支持序列化的
5. 和Vector不同ArrayList不是线程安全的在单线程下可以使用在多线程中可以选择Vector或者CopyOnWriteArrayList
6. ArrayList底层是一段连续的空间并且可以动态扩容是一个动态类型的顺序表

🍇ArrayList常见操作

方法	解释
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 的下标
List<E> subList(int fromIndex, int toIndex)	截取部分 list

在第一次add的时候才会给ArrayList底层的elementData分配内存且大小为0。当内存不够时会进行近似1.5倍扩容。

一般java中的from……to……都是左闭右开的所以这边截取用的subList是左闭右开的。而且我们在运行时会发现subList方法只是放入了指向arraylist元素的地址。当arraylist的值发生改变时sub值也会变。

实例代码块

import java.util.ArrayList;
import java.util.List;

public class Test {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList1=new ArrayList<>();
        arrayList1.add(1);//增加元素
        arrayList1.add(2);
        arrayList1.add(3);
        arrayList1.add(4);
        arrayList1.add(5);
        arrayList1.add(0,10);//在指定位置增加元素
        System.out.println(arrayList1);
        List<Integer> sub= arrayList1.subList(0,2);//截取arraylist部分
        System.out.println(sub);
        System.out.println("________");
        arrayList1.set(0,1000);//在指定位置放入指定数据
        System.out.println(arrayList1);
        System.out.println(sub);
    }
}

运行结果 

 arraylist的遍历方法

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

public class Test {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList1=new ArrayList<>();
        arrayList1.add(1);//增加元素
        arrayList1.add(2);
        arrayList1.add(3);
        arrayList1.add(4);
        arrayList1.add(5);
        //遍历arraylist
        System.out.println(arrayList1);
        //用for循环遍历
        for (int i = 0; i < arrayList1.size() ; i++) {
            System.out.print(arrayList1.get(i)+" ");
        }
        System.out.println("");
        //foreach遍历
        for (Integer i:arrayList1) {
            System.out.print(i+" ");
        }
        System.out.println();
        //迭代器遍历
        ListIterator<Integer> it= arrayList1.listIterator();
        while (it.hasNext()){
            System.out.print(it.next()+" ");
        }
    }
}

运行结果

  

二、练习

1.String s1="welcome to world"; String s2="come";要求删除s1中的字符这些字符都是s2中出现的.

import java.util.ArrayList;
public class Test {
    public static void main(String[] args) {
        ArrayList<Character> list=new ArrayList<>();
 String s1="welcome to world";
 String s2="come";
        for (int i = 0; i < s1.length(); i++) {
            char ch=s1.charAt(i);
                if(!s2.contains(ch+"")){
                    list.add(ch);
            }
        }
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i)+"");
        }
    }
}

运行结果 

 

 2.杨辉三角

我们在构建时这样子构建

 

 行为i列为j

公式为[i][j]=[i-1][j]+[i-1][j-1]

代码

class Solution {
    public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> ret=new ArrayList<List<Integer>>();
    for(int i=0;i<numRows;++i){
        List<Integer> row=new ArrayList<Integer>();
        for(int j=0;j<=i;++j){
            if(j==0||i==j){
                row.add(1);
            }else{
                row.add(ret.get(i-1).get(j-1)+ret.get(i-1).get(j));
            }
        }
        ret.add(row);
    }
    return ret;
    }
}

其中 List<List<Integer>> ret=new ArrayList<List<Integer>>();

可以理解为每一列作为一个数组每个数组合起来成为一个数组