本篇是Java笔记10的复习,顺便捎带了点数据结构中的链表和树.
ArrayList
与数组的区别
如果要存放多个对象，可以使用数组，但是数组有局限性.比如:声明长度是10的数组,不用的数组就浪费了,超过10的个数，又放不下.
为了解决数组的局限性，引入容器类的概念。最常见的容器类就是ArrayList容器的容量”capacity”会随着对象的增加，自动增长只需要不断往容器里增加英雄即可，不用担心会出现数组的边界问题。
常用方法:
add
有两种用法:
第一种是直接add对象，把对象加在最后面
heros.add(new Hero("hero " + i));
第二种是在指定位置加对象
heros.add(3, specialHero);
判断是否存在
通过方法contains判断一个对象是否在容器中
contains(Object o)
判断标准:是否是同一个对象，而不是name是否相同
获取指定位置的对象
get(int index)
通过get获取指定位置的对象，如果输入的下标越界，一样会报错
获取对象所处的位置
indexOf用于判断一个对象在ArrayList中所处的位置 与contains一样，判断标准是对象是否相同，而非对象的name值是否相等
删除
remove用于把对象从ArrayList中删除
remove可以根据下标删除ArrayList的元素
heros.remove(2);
heros.remove(specialHero);
替换
set用于替换指定位置的元素
set(int index, E element)
获取大小
size用于获取ArrayList的大小
转换为数组
toArray可以把一个ArrayList对象转换为数组。 需要注意的是，如果要转换为一个Hero数组，那么需要传递一个Hero数组类型的对象给toArray()，这样toArray方法才知道，你希望转换为哪种类型的数组，否则只能转换为Object数组
Hero hs[] = (Hero[])heros.toArray(new Hero[]{});
把另一个容器所有对象都加进来
addAll
清空
clear清空一个ArrayList
其他方法参见我Java笔记10.
遍历
- 普通for循环
- foreach循环
- 迭代器循环
- Lambda表达式
LinkedList
双向链表
LinkedList除了实现了List接口外，LinkedList还实现了双向链表结构Deque，可以很方便的在头尾插入删除数据
什么是链表结构: 与数组结构相比较，数组结构，就好像是电影院，每个位置都有标示，每个位置之间的间隔都是一样的。 而链表就相当于佛珠，每个珠子，只连接前一个和后一个，不用关心除此之外的其他佛珠在哪里。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| package collection;
import java.util.LinkedList;
import charactor.Hero;
public class TestCollection {
public static void main(String[] args) {
LinkedList<Hero> ll =new LinkedList<Hero>();
ll.addLast(new Hero("hero1"));
ll.addLast(new Hero("hero2"));
ll.addLast(new Hero("hero3"));
System.out.println(ll);
ll.addFirst(new Hero("heroX"));
System.out.println(ll);
System.out.println(ll.getFirst());
System.out.println(ll.getLast());
System.out.println(ll);
System.out.println(ll.removeFirst());
System.out.println(ll.removeLast());
System.out.println(ll);
}
}
|
队列
LinkedList除了实现了List和Deque外，还实现了Queue接口(队列)。Queue是先进先出队列 FIFO，常用方法:
offer在最后添加元素
poll取出第一个元素
peek查看第一个元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| package collection;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import charactor.Hero;
public class TestCollection {
public static void main(String[] args) {
List ll =new LinkedList<Hero>();
Queue<Hero> q= new LinkedList<Hero>();
System.out.print("初始化队列：\t");
q.offer(new Hero("Hero1"));
q.offer(new Hero("Hero2"));
q.offer(new Hero("Hero3"));
q.offer(new Hero("Hero4"));
System.out.println(q);
System.out.print("把第一个元素取poll()出来:\t");
Hero h = q.poll();
System.out.println(h);
System.out.print("取出第一个元素之后的队列:\t");
System.out.println(q);
h=q.peek();
System.out.print("查看peek()第一个元素:\t");
System.out.println(h);
System.out.print("查看并不会导致第一个元素被取出来:\t");
System.out.println(q);
}
}
|
ArrayList和LinkedList的区别
ArrayList 插入，删除数据慢
LinkedList，插入，删除数据快
ArrayList是顺序结构，所以定位很快，指哪找哪。 就像电影院位置一样，有了电影票，一下就找到位置了.
LinkedList 是链表结构，就像手里的一串佛珠，要找出第99个佛珠，必须得一个一个的数过去，所以定位慢.
比较 ArrayList和LinkedList 在最后面插入100000条数据，谁快谁慢？为什么？
直接调用add方法，就表示在最后插入数据 因为是插入在最后面，所以对于数组而言，并没有一个移动很多数据的需要，所以也非常的快 而链表本身就很快，无论插入在哪里
在List的中间位置，插入数据，比较ArrayList快，还是LinkedList快，并解释为什么？
在这个位置插入数据
数组定位很快，插入数据比较慢
链表定位很慢，插入数据比较快
最后发现，当总数是10000条的时候，链表定位的总开支要比数组插入的总开支更多，所以最后整体表现，数组会更好。 如果总数是1000条，结果可能就不一样了。
二叉树
二叉树由各种节点组成 二叉树特点： 每个节点都可以有左子节点，右子节点,每一个节点都有一个值.
假设通过二叉树对如下10个随机数进行排序 67,7,30,73,10,0,78,81,10,74 排序的第一个步骤是把数据插入到该二叉树中 插入基本逻辑是，小、相同的放左边，大的放右边
67 放在根节点
7 比 67小，放在67的左节点
30 比67 小，找到67的左节点7，30比7大，就放在7的右节点
73 比67大， 放在67得右节点
10 比 67小，找到67的左节点7，10比7大，找到7的右节点30，10比30小，放在30的左节点。
… …
9.10比67小，找到67的左节点7，10比7大，找到7的右节点30，10比30小，找到30的左节点10，10和10一样大，放在左边
通过上一个步骤的插入行为，实际上，数据就已经排好序了。
接下来要做的是看，把这些已经排好序的数据，遍历成我们常用的List或者数组的形式
二叉树的遍历分左序，中序，右序
左序即： 中间的数遍历后放在左边
中序即： 中间的数遍历后放在中间
右序即： 中间的数遍历后放在右边
我们希望遍历后的结果是从小到大的，所以应该采用中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| package collection;
import java.util.ArrayList;
import java.util.List;
public class Node {
public Node leftNode;
public Node rightNode;
public Object value;
public void add(Object v) {
if (null == value)
value = v;
else {
if ((Integer) v -((Integer)value) <= 0) {
if (null == leftNode)
leftNode = new Node();
leftNode.add(v);
}
else {
if (null == rightNode)
rightNode = new Node();
rightNode.add(v);
}
}
}
public List<Object> values() {
List<Object> values = new ArrayList<>();
if (null != leftNode)
values.addAll(leftNode.values());
values.add(value);
if (null != rightNode)
values.addAll(rightNode.values());
return values;
}
public static void main(String[] args) {
int randoms[] = new int[] { 67, 7, 30, 73, 10, 0, 78, 81, 10, 74 };
Node roots = new Node();
for (int number : randoms) {
roots.add(number);
}
System.out.println(roots.values());
}
}
|
比较冒泡法，选择法以及二叉树排序的性能区别
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
| package collection;
import java.util.Arrays;
import java.util.List;
public class SortCompare {
public static void main(String[] args) {
int total = 40000;
System.out.println("初始化一个长度是"+total+"的随机数字的数组");
int[] originalNumbers = new int[total];
for (int i = 0; i < originalNumbers.length; i++) {
originalNumbers[i] = (int)(Math.random()*total);
}
System.out.println("初始化完毕");
System.out.println("接下来分别用3种算法进行排序");
int[] use4sort;
use4sort= Arrays.copyOf(originalNumbers, originalNumbers.length);
int[] sortedNumbersBySelection= performance(new SelectionSort(use4sort),"选择法");
use4sort= Arrays.copyOf(originalNumbers, originalNumbers.length);
int[] sortedNumbersByBubbling=performance(new BubblingSort(use4sort),"冒泡法");
use4sort= Arrays.copyOf(originalNumbers, originalNumbers.length);
int[] sortedNumbersByTree=performance(new TreeSort(use4sort),"二叉树");
System.out.println("查看排序结果，是否是不同的数组对象");
System.out.println(sortedNumbersBySelection);
System.out.println(sortedNumbersByBubbling);
System.out.println(sortedNumbersByTree);
System.out.println("查看排序结果，内容是否相同");
System.out.println("比较 选择法 和 冒泡法 排序结果：");
System.out.println(Arrays.equals(sortedNumbersBySelection, sortedNumbersByBubbling));
System.out.println("比较 选择法 和 二叉树 排序结果：");
System.out.println(Arrays.equals(sortedNumbersBySelection, sortedNumbersByTree));
}
interface Sort{
void sort();
int[] values();
}
static class SelectionSort implements Sort{
int numbers[];
SelectionSort(int [] numbers){
this.numbers = numbers;
}
@Override
public void sort() {
for (int j = 0; j < numbers.length-1; j++) {
for (int i = j+1; i < numbers.length; i++) {
if(numbers[i]<numbers[j]){
int temp = numbers[j];
numbers[j] = numbers[i];
numbers[i] = temp;
}
}
}
}
@Override
public int[] values() {
return numbers;
}
}
static class BubblingSort implements Sort{
int numbers[];
BubblingSort(int [] numbers){
this.numbers = numbers;
}
@Override
public void sort() {
for (int j = 0; j < numbers.length; j++) {
for (int i = 0; i < numbers.length-j-1; i++) {
if(numbers[i]>numbers[i+1]){
int temp = numbers[i];
numbers[i] = numbers[i+1];
numbers[i+1] = temp;
}
}
}
}
@Override
public int[] values() {
return numbers;
}
}
static class TreeSort implements Sort{
int numbers[];
Node n;
TreeSort(int [] numbers){
n =new Node();
this.numbers = numbers;
}
@Override
public void sort() {
for (int i : numbers) {
n.add(i);
}
}
@Override
public int[] values() {
List<Object> list = n.values();
int sortedNumbers[] = new int[list.size()];
for (int i = 0; i < sortedNumbers.length; i++) {
sortedNumbers[i] = Integer.parseInt(list.get(i).toString());
}
return sortedNumbers;
}
}
private static int[] performance(Sort algorithm, String type) {
long start = System.currentTimeMillis();
algorithm.sort();
int sortedNumbers[] = algorithm.values();
long end = System.currentTimeMillis();
System.out.printf("%s排序，一共耗时 %d 毫秒%n",type,end-start);
return sortedNumbers;
}
}
|
卒,写着写着发现还没我原来写的好,这篇就到这吧,不写了.
