数据结构之List
·
目录
一、初始泛型
1.我们之前实现过一个顺序表，但是那个顺序表只能存放一种数据类型，不通用，我们也已知 Object 是 java 中所有类的祖先类，所以我们可以对之前的顺序表稍微改改，改成什么都可以放的
class MyArrayList{
private Object[] elem;
private int usedSize;
public MyArrayList(){
this.elem = new Object[10];
}
public void add(Object val){
this.elem[usedSize] = val;
usedSize++;
}
public Object get(int pos){
return this.elem[pos];
}
}
public class TestDemo {
public static void main(String[] args) {
MyArrayList myArrayList = new MyArrayList();
myArrayList.add(1);
myArrayList.add("hello");
String ret = (String)myArrayList.get(1);//原型为Object
System.out.println(ret);
}
}但是现在问题又来了，存放元素不能指定元素，什么都可以放；每次取出数据都需要进行强制类型转换，很麻烦，那我们继续改改：
class MyArrayList<E>{//<E>代表当前类是一个泛型类，此时的E只是一个占位符
private E[] elem;
private int usedSize;
public MyArrayList(){
//this.elem = new E[10];此处相当于private E[] elem = new E[10];error,泛型不能实例化一个泛型数组
this.elem = (E[])new Object[10];
}
public void add(E val){
this.elem[usedSize] = val;
usedSize++;
}
public E get(int pos){
return this.elem[pos];
}
}
public class TestDemo {
public static void main(String[] args) {
MyArrayList<String> myArrayList = new MyArrayList<>();
myArrayList.add("ABC");
myArrayList.add("abc");
//myArrayList.add(10);error
String ret = myArrayList.get(1);
System.out.println(ret);
MyArrayList<Integer> myArrayList2 = new MyArrayList<>();
MyArrayList<Boolean> myArrayList3 = new MyArrayList<>();
//把类型参数化
}
}泛型的意义：
（1）自动对类型进行检查
（2）自动对类型进行强制类型转换
我们在来看一个问题：
class MyArrayList<E>{//<E>代表当前类是一个泛型类，此时的E只是一个占位符
private E[] elem;
private int usedSize;
public MyArrayList(){
//this.elem = new E[10];此处相当于private E[] elem = new E[10];error,泛型不能实例化一个泛型数组
this.elem = (E[])new Object[10];//本质上来说这个也不对，但是我们先凑活着来用
}
public void add(E val){
this.elem[usedSize] = val;
usedSize++;
}
public E get(int pos){
return this.elem[pos];
}
}
public class TestDemo {
public static void main(String[] args) {
MyArrayList<String> myArrayList = new MyArrayList<>();
MyArrayList<Integer> myArrayList2 = new MyArrayList<>();
System.out.println(myArrayList);
System.out.println(myArrayList2);
}
}编译并运行该代码，输出如下：
MyArrayList@1b6d3586
MyArrayList@4554617c
我们惊奇的发现@的前面没有<>，这是因为泛型中的尖括号不参与类型的组成，那么泛型是怎么编译的呢？泛型是编译时期的一种机制，擦除机制，擦成Object
2.注意事项
为什么T[] elements = new T[size];这样是错的？
数组和泛型之间的一个重要区别是它们如何强制类型检查。具体来说，数组在运行时存储和检查类型信息。但是，泛型在编译时检查类型错误，并且在运行没有类型信息
假设T[] elements = new T[size];是对的，那么下面这段代码也可以假设是对的：
public <T> T[] getArray(int size) {
T[] genericArray = new T[size];
return genericArray;
}上面这段代码将会转换成：
public Object[] getArray(int size) {
Object[] genericArray = new Object[size];
return genericArray;
}得到这段代码后我们一般会这么做：
class MyArrayList<E>{
private E[] elem;
private int usedSize;
public MyArrayList(){
//this.elem = new E[10];
this.elem = (E[])new Object[10];
}
public void add(E val){
this.elem[usedSize] = val;
usedSize++;
}
public E get(int pos){
return this.elem[pos];
}
public Object[] getArray(int size) {
Object[] genericArray = new Object[size];
return genericArray;
}
}
public class TestDemo {
public static void main(String[] args) {
MyArrayList<String> myArrayList = new MyArrayList<>();
String[] ret = (String[]) myArrayList.getArray(10);
}
}编译并运行该代码，输出如下：
又回到了之前我们说的那个问题：我们只是将整体进行了强制类型转换，并没有把数组里的元素进行强转，所以出错了.更细处说，所有类类型的父类都是Object,数组当然也是一种类类型，因此String[]和Object[]都是Object类型的子类，它们是平级关系，不存在父子类关系（运行时异常ClassCastExceptioon出现试图将一个对象强制转换为一个并非是自己或自己的子类的对象的时候）,所以会抛出错误
其实正确的方式应该是利用反射进行创建（以后再总结）
3.总结：
（1）泛型是为了解决某些容器、算法等代码的通用性而引入，并且能在编译期间做类型检查。
（2）泛型利用的是
Object
是所有类的祖先类，并且父类的引用可以指向子类对象的特定而工作。
（3）泛型是一种编译期间的机制，即
MyArrayList<Person>
和
MyArrayList<Book>
在运行期间是一个类型。
（4）泛型是
java
中的一种合法语法，标志就是尖括号
<>
二、初始包装类
1.为什么要有包装类
Object
引用可以指向任意类型的对象，但有例外出现了，
8
种基本数据类型不是对象，那岂不是刚才的泛型机制要失效了？实际上也确实如此，为了解决这个问题，java 引入了一类特殊的类，即这
8
种基本数据类型的包装类，在使用过程中，会将类似 int
这样的值包装到一个对象中去。
2.基本数据类型和包装类直接的对应关系
| 基本数据类型 | 包装类 |
| byte | Byte |
| short | Short |
| int | Integer |
| long | Long |
| float | Float |
| double | Double |
| char | Character |
| boolean | Boolean |
注意：
（1）包装类的首字母要大写
（2）注意两组特别的：int--Integer char--Character
3.装箱和拆箱
装箱：也称装包。把简单数据类型变为包装类类型
拆箱：也称拆包。把包装类类型变为简单数据类型
public class TestDemo {
public static void main3(String[] args) {
Integer a = 123;//装箱 装包（隐式、自动）
int b = a;//拆箱 拆包（隐式、自动）
System.out.println(a+" "+b);
}
}编译并运行该代码，输出如下：
123 123
那么如何显式的装箱和拆箱呢？我们来看一下它的底层编译逻辑：
可以看到它调用了一些方法，它用valueOf()进行装箱，用intValue()进行拆箱,因此我们也可以利用这两个方法进行显式的装箱和拆箱
public class TestDemo {
public static void main3(String[] args) {
Integer a2 = Integer.valueOf(123);//显示装包
Integer a3 = new Integer(123);//Integer是一个类，所以也可以这样显式的装包
int b2 = a2.intValue();//显示的拆包
double d = a2.doubleValue();//变成double类型的
System.out.println(a+" "+b);
}
}编译并运行该代码，输出如下：
123 123
现在我们来看一道题：
public class TestDemo {
public static void main4(String[] args) {
Integer a = 123;
Integer b = 123;
System.out.println(a == b);
Integer c = 129;
Integer d = 129;
System.out.println(c == d);
}
}编译并运行该代码，输出如下：
true
false
分析如下：
这里a,b,c,d都进行了隐式的装包，那么它的底层会调用valueOf()进行装包，我们来看一下valueOf()的源码：
三、List
1.List的常用方法
| 方法 | 解释 |
|
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
|
2.ArrayList框架图
在集合框架中，ArrayList是一个普通的类，实现了List接口，具体框架图如下：
（1）ArrayList
实现了
RandomAccess
接口，表明
ArrayList
支持随机访问
（2）ArrayList
实现了
Cloneable
接口，表明
ArrayList
是可以
clone
的
（3）ArrayList
实现了
Serializable
接口，表明
ArrayList
是支持序列化的
（4）和
Vector
不同，
ArrayList
不是线程安全的，在单线程下可以使用，在多线程中可以选择
Vector
或者CopyOnWriteArrayList
（5）ArrayList
底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表
3.ArrayList的构造
| 方法 | 解释 |
| ArrayList() | 无参构造 |
| ArrayList(Collection<?extends E> c) | 利用其他Collection构建ArrayList |
| ArrayList(int initialCapacity) | 指定顺序表初始容量 |
使用用例如下：
import java.util.ArrayList;
public class TestDemo {
public static void main(String[] args) {
//构造一个空的列表
List<Integer> list1 = new ArrayList<>();
//构造一个具有10个容量的列表
List<Integer> list2 = new ArrayList<>(10);
list2.add(1);
list2.add(2);
list2.add(3);
//list3构造好之后，与list中的元素一致（使用另外一个ArrayList进行初始化）
ArrayList<Integer> list3 = new ArrayList<>(list2);
}
}4.ArrayList的遍历
（1）for循环遍历
（2）增强for循环遍历
（3）使用迭代器（它是一个对象，它的工作是遍历并选择序列中的对象，我们不必知道或关心该序列底层的结构）
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
public class TestDemo {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
//或：ArrayList<String> arrayList = new ArrayList<>();
//上述两者的区别是：此时list的方法没有arraylist的方法多，因为父类引用引用子类所指的对象，只能同通过父类引用调用父类里面的方法，不能调用子类里面的方法，除非重写
list.add("hello");
list.add("world");
//ArrayList<String> arrayList2 = new ArrayList<>(list);//使用另外一个ArrayList进行初始化
System.out.println(list);//把ArrayList内的元素以字符串的形式输出,说明它重写了toString方法
for(int i = 0; i < list.size();i++){
System.out.print(list.get(i)+" ");
}
System.out.println();
for(String s:list){
System.out.print(s+" ");
}
System.out.println();
//利用迭代器进行打印：
Iterator<String> it = list.iterator();
while(it.hasNext()){//使用hasNext()检查序列中是否还有元素 注意：一开始it指向第一个元素的前一个位置
System.out.print(it.next()+" ");//使用next()获得序列中的下一个元素
}
System.out.println();
//迭代器打印 实现了List接口的一般都可以用其来打印
ListIterator<String> it2 = list.listIterator();// ListIterator一个接口，实现了Iterator,所以它有它自己的功能，也有Iterator的功能
while(it2.hasNext()){
System.out.print(it2.next()+" ");
}
}
}
编译并运行该代码，输出如下：
[hello, world] //如上图所示
hello world
hello world
hello world
hello world
Iterator和ListIterator从方法上有一些区别：ListIterator有一些add()、remove()等方法
remove():
import java.util.ArrayList;
import java.util.ListIterator;
public class TestDemo {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("hello");
list.add("world");
ListIterator<String> it = list.listIterator();
while(it.hasNext()){
String ret = it.next();
if(ret.equals("hello")){
it.remove();//首先需要使用next方法迭代出集合中的元素，然后才能调用remove方法，否则集合可能会因为对同一个Iterator删除了多次而抛出异常lllegalstateexception(重复执行程序中的循环，直到满足某条件为止，称为Java迭代)
}else{
System.out.println(ret+" ");
}
}
System.out.println();
}
}编译并运行该代码，输出如下：
world
add()方法：
import java.util.ArrayList;
import java.util.ListIterator;
public class TestDemo {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("hello");
list.add("world");
ListIterator<String> it = list.listIterator();
while(it.hasNext()){
String ret = it.next();
if(ret.equals("hello")){
it.add("haha");
}else{
System.out.println(ret+" ");
}
}
System.out.println(list);
}
}编译并运行该代码，输出如下：
world
[hello, haha, world]
现在我们将上面的it.add("haha");改一改，改为list.add("haha");
import java.util.ArrayList;
import java.util.ListIterator;
public class TestDemo {
public static void main8(String[] args) {
ArrayList<String> list = new ArrayList<>();//(i)不是线程安全的
//CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();//(ii)线程安全的
list.add("hello");
list.add("world");
ListIterator<String> it = list.listIterator();
while(it.hasNext()){
String ret = it.next();//抛出异常
if(ret.equals("hello")){
list.add("haha");
}else{
System.out.println(ret+" ");
}
}
System.out.println(list);
}
}（i）编译并运行该程序，输出如下：
（ii）编译并运行该程序，输出如下：
world
[hello, world,haha]
5.ArrayList的扩容机制
这段代码是否有问题？
public class TestDemo {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 100; i++) {
list.add(i);
}
}
}这段代码其实并没有问题，我们看看ArrayList的底层：
所以在 List<Integer> list = new ArrayList<>();中，我们认为ArrayList的底层虽然是一个数组，但是当前的这个数组没有大小，大小为0；但是为什么我在ArrayList中add元素，没有抛出数组越界异常的问题？此时，我们需要看看add在底层是如何实现的？
所以，我们可以得出结论：
如果ArrayList调用不带参数的构造方法，那么顺序表的大小为0；当第一次add的时候，整个顺序表的容量才变为10，当这10个空间放慢了，就会开始以1.5的方式扩容。如果调用的是给定容量的构造方法，那么我们的顺序表的容量的大小就是我们给定的大小，放满了还是以1.5倍的方式去扩容
6.模拟实现ArrayList
import java.util.ArrayList;
import java.util.Arrays;
class MyArrayList<E>{
private Object[] elementData;//数据
private int usedSize;//代表有效的数据个数
private static final Object[] EMPTY_ELEMENTDATA = {};
public MyArrayList(){
this.elementData = EMPTY_ELEMENTDATA;
}
public MyArrayList(int capacity){
if(capacity > 0){
this.elementData = new Object[capacity];
}else if(capacity == 0){
this.elementData = new Object[0];
}else{
throw new IllegalArgumentException("初始化的容量不能为负数");
}
}
public boolean add(E e){
ensureCapacityInternal(usedSize + 1);//确定一个真正的容量
elementData[usedSize++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
int capacity = calculateCapacity(elementData,minCapacity);//计算出需要的容量
ensureExplicitCapacity(capacity);
}
private static int calculateCapacity(Object[] elementData, int minCapacity){
if(elementData == EMPTY_ELEMENTDATA){//elementData数组在之前是否分配过内存
return Math.max(10,minCapacity);
}
return minCapacity;//分配过就返回+1后的值
}
private void ensureExplicitCapacity(int minCapacity){
//如果进不去if语句说明数组还没放满，放满就要扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - Integer.MAX_VALUE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
public void add(int index,E e){
rangeCheckForAdd(index);//检查下标是否合法
ensureCapacityInternal(usedSize + 1);//确定真正的容量
copy(index, e);//挪数据
usedSize++;
}
private void copy(int index,E e){
for(int i = usedSize -1; i >= index; i--){
elementData[i+1] = elementData[i];
}
elementData[index] = e;
}
private void rangeCheckForAdd(int index) {
if (index > size() || index < 0)
throw new IndexOutOfBoundsException("index位置不合法，不能插入！");
}
public int size(){
return this.usedSize;
}
}
public class TestDemo {
public static void main(String[] args) {
MyArrayList<String> list = new MyArrayList<>();
list.add("abc");
list.add("efg");
list.add(0,"xyz");
}
}打断点调试，便可验证我们的ArrayList是否可以正常运行
发现模拟成功。
7.一些练习
（1）某班有若干个学生（学生对象放在一个List中），每个学生有一个姓名（String），班级（String）,和考试成绩（double），某次考试后，每个学生都获得一个考试成绩。遍历List集合，并把学生对象的属性打印出来
import java.util.ArrayList;
class Student{
public String name;
public String classes;
public double score;
public Student(String name, String classes, double score) {
this.name = name;
this.classes = classes;
this.score = score;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", classes='" + classes + '\'' +
", score=" + score +
'}';
}
}
public class TestDemo {
public static void main(String[] args) {
ArrayList<Student> students = new ArrayList<>();//<>中也可以放自定义类型
students.add(new Student("haha","13",96.6));
students.add(new Student("hehe","10",85.9));
students.add(new Student("heihei","12",90.6));
System.out.println(students);
}
}（2）有一个List当中存放的是整型的数据，要求使用Collection.sort对List进行排序
import java.util.ArrayList;
import java.util.Collections;
public class TestDemo {
public static void main(String[] args) {
ArrayList<Integer> integers = new ArrayList<>();
integers.add(11);
integers.add(6);
integers.add(9);
Collections.sort(integers);
//Collections.reverse(integers);//Collections下面有好多方法，我们可以自行慢慢学习
System.out.println(integers);
}
}编译并运行该代码，输出如下：
[6, 9, 11]
（3）删除第一个字符串当中出现的第二个字符串中的字符，如：
String str1 = "welcome to China";
String str2 = "come";
输出结果：wl t China
思路：遍历str1，如果str1中没有str2中的字符，那么就放在顺序表中
import java.util.ArrayList;
public class TestDemo {
public static void main(String[] args) {
ArrayList<Character> list = new ArrayList<>();
String str1 = "welcome to China";
String str2 = "come";
for(int i = 0; i < str1.length(); i++){
char ch = str1.charAt(i);
if(! str2.contains(ch + "")){
list.add(ch);
}
}
for(char ch:list){
System.out.print(ch);
}
}
}编译并运行该代码，输出如下：
wl t China
（4）扑克牌（买牌，洗牌，揭牌）
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
class Card{
private int rank;//数字
private String suit;//花色
public Card(int rank, String suit) {
this.rank = rank;
this.suit = suit;
}
@Override
public String toString() {
return "[ "+this.suit+" "+this.rank+" ]";
}
}
public class TestDemo {
private static final String[] suits = {"♥","♠","♣","♦"};
public static List<Card> buyCard(){
ArrayList<Card> cards = new ArrayList<>();
for(int i = 0; i < 4; i++){
for(int j = 1; j <= 13;j++){
/*String suit = suits[i];
int rank = j;
Card card = new Card(rank,suit);
cards.add(card);*/
//等价于：
cards.add(new Card(j,suits[i]));
}
}
return cards;
}
public static void swap(List<Card> cards,int i,int j){
/*Card tmp = cards[i];
cards[i] = cards[j];
cards[j] = tmp;*/ //error，它不是一个数组，我们现在在面向对象
Card tmp = cards.get(i);
cards.set(i, cards.get(j));
cards.set(j, tmp);
}
private static void shuffle(List<Card> cards){
int size = cards.size();
for(int i = size - 1; i > 0; i--){
Random random = new Random();
int rand = random.nextInt(i);
swap(cards,i,rand);
}
}
public static void main(String[] args) {
List<Card> cards = buyCard();
System.out.println("买牌"+cards);
shuffle(cards);
System.out.println("洗牌"+cards);
System.out.println("揭牌：3个人每个人轮流揭5张牌");
ArrayList<List<Card>> hand = new ArrayList<>();//二维数组
List<Card> hand1 = new ArrayList<>();
List<Card> hand2 = new ArrayList<>();
List<Card> hand3 = 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);
}
}
System.out.println("第一个人的牌："+hand1);
System.out.println("第二个人的牌："+hand2);
System.out.println("第三个人的牌："+hand3);
System.out.println("剩下的牌："+cards);
}
} 
更多推荐
0
0- 0
已为社区贡献1条内容
所有评论(0)