数据结构--＞ArrayList与顺序表

目录

1. 线性表

1.1 概念

2. 顺序表

2.1 概念

2.2 接口的实现

3. ArrayList简介

3.1 简介

4. ArrayList使用

4.1 ArrayList的构造

4.2 ArrayList常见操作

4.3 ArrayList的遍历

4.4 ArrayList的扩容机制

4.5 ArrayList的优缺点

5. ArrayList的具体使用

5.1 简单的洗牌算法

5.2 杨辉三角

1. 线性表

1.1 概念

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

2. 顺序表

2.1 概念

• 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成 数据的增删查改。通过方法来操作数组
• 顺序表在逻辑上是连续的，在物理上也是连续的。

2.2 接口的实现

package demo1;public class PosOutBoundsException extends RuntimeException {public PosOutBoundsException() {}public PosOutBoundsException(String message) {super(message);}
}

package demo1;import java.util.Arrays;public class SeqList {private int[] elem;private int usedSize;//记录当前顺序表当中有多少个有效的数据private static final int DEFAULT_CAPACITY = 10;public SeqList(){this.elem = new int[DEFAULT_CAPACITY];}//打印顺序表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()){elem = Arrays.copyOf(elem,2*elem.length);}this.elem[usedSize] = data;usedSize++;}public boolean isFull(){return usedSize == elem.length;}//判断是否包含某个元素public boolean contains(int toFind){for(int i = 0; i < this.usedSize; i++){if(elem[i] == toFind){//如果数组中存储的时引用数据类型，这里能否继续用等号去比较return true;}}return false;}//查询某个元素对应的位置，下标public int indexOf(int toFind){for(int i = 0; i < this.usedSize; i++){if(elem[i] == toFind){//如果数组中存储的时引用数据类型，这里能否继续用等号去比较return i;}}return -1;}//获取pos位置的元素public int get(int pos){//pos一定合法吗if(pos < 0 || pos >=usedSize){throw new PosOutBoundsException("get 获取数据时 位置不合法");}return elem[pos];}//获取顺序表长度public int size(){return this.usedSize;}//给pos位置的值设置为valuepublic void set(int pos, int value){if(!checkPos(pos)){throw new PosOutBoundsException("set 数据时，位置不合法");}this.elem[pos] = value;}private boolean checkPos(int pos){if(pos < 0 || pos >=usedSize){return false;}return true;}//在pos位置新增元素//要连续public void add(int pos,int data){if(pos < 0 || pos > usedSize){throw new PosOutBoundsException("add 元素时，pos位置不合法");}if(isFull()){elem = Arrays.copyOf(elem,2*elem.length);}//挪数据for (int i = usedSize-1; i >= pos;i--){this.elem[i+1] = this.elem[i];}//存数据this.elem[pos] = data;this.usedSize++;}private void resize(){elem = Arrays.copyOf(elem,2*elem.length);}//删除第一次出现的关键字keypublic void remove(int toRemove){//要删除值的下标//index < us-1//us--if(isEmpty()){return;}int index = indexOf(toRemove);if(index == -1){return;//没有你要删除的数字}for (int i = index; i < usedSize-1; i++){this.elem[i] = this.elem[i+1];}usedSize--;//elem[us] = null;}public boolean isEmpty(){return usedSize == 0;}//清空顺序表public void clear(){/*for (int i = 0; i < usedSize; i++){this.elem[i] = null;}*/  //如果是引用类型，全部置空，回收，否则占内存（内存泄漏）usedSize = 0;}
}

package demo1;public class test2 {public static void main(String[] args) {SeqList seqList = new SeqList();for (int i = 0; i < 10; i++){seqList.add(i,i);}/*seqList.add(1);seqList.add(2);seqList.add(3);seqList.add(4);seqList.add(5);seqList.add(6);*/seqList.display();}
}

3. ArrayList简介

3.1 简介

1. ArrayList是以泛型方式实现的，使用时必须要先实例化
2. 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者 CopyOnWriteArrayList 
3. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

4. ArrayList使用

4.1 ArrayList的构造

①无参构造

总结：当调用不带参数的构造方法的时候，底层的数组长度为0，但是当我第一次add时，才会为我分配内存，此时第一次分配的内存为10

②利用其他 Collection 构建 ArrayList

③指定顺序表初始容量

4.2 ArrayList常见操作

①常用方法如下：

②一些简单的例子：

package demo3;import java.util.ArrayList;
import java.util.List;public class test1 {public static void main(String[] args) {ArrayList arrayList = new ArrayList<>();arrayList.add("abc");arrayList.add("mn");arrayList.add("jvof");System.out.println(arrayList);System.out.println("============");List ret1 = arrayList.subList(1,3);ret1.set(0,"momo");System.out.println(ret1);System.out.println("============");List list = new ArrayList<>();list.add("hello");list.addAll(arrayList);System.out.println(list);System.out.println("===========");boolean ret = list.remove("hello");System.out.println(ret);System.out.println(list);System.out.println("============");list.clear();System.out.println(list);}
}

