
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
 
public class Test {
    List<Integer> stack = new Stack<>();//栈
    List<Integer> arrayList = new ArrayList<>();//顺序表
    List<Integer> linkList = new LinkedList<>();//链表
}

2.线性表

定义：n个具有相同特性的数据元素的有限序列，是一种在实际中广泛使用的数据结构。

常见的线性表：顺序表、链表、栈、队列……

逻辑上是线性结构，即连续的一条直线，但在物理结构上并不一定是连续的。

物理上存储时，通常以数组和链式结构的形式存储。

3.顺序表

定义：用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。逻辑上是连续的，物理上也是连续的。

即：通过方法操作数组。

3.1常用方法

方法	说明
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

其中E为泛型。

注意：subList 方法截取的是原来List对象中的地址，所以修改subList截取后的值会同时改变原来List中的值。

3.2常用方法的实现

下面方法ArrayList表中都有，我们自己来实现一下，更能理解里面具体的实现原理：


package Demo1;
 
public class PosOutOfBoundsException extends RuntimeException{
    public PosOutOfBoundsException(String message) {
        super(message);
    }
}


package Demo1;
 
public class Test {
    public static void main(String[] args) {
        SeqList seqList = new SeqList();
        for (int i = 0; i < 10; i++) {
            seqList.add(i,i);
        }
        seqList.display();
        //System.out.println(seqList.get(6));//报错
        //……………………
    }
}


package Demo1;
 
import java.util.Arrays;
 
public class SeqList {
    private int[] elem;
    private int usedSize;//默认为0，记录当前顺序表中有几个有效的数据
    private static final int DEFAULT_CAPACITY = 3;//默认容量
    public SeqList() { //不带参数的构造方法
        this.elem = new int[DEFAULT_CAPACITY];//new一个数组
    }
    private boolean isFull() { //判断数组是否满了
        return this.usedSize == this.elem.length;
    }
    private boolean checkPos(int pos) { //判断获取的下标是否合法
        if (pos < 0 || pos >= this.usedSize) {
            return false;
        }
        return true;
    }
    private boolean isEmpty() { //判断顺序表是否为空数据
        return this.usedSize == 0;
    }
    private void resize() { //扩容
        this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        //copyOf开辟一个长度为2*elem.length的新数组并将原elem数组中的元素拷贝进去，再返回给elem
    }
    public void display() { //打印顺序表
        for (int i = 0; i < this.usedSize; i++) {
            System.out.println(this.elem[i]+" ");
        }
        System.out.println();
    }
    public void add(int data) { //新增元素，默认在已有数据后新增
        if (isFull()) { //如果满了，给数组扩容
            resize();
        }
        this.elem[this.usedSize] = data;
        this.usedSize++;
    }
    public void add(int pos,int data) { //在pos位置新增元素data
        if (isFull()) { //满了就扩容
            resize();
        }
        if (pos < 0 || pos > this.usedSize) { //注意这里与checkPos不同
            throw new PosOutOfBoundsException("add时位置不合法");
        }
        for (int i = this.usedSize-1; i >= pos ; i--) { //给data挪位置
            this.elem[i+1] = this.elem[i];
        }
        this.elem[pos] = data;//存data
        this.usedSize++;
    }
    public boolean contains(int toFind) { //判断是否包含某个元素
        for (int i = 0; i < this.usedSize; i++) {
            if (toFind == this.elem[i]) {
                return true;
            }
        }
        return false;
    }
    public int indexOf(int toFind) { //查找某个元素对应位置的下标
        for (int i = 0; i < this.usedSize; i++) {
            if (toFind == this.elem[i]) {
                return i;
            }
        }
        return -1;
    }
    public int get(int pos) { //获取pos位置处的元素
        if (checkPos(pos) == false) {
            throw new PosOutOfBoundsException("get时位置不合法");//自定义一个异常
        }
        return this.elem[pos];
    }
    public int size() { //获取当前顺序表长度
        return this.usedSize;
    }
    public void set(int pos,int value) { //将pos位置处的值更新为value
        if (checkPos(pos)) {
            throw new PosOutOfBoundsException("set时位置不合法");
        }
        this.elem[pos] = value;
    }
    public void remove(int key) { //删除第一次出现的关键字key
        if (isEmpty()) {
            return;
        }
        int index = indexOf(key); //查找key
        if (index == -1) { //没找到要删除的key
            return;
        }
        for (int i = index; i <this.usedSize-1; i++) {
            this.elem[i] = this.elem[i+1];
        }
        this.usedSize--;//这一步不能忘！
        //this.elem[usedSize] = null; 存储引用类型时要手动置空
    }
    public void clear() { //清空顺序表
        /*for (int i = 0; i < usedSize; i++) {
            this.elem[i] = null;
        }*/  //此处是当elem中存储引用类型数据时，清空时全部置为null
        this.usedSize = 0; //存数字时只需将有效元素个数置为0即可
    }
}

