1.线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。
线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
2.顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数
据的增删查改,其实，说人话就是高级一点的数组，在这个高级数组上能完成一些功能.
那么这个高级的数组到底长啥样呢，让我们一起来看看它的真面目
其实将它形象化以后它也就长这样，就是比普通的数组多了一个元素——usedSize,用来存放有效数据个数.
下面我们用代码来造出这个顺序表：
public class MyArrayList { public int[] elem;//数组 public int usedSize;//有效数据个数 左边这两者就是在堆区形成了我们的顺序表 public static final int DEFAULT_CAPACITY=5;;//DEFAULT_CAPACITY是顺序表数组的容量，将其存放在方法区，不属于对象 public MyArrayList() {//构造方法将顺序表实例化 this.elem = new int[DEFAULT_CAPACITY]; //this.usedSize = 0;默认为0 写不写都可 } }
这是这个顺序表所要实现的功能（接口）：
public void display() { } // 打印顺序表 public void add(int pos, int data) { } // 在 pos 位置新增元素 public boolean contains(int toFind) { return true; }// 判定是否包含某个元素 public int search(int toFind) { return -1; }// 查找某个元素对应的位置 public int getPos(int pos) { return -1; } // 获取 pos 位置的元素value public void setPos(int pos, int value) { } // 给 pos 位置的元素设为key public void remove(int toRemove) { } //删除第一次出现的关键字 public int size() { return 0; } // 获取顺序表长度 public void clear() { }// 清空顺序表
接下来为这些接口的具体实现（顺序上下一致）
1.打印顺序表（两种方法）
import java.util.Arrays;//第一种方法 public void display() { //导入until包，然后直接用Arrays.toString（）来将顺序表打印 System.out.println(Arrays.toString(this.elem)); } public void display() {//第二种方法 for (int i = 0; i < this.usedSize; i++) {//设置循环依次打印顺序表中的元素 System.out.print(this.elem[i] + " "); } System.out.println(); }
2.在 pos 位置新增元素
完成这一项工作需要分三步：
（1）判断pos位置是否合法
（2）挪数据（pos位置以后的数据给新元素腾地方，整体后移闪出一个空地）
（3）放数据（新来的老大就坐这里了）
import java.util.Arrays; private boolean isFull() {//判断顺序表是否已满 return this.usedSize==this.elem.length;//相等返回true，否则返回false } public void add(int pos,int data) { if(pos<0||pos>this.usedSize) {//当pos为负数或者大于有效个数时，位置不合法直接返回 return; } if (isFull()) {//如果顺序表已满，需要进行增容 this.elem = Arrays.copyOf(this.elem, 2*elem.length);//新数组需要将原数组先进性拷贝，然后其容量变为原来2倍 } for (int i = usedSize-1; i >=pos; i--) {//设置循环，从后边开始往前移，到pos位置终止循环，闪出一个位子 this.elem[i+1]=this.elem[i]; } this.elem[pos]=data;//放数据 this.usedSize++;//有效个数+1 }
3.判定是否包含某个元素
public boolean contains(int toFind) { for (int i = 0; i < this.usedSize; i++) {//遍历顺序表挨个比对，相同返回true if(toFind==this.elem[i]) { return true; } } return false;//遍历完成仍然没有return，就返回false }
4.查找某个元素对应的位置
public int search(int toFind) { for (int i = 0; i < this.usedSize; i++) {//与3其实一样，挨个比对，找到返回其角标 if(toFind==this.elem[i]) { return i; } } return -1;//没找到就返回-1，因为数组角标无-1，-1即代表没找到 }
5.获取 pos 位置的元素
public int getPos(int Pos) { if(this.usedSize==0) {//顺序表为空直接返回-1 return -1; } if(Pos<0||Pos>this.usedSize-1) {//pos位置不合法，直接返回-1（合法位置范围[0,this.usedSize-1]） return -1; } return this.elem[Pos]; }
6.给 pos 位置的元素设为
private boolean isEmpty() { return this.usedSize == 0; } public void setPos(int pos, int value) { if(pos < 0 || pos >= this.usedSize) { System.out.println("pos不合法！"); return; } if(isEmpty()) { System.out.println("顺序表为空！"); return; } this.elem[pos] = value; }
7.删除第一次出现的关键字
private boolean isEmpty() { return this.usedSize == 0; } public void remove(int toRemove) { if(isEmpty()) return; int index = this.search(toRemove);//search方法在4中实现 if(index == -1) { System.out.println("没有你要删除的数字"); return; } for (int i = index; i < this.usedSize-1; i++) {//该关键字后边的数据整体前移，将其覆盖掉 this.elem[i] = this.elem[i+1]; } this.usedSize--; }
8.获取顺序表长度
public int size() { return this.usedSize; }
9.清空顺序表
public void clear() { this.elem=null;//JVM在回收内存时，当该对象没有人在引用它的时候，这个对象才会被回收，将this.elem置为空，则数组将没有对象引用，自动被JVM回收 this.usedSize = 0; }
3. ArrayList
ArrayList底层是一段连续的空间，并且可以动态扩容，其实就是一个动态类型的顺序表
3.1 ArrayList的构造
方法 |
解释 |
| ArrayList() | 无参构造 |
ArrayList(Collection<? extends E> c) |
利用其他Collection构建ArrayList |
| ArrayList(int initialCapacity) | 指定顺序表初始容量 |
代码示例：
public static void main(String[] args) { // ArrayList创建，推荐写法 // 构造一个空的列表 List<Integer> list1=new ArrayList<>(); List<Integer> list2=new ArrayList<>(10); list2.add(1); list2.add(2); list2.add(3); // list3构造好之后，与list2中的元素一致 ArrayList<Integer> list3=new ArrayList<>(list2); }
3.2 ArrayList常见操作
大部分操作方法与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 的下标 |
| List subList(int fromIndex, int toIndex) | 截取部分 list |
3.3 ArrayList的遍历
ArrayList 可以使用三种方式遍历：for循环+下标、foreach、使用迭代器。
public static void main(String[] args) { List<Integer> list=new ArrayList<>(); list.add(1); list.add(2); list.add(3); list.add(4); list.add(5); //for循环遍历 for (int i = 0; i < list.size(); i++) { System.out.println(list.get(i)+" "); } System.out.println(); for(Integer integer:list) { System.out.println(integer+" "); } System.out.println(); //迭代器遍历 Iterator<Integer> it=list.listIterator(); while (it.hasNext()) { System.out.println(it.next()+" "); } System.out.println(); }
迭代器起一行一行扫描内容的作用，代码it.next()的作用为获取本行内容，并移步至下一行。
3.4 ArrayList的扩容机制（源码分析）
public static void main(String[] args) { ArrayList<Integer> list=new ArrayList<>();//顺序表大小是0 list.add(1);//大小变为了10 list.add(2); list.add(3); //。。。。。。。。当十个放慢以后，需要扩容，扩容采取的是1.5倍的扩容方式 }
ArrayList是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容：以下是ArrayList源码中扩容方式.
我们先来看ArrayList的构造方法：
此时给数组分配的大小为0，也就是说在一开始实例化时，数组容量为0
在调用add方法时，会根据目前的容量判断是否需要增容（如果增容增1.5倍）
【总结】
- 1.检测是否真正需要扩容，如果是调用grow准备扩容
- 预估需要库容的大小
- 2.初步预估按照1.5倍大小扩容
- 如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容
- 真正扩容之前检测是否能扩容成功，防止太大导致扩容失败
- 3.使用copyOf进行扩容
4. 使用实例（扑克牌）
一副牌（除大小王），现在需要进行的操作是先买牌，进行洗牌，然后三个人轮流从牌堆中摸五张牌，该实例是对ArrayList的总结与运用。
CardDemo类：
import java.util.ArrayList; import java.util.List; import java.util.Random; class Card { public int rank;//数字 public String suit;//花色 public Card(int rank, String suit) { this.rank = rank; this.suit = suit; } //重写打印方法 数字+花色 @Override public String toString() { return ""+suit+" "+rank; } } public class CardDemo { public static final String[] suits={"♥","♠","♣","♦"}; /** * 买扑克方法 * @return 扑克 */ public List<Card> buyDeskCard() { List<Card> cards=new ArrayList<>(); //13个数字，每个数字四张不同花色 for (int i = 1; i <=13 ; i++) { for (int j = 0; j < 4; j++) { Card card=new Card(i,suits[j]); cards.add(card); } } return cards; } /** * 洗牌方法 */ public void shuffle(List<Card> cards) { for (int i = cards.size()-1; i >0 ; i--) { Random random=new Random(); int index=random.nextInt(i); swap(cards,index,i); } } /** * 交换两张牌 * @param cards * @param i * @param j */ private void swap(List<Card> cards,int i,int j) { Card tmp=cards.get(i); cards.set(i,cards.get(j)); cards.set(j,tmp); } /** * 摸牌方法 * @param cards 牌堆 * @return 最后的摸牌清空 */ public List<List<Card>> test(List<Card> cards) { List<Card> hand1 = new ArrayList<>(); List<Card> hand2 = new ArrayList<>(); List<Card> hand3 = new ArrayList<>(); List<List<Card>> hands = new ArrayList<>(); hands.add(hand1); hands.add(hand2); hands.add(hand3); //3个人 每个人轮流抓5张牌 for (int i = 0; i < 5; i++) { for (int j = 0; j < 3; j++) { //remove方法返回值为牌堆的第一张牌，并且会把这张牌从牌堆中清除 Card card = cards.remove(0); hands.get(j).add(card); } } return hands; } }
Test类：
import java.util.List; public class Test { public static void main(String[] args) { CardDemo cardDemo=new CardDemo(); List<Card> ret=cardDemo.buyDeskCard(); System.out.println(ret); System.out.println("洗牌："); cardDemo.shuffle(ret); System.out.println("摸牌："); List<List<Card>> ret2=cardDemo.test(ret); for (int i = 0; i < ret2.size(); i++) { System.out.println("第"+(i+1)+"个人的牌："+ret2.get(i)); } System.out.println("剩余的牌:"); System.out.println(ret); } }
运行结果：