4.3 ArrayList的遍历

①for循环＋下标

package demo2;import java.util.ArrayList;public class tets1 {public static void main(String[] args) {ArrayList arrayList = new ArrayList<>();arrayList.add("abc");arrayList.add("efg");arrayList.add("kjl");arrayList.add("mmm");for (int i = 0; i < arrayList.size();i++){System.out.println(arrayList.get(i)+" ");}System.out.println();}
}

②foreach

package demo2;import java.util.ArrayList;public class test2 {public static void main(String[] args) {ArrayList arrayList = new ArrayList<>();arrayList.add("abc");arrayList.add("efg");arrayList.add("kjl");arrayList.add("mmm");for (String x: arrayList){System.out.println(x+" ");}}
}

③使用迭代器

package demo2;import java.util.ArrayList;
import java.util.Iterator;public class test3 {public static void main(String[] args) {ArrayList arrayList = new ArrayList<>();arrayList.add("abc");arrayList.add("efg");arrayList.add("kjl");arrayList.add("mmm");Iterator it = arrayList.listIterator();while(it.hasNext()){System.out.println(it.next()+" ");}System.out.println();}
}

4.4 ArrayList的扩容机制

ArrayList是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容。

看下列代码：

public static void main(String[] args) {List list = new ArrayList<>();for (int i = 0; i < 100; i++) {list.add(i);}
}

由4.1①可知，ArrayList在插入元素的过程中会自动扩容。

总结：

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

2.预估需要库容的大小：

•   初步预估按照1.5倍大小扩容
•   如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容
•   真正扩容之前检测是否能扩容成功，防止太大导致扩容失败

3.使用copyOf进行扩容

4.5 ArrayList的优缺点

一、优点：

①根据指定下标（索引）去查找元素，效率非常高，时间复杂度为O（1）

②更新元素也很快，更新指定下标的元素

二、缺点：

①每次插入数据，都要移动元素，极端情况下，如果插入到0下标，那么移动的元素复杂度O（N)

②每次删除数据的时候，都需要移动元素，极端情况下，删除0下标的元素：O（N)

③当满了之后，进行扩容，1.5倍扩容。如果只放了1个元素，可能会浪费空间

三、总结：

顺序表适用于经常进行查找元素或者更新元素的场景下

5. ArrayList的具体使用

5.1 简单的洗牌算法

（三人轮流揭洗过的牌五张）分析：

1.每个人揭的牌都放到哪里

 2.怎么知道我现在揭牌到哪个list

 3.怎么揭牌

 4.怎么实现3个人每个人轮流揭牌5张

 完整代码如下所示：

package demo1;import java.util.ArrayList;
import java.util.List;
import java.util.Random;public class Test {//花色private  static final String[] SUITS ={"♥","♠","♦","♦"};public static List buyCard(){List cards = new ArrayList<>();for (int i = 0; i < SUITS.length; i ++){for (int j = 1; j <= 13 ; j++){Card card = new Card(SUITS[i],j);cards.add(card);}}return cards;}//洗牌public static void shuffle( List cards){Random random = new Random();//生成随机数for (int i = cards.size()-1; i > 0; i--){int j = random.nextInt(i);//交换Card tmp = cards.get(i);cards.set(i,cards.get(j));//更新i下标的值cards.set(j,tmp);///更新j下标的值}}public static void main(String[] args) {List cards = buyCard();System.out.println(cards);System.out.println("洗牌：");shuffle(cards);System.out.println(cards);//3个人，每个人轮流接牌5张//每个人轮流接的牌都放到哪里List hand1 = new ArrayList<>();List hand2 = new ArrayList<>();List hand3 = new ArrayList<>();List>  hand = new ArrayList<>();//二维数组hand.add(hand1);hand.add(hand2);hand.add(hand3);for (int i = 0; i < 5; i++){for (int j = 0; j < 3; j++){//接牌的动作Card card = cards.remove(0);//如何放到指定的人手里hand.get(j).add(card);//j下标获取list}}System.out.println("第一个人的牌：");System.out.println(hand1);System.out.println("第二个人的牌：");System.out.println(hand2);System.out.println("第三个人的牌：");System.out.println(hand3);System.out.println("剩下的牌：");System.out.println(cards);}
}

package demo1;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;}@Overridepublic String toString() {return suit + " " + rank ;}
}

5.2 杨辉三角

链接

分析：

首位的数字：1

中间的数字：[i][j]= [i-1][j-1]+[i-1][j]

import java.util.ArrayList;
import java.util.List;
//杨辉三角
public class test {public List> generate(int numRows){List> ret = new ArrayList<>();List list =new ArrayList<>();list.add(1);ret.add(list);for (int i = 1; i < numRows; i++){List curRow =new ArrayList<>();curRow.add(1);//处理中间的数字List perRow = ret.get(i-1);//上一行for (int j = 1; j < i; j++){int val = perRow.get(j)+perRow.get(j-1);curRow.add(val);}//最后一个数字1curRow.add(1);ret.add(curRow);}return ret;}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！