4.ArrayList

注意：1> ArrayList实现了List接口；

2> ArrayList是以泛型方式实现的，使用时必须要先实例化；

3> 实现了RandomAccess接口，表明支持随机访问；

4> 实现了Cloneable接口，表明支持克隆；

5> 实现了Serializable接口，表明支持序列化；

6> ArrayList不是线程安全的，在单线程下可以使用，多线程中应选择 Vector 或CopyOnWriteArrayList；

7> ArrayList底层是一段连续的空间，可以动态扩容，是一个动态类型的顺序表。

4.1构造方法

方法	说明
ArrayList ()	无参构造
ArrayList ( Collection < ? extends E > c )	利用其他Collection构建ArrayList
ArrayList ( int intialCapacity )	指定顺序表初始容量

注意：上述第二个构造方法中，？是通配符，在之后的泛型进阶中会讲到；后面括号中代码意为参数必须为E本身或E的子类。


public class Test {
    public static void main(String[] args) {
        List<Integer> list1 = new ArrayList<>();//构造一个空的顺序表
        List<Integer> list2 = new ArrayList<>(10);//构造一个初始容量为10的顺序表
        list2.add(1);
        list2.add(2);
        list2.add(3);
        ArrayList<Integer> list3 = new ArrayList<>(list2);//参数为本身或其子类时，可以直接赋值
    }
}

4.2遍历

四种遍历方法：sout直接打印，for循环，for-each循环，迭代器。


public class Test {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        //法一：sout直接输出
        System.out.println(arrayList);//[1, 2, 3]---原因：父类中重写了toString方法
        //法二：for循环
        for (int i = 0; i < arrayList.size(); i++) {
            System.out.print(arrayList.get(i)+" ");
        }
        System.out.println();
        //法三：for-each循环
        for (int x : arrayList) { //冒号前为类型和临时创建的变量，冒号后为需要遍历的对象
            System.out.print(x+" ");
        }
        System.out.println();
        //法四：迭代器(设计模式的一种)
        Iterator<Integer> iterator = arrayList.listIterator();//定义一个迭代器
        while (iterator.hasNext()) { //如果有下一个就打印下一个
            System.out.print(iterator.next()+" ");
        }
        System.out.println();
    }
}

4.3扩容

源码见下：

说明：

1.当调用不带参数的构造方法时，底层的数组长度为0（空数组）；

2.第一次add时，会给我分配大小为10的内存；

3.所需空间超过原有空间时，初步预估按照1.5倍大小扩容；

4.如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容；

5. 使用copyOf进行扩容。

注意：

1. 检测是否真正需要扩容，如果是调用grow准备扩容；

2.扩容之前检测是否能扩容成功，防止太大导致扩容失败。

4.4CVTE面试题：删除相同字符

编程要求：删除第一个字符串中出现的第二个字符串中的字符。


public class Test {
    //法一：ArrayList
    public static void func1(String str1,String str2) {
        List<Character> ret = new ArrayList<>();//定义一个ArrayList表用来存放结果
        for (int i = 0; i < str1.length(); i++) {
            char ch = str1.charAt(i);//遍历获取str1中的每个字符
            if (!str2.contains(ch+"")) { //如果str2不包含这个字符
                ret.add(ch);//将这个字符插入顺序表中
            }
        }
        for (int i = 0; i < ret.size(); i++) {
            System.out.print(ret.get(i));
        }
    }
 
    //法二：数组
    public static String func1(String str1,String str2) {
        String Tmp = str1;
        for (int i = 0; i < str2.length(); i++) {
            String tmp = String.valueOf(str2.charAt(i));
            Tmp = Tmp.replaceAll(tmp,"");
        }
        return Tmp;
    }
 
    public static void main(String[] args) {
        func("welcome to world","come");//wl t wrld
        String s = func1("welcome to world","come");
        System.out.println(s);//wl t wrld
    }
}

这里有一个编程技巧：因为 contains 的参数为 CharSequence，是字符串，而ch只是一个字符，此时将ch 加上一个"" 即可将字符变为字符串。

5.ArrayList的具体实现

5.1洗牌算法

Card.java


