数据结构-ArrayList和顺序表 _ArrayList

胸怀万里世界，放眼无限未来。这篇文章主要讲述数据结构-ArrayList和顺序表相关的知识，希望能为你提供帮助。

目录
一.线性表
二.顺序表
三.ArrayList
1.源码的分析
2.ArrayList的构造
3.ArrayList的常见操作
4.ArrayList的遍历
5.ArrayList的扩容机制
四.杨辉三角
五.去掉第一个字符串中与第二个字符串相同的内容
六.扑克牌
七.复试面试题6-11
6.结构体的赋值？
7.函数参数入栈顺序？
8.inline内联函数
9、“引用”与指针的区别是什么？
10、.h头文件中的ifndef/define/endif 的作用？

下面开始本节课的内容
一.线性表线性表是最基本最简单最常用的一种数据结构，线性表是一种数据结构，一个线性表示n个具有相同特性元素的有序数列。
常见的线性表有：顺序表链表栈队列字符串
线性表在逻辑上是线性结构，也就是一条直线，但在物理结构上并不是连续的，线性表上都是首尾相接的

1	2	3	4	5	6	7

链表

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

public class SeqList
// 打印顺序表
public void display()
// 新增元素,默认在数组最后新增
public void add(int data)
// 在 pos 位置新增元素
public void add(int pos, int data)
// 判定是否包含某个元素
public boolean contains(int toFind)return true;
// 查找某个元素对应的位置
public int indexOf(int toFind)return -1;
// 获取 pos 位置的元素
public int get(int pos)return -1;
// 给 pos 位置的元素设为 value
public void set(int pos, int value)
//删除第一次出现的关键字key
public void remove(int toRemove)
// 获取顺序表长度
public int size()return 0;
// 清空顺序表
public void clear()

分析：
1.新增元素，默认在数组最后新增

新增元素，默认在数组后面新增
public void add(int data)
判断当前的顺序是不是满的

如果是满的就需要扩容

新增元素，默认在数组后面新增
public void add(int data)
判断当前的顺序是不是满的//如果满了，就扩容原来的2倍
if (isFull())
this.elem=Arrays.copyof(elem,newlength:2*elem.length);

//没满就进行直接插入
this.elem[usedSize]=data;
unsedSize++;

2.在POS位置上新增元素

那么我们判断的步骤就是

3.判断是否包含某个元素

4.删除某个元素

0 1 2 3 4

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

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

1.源码的分析2.ArrayList的构造

public static void main(String[] args)
// ArrayList创建，推荐写法
// 构造一个空的列表
List< Integer> list1 = new ArrayList< > ();
// 构造一个具有10个容量的列表
List< Integer> list2 = new ArrayList< > (10);
list2.add(1);
list2.add(2);
list2.add(3);
// list2.add("hello"); // 编译失败，List< Integer> 已经限定了，list2中只能存储整形元素
// list3构造好之后，与list中的元素一致
ArrayList< Integer> list3 = new ArrayList< > (list2);

注意我们要避免省略类型

// 避免省略类型，否则：任意类型的元素都可以存放，使用时将会出现很大的问题
List list4 = new ArrayList();
list4.add("111");
list4.add(100);

3.ArrayList的常见操作4.ArrayList的遍历

ArrayList< Integer> arrayList = new ArrayList< > ();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
arrayList.add(4);
arrayList.add(5);
// 使用下标+for遍历
for (int i = 0; i < arrayList.size(); i++)
System.out.print(arrayList.get(i)+" ");

System.out.println();

// 借助 foreach 遍历
for (Integer x : arrayList)
System.out.print(x+" ");

System.out.println();
System.out.println("==========================");

//使用迭代器
Iterator< Integer> it = arrayList.iterator();
while(it.hasNext())
System.out.print(it.next()+" ");

5.ArrayList的扩容机制

