目录
1. 线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列...
线性表在逻辑上是线性结构，也就是说是连续的一条直线，但在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储
2. 顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删改查
3. ArrayList
- ArrayList是以泛型方式实现的，使用时必须要先实例化
- ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
- ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
- ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
- 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者CopyOnWriteArrayList
- ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表
3.1 subList方法
import java.util.ArrayList;
import java.util.List;
public class Test {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
//通过list这个引用可以调用当前类的所有可以被调用的方法
List<String> list1 = new ArrayList<String>();
//只要实现这个接口的都能引用，向上转型
//通过这个接口，只能调用这个接口当中的方法
list.add("a");
list.add("b");
list.add("c");
list.add("d");
list.add("e");
list.add("f");
list.add("g");
List<String> list2=list.subList(1,3);
System.out.println(list2);//[b, c]
System.out.println("==============");
list2.set(0,"y");
System.out.println(list2);//[y, c]
System.out.println(list);//[a, y, c, d, e, f, g]（这里强调没有创建新的对象，而是对原本对象直接进行修改）
}
}
3.2 ArrayList的遍历
使用迭代器输出元素：
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next()+" ");//a y c d e f g
}
System.out.println();使用迭代器逆向输出元素：
ListIterator<String> listIterator = list.listIterator(list.size());
while (listIterator.hasPrevious()) {
System.out.print(listIterator.previous() + " ");//g f e d c y a (倒着打印)
}
System.out.println();
3.3 ArrayList的扩容机制
- 检测是否真正需要扩容，如果是调用grow准备扩容
- 预估需要库容的大小：初步预估按照1.5倍大小扩容，如果所需大小超过1.5倍，则按照实际大小扩容，扩容之前检测是否能扩容成功，防止太大导致扩容失败
- 使用copyOf进行扩容
4. 删除两字符串重复部分
import java.util.ArrayList;
public class Test {
public static void main(String[] args) {
String list1 = "welcome to bit";
String list2 = "come";
ArrayList<Character> ret = new ArrayList<>();
for (int i = 0; i < list1.length(); i++) {
char c = list1.charAt(i);
if (!list2.contains(c + "")) {//此处为字符串
ret.add(c);
}
}
for (Character c : ret) {
System.out.print(c + "");//wl t bit
}
}
}5. 杨辉三角
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> ret = new ArrayList<>();
for (int i = 0; i < numRows; i++) {
List<Integer> row = new ArrayList<>();
for (int j = 0; j < i + 1; j++) {
int val = (j == 0 || j == i) ? 1 : (ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));
row.add(val);
}
ret.add(row);
}
return ret;
}
}6. 简单的洗牌算法
Card类：
public class Card {
private String suit;
private int rank;
public Card(String suit, int rank) {
this.suit = suit;
this.rank = rank;
}
@Override
public String toString() {
/*return "Card{" +
"suit='" + suit + '\'' +
", rank=" + rank +
'}';*/
return suit + rank;
}
}
CardDemo类：
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class CardDemo {
public static final String[] suits = {"♦", "♥", "♠", "♣"};
public List<Card> buyCard() {
List<Card> cards = new ArrayList<Card>();
for (int i = 1; i < 13; i++) {
for (int j = 0; j < 4; j++) {
int rank = i;
String suit = suits[j];
Card card = new Card(suit, rank);
cards.add(card);
}
}
return cards;
}
public void shuffle(List<Card> cards) {
Random random = new Random();
for (int i = cards.size() - 1; i > 0; i--) {
int index = random.nextInt(i);
swap(cards, index, i);
}
}
private void swap(List<Card> cards, int i, int j) {
Card temp = cards.get(i);
cards.set(i, cards.get(j));
cards.set(j, temp);
}
public List<List<Card>> play(List<Card> cards) {
List<Card> hand0 = new ArrayList<>();
List<Card> hand1 = new ArrayList<>();
List<Card> hand2 = new ArrayList<>();
List<List<Card>> hand = new ArrayList<>();
hand.add(hand0);
hand.add(hand1);
hand.add(hand2);
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 3; j++) {
Card card = cards.remove(0);
hand.get(j).add(card);
}
}
return hand;
}
}
Test类：
import java.util.ArrayList;
import java.util.List;
public class Test {
public static void main(String[] args) {
CardDemo cardDemo = new CardDemo();
List<Card> cardList = cardDemo.buyCard();//买牌
System.out.println(cardList);
cardDemo.shuffle(cardList);//洗牌
System.out.println(cardList);
List<List<Card>> ret = cardDemo.play(cardList);
for (int i = 0; i < ret.size(); i++) {
System.out.print(" NO" + (i + 1) + ":" + ret.get(i));
}
}
public static void main1(String[] args) {
String list1 = "welcome to bit";
String list2 = "come";
ArrayList<Character> ret = new ArrayList<>();
for (int i = 0; i < list1.length(); i++) {
char c = list1.charAt(i);
if (!list2.contains(c + "")) {//此处为字符串
ret.add(c);
}
}
for (Character c : ret) {
System.out.print(c + "");//wl t bit
}
}
}
7. ArrayList的问题及思考
- ArrayList底层使用连续的空间，任意位置插入或删除元素时，需要将该位置后序元素整体往前或者往后搬移，时间复杂度为O(N)
- 增容需要申请新空间，拷贝数据，释放旧空间，会有不小消耗
- 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，再继续插入5个数据，后面没有数据插入，就浪费了95个数据空间