package Demo;
//这里面的所有代码都可以用Generate自动生成
public class Card { //定义牌
    private String suit;//花色
    private int rank;//数字
    public Card(String suit, int rank) {
        this.suit = suit;
        this.rank = rank;
    }
    public String getSuit() {
        return suit;
    }
    public void setSuit(String suit) {
        this.suit = suit;
    }
    public int getRank() {
        return rank;
    }
    public void setRank(int rank) {
        this.rank = rank;
    }
    @Override
    public String toString() {
        return suit+rank ;
    }
}

Test.java


package Demo;
 
import java.util.*;
 
public class Test {
    private static final String[] SUITS = {"♥","♦","♠","♣"};//定义四个花色
    public static List<Card> buyCard() { //买牌(初始化牌)
        List<Card> cards = new ArrayList<>();//定义一个cards表
        for (int i = 0; i < SUITS.length; i++) {
            for (int j = 1; j <= 13; j++) {
                Card card = new Card(SUITS[i],j);//调用了Card的构造方法，分别new了一张牌
                cards.add(card);//将牌放入cards表里
            }
        }
        return cards;
    }
    public static void shuffle(List<Card> cards) { //洗牌
        //Collections.shuffle(cards); --- 库方法中有，这里我们自己实现：
        Random random = new Random();//new一个随机数对象
        for (int i = cards.size()-1; i > 0 ; i--) {
            int j = random.nextInt(i);//随机取一个[0,i)中的值(下标)
            Card tmp = cards.get(i);//在表中随机取一个值
            cards.set(i,cards.get(j));//利用set方法交换这两个值
            cards.set(j,tmp);
        }
    }
    public static void main(String[] args) {
        List<Card> cards = buyCard();//买牌(初始化牌)
        System.out.println("初始的牌："+cards);
        shuffle(cards);//洗牌
        System.out.println("洗完的牌："+cards);
 
        //定义三个表分别存放每个人揭的牌
        List<Card> hand1 = new ArrayList<>();
        List<Card> hand2 = new ArrayList<>();
        List<Card> hand3 = new ArrayList<>();
 
        //再定义一个表存放上面存牌的三个表(相当于二维数组)
        List<List<Card>> hand = new ArrayList<>();//注意这里List<>中的类型
        hand.add(hand1);
        hand.add(hand2);
        hand.add(hand3);
 
        //三个人轮流揭5张牌，注意不是一次性揭5张牌
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 3; j++) {
                Card card = cards.remove(0);//揭牌，即每次拿走表中的第一张(0下标处的)牌
                hand.get(j).add(card);//相当于先拿到二维数组的行数，再去访问行里的元素
            }
        }
 
        System.out.println("第一个人的牌:"+hand1);
        System.out.println("第二个人的牌:"+hand2);
        System.out.println("第三个人的牌:"+hand3);
        System.out.println("剩下的牌"+cards);
    }
}

5.2杨辉三角

杨辉三角


import java.util.ArrayList;
import java.util.List;
 
public class Test {
    public static List<List<Integer>> generate(int numRows) { //这个类型相当于二维数组
        List<List<Integer>> ret = new ArrayList<>();//用来接收整个杨辉三角，相当于二维数组
        List<Integer> list = new ArrayList<>();//用来接收杨辉三角的每一行，相当于一维数组
        list.add(1);//第一行只有1
        ret.add(list);//将第一行放入"二维数组"中
        for (int i = 1; i < numRows; i++) { //循环add每一行
            List<Integer> curRow = new ArrayList<>();
            curRow.add(1);//每一行第一个元素均为1
            for (int j = 1; j < i; j++) { //这里add每一行中间的元素
                int value = ret.get(i-1).get(j)+ret.get(i-1).get(j-1);//!!!
                curRow.add(value);
            }
            curRow.add(1);//每一行最后一个元素均为1
            ret.add(curRow);//add完一行后再整行add进"二维数组"中
        }
        return ret;
    }
    public static void main(String[] args) {
        List<List<Integer>> list = new ArrayList<>();
        list = generate(5);
        System.out.println(list);
    }
}

6.ArrayList的优缺点

优点：根据指定下标 (索引) 去查找元素或更新元素的效率非常高，时间复杂度可为O(1)。

缺点：1> 每次插入或删除数据时，都需要移动数据，若要插到0下标位置或删除0下标数据，复杂度将达到O(n)；2> 扩容时默认扩容1.5倍，当原空间很大而扩容空间只使用了一点时，将会浪费很多空间。

总结：顺序表适用于经常进行查找元素或更新元素的场景下使用，在另一些顺序表不适用的场景下，就需要链表出马了~~

下一篇文章就要探讨链表的奥秘了，狠狠期待住了！！

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/715545