检测是否真正需要扩容，如果是调用grow准备扩容
预估需要库容的大小，初步预估按照1.5倍大小扩容，如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容，真正扩容之前检测是否能扩容成功，防止太大导致扩容失败
使用copyOf进行扩容

四.杨辉三角

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

class Solution
public List< List< Integer> > generate(int numRows)
List< List< Integer> > ret = new ArrayList< > ();
List< Integer> one = new ArrayList< > ();
one.add(1);
ret.add(one);
//i 代表每一行
for (int i = 1; i < numRows; i++)
List< Integer> curRow = new ArrayList< > ();
curRow.add(1); //这一行开始的 1
//j 代表这一行的每个元素
for (int j = 1; j < i ; j++)
//curRow[i][j] = 前一行[i-1][j] + 前一行[i-1][j-1]
List< Integer> preRow = ret.get(i-1); //前一行
int x = preRow.get(j) + preRow.get(j-1);
curRow.add(x);

// j==i这一行最后的 1
curRow.add(1);
ret.add(curRow);

return ret;

五.去掉第一个字符串中与第二个字符串相同的内容

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

public class TestDemo
public static List< Character> func(String s1,String s2)
if( s1==null || s2==null)
return null;

if( s1.length()==0 || s2.length()==0 )
return null;

List< Character> ret = new ArrayList< > ();
for (int i = 0; i < s1.length(); i++)
char ch = s1.charAt(i);
if(!s2.contains(ch+""))
ret.add(ch);

return ret;

public static void main(String[] args)
String s1 = "welcome to china";
String s2 = "come";
List< Character> ret = func(s1,s2);
for (char ch : ret)
System.out.print(ch);

六.扑克牌

package demo1;

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

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+"]";

public class TestCard
public static final String[]suits="?","?","?","?";
public static List< Card> buyCard()
List< Card> desk = new ArrayList< > ();
for (int i = 0; i < 4; i++)
for (int j = 1; j < = 13 ; j++)
String suit = suits[i];
Card card = new Card(suit,j);
desk.add(card);

return desk;

/**
*
* @param cardList
*/
public static void shuffle(List< Card> cardList)
for (int i = cardList.size()-1 ; i > 0 ; i--)
Random random = new Random();
int index = random.nextInt(i);
swap(cardList,i,index);

public static void swap(List< Card> cardList,int i,int j)
Card tmp = cardList.get(i);
cardList.set(i,cardList.get(j));
cardList.set(j,tmp);

public static void main(String[] args)
List< Card> cardList = buyCard();
System.out.println("买牌"+cardList);
shuffle(cardList);
System.out.println("洗牌"+cardList);

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);

// 三个人，每个人轮流抓 5 张牌
for (int i = 0; i < 5; i++)
for (int j = 0; j < 3; j++)
//每次揭牌都去获取 cardList的 0下标的数据【删除】
Card card = cardList.remove(0);
List< Card> hand = hands.get(j);
hand.add(i,card);

System.out.println("第1个人的牌："+hand1);
System.out.println("第2个人的牌："+hand2);
System.out.println("第3个人的牌："+hand3);

System.out.println("剩余的牌"+cardList);

七.复试面试题6-116.结构体的赋值？C语言中对结构体变量的赋值或者在初始化或者在定义后按字段赋值。
7.函数参数入栈顺序？C语言函数参数入栈顺序是从右向左的
8.inline内联函数inline关键字仅仅是建议编译器做内联展开处理，即是将函数直接嵌入调用程序的主体，省去了调用/返回指令
9、“引用”与指针的区别是什么？引用必须被初始化，指针不必。
引用初始化以后不能被改变，指针可以改变所指的对象。
不存在指向空值的引用，但是存在指向空值的指针。
指针通过某个指针变量指向一个对象后，对它所指向的变量间接操作。程序中使用指针，程序的可读性差；而引用本身就是目标变量的别名，对引用的操作就是对目标变量的操作。
10、.h头文件中的ifndef/define/endif 的作用？答：防止该头文件被重复引用。

【数据结构-ArrayList和顺序表】