week06_day02_List集合&&数组和链表
接着昨天的List讲：
获取子串：
List subList(int fromIndex, int toIndex)
//范围[fromIndex,toIndex）
public class Demo01 {
public static void main(String[] args) {
List list = new ArrayList();
list.add("hello");
list.add("world");
list.add("java");
List subList = list.subList(1, 2);
System.out.println(subList); //[world]
//subList和list共享一份数据
subList.set(0, "WORLD");
System.out.println(subList); //[WORLD]
System.out.println(list); //[hello, WORLD, java]
}
}
这段代码执行完后，会发现subList和list中的值都变了，为什么呢？因为subList和list共享一份数据。把这种技术称之为视图技术。
去看ArrayList中subList的源码：
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}
subList方法只是返回了一个SubList对象，再找到SubList的源码，发现SubList是一个成员位置内部类。ArrayList底层其实就是一个数组。但是看SubList的四个成员变量，它并没有维护一个数组，说明它的数据就是通过访问外部类的数据而得到的。
利用成员位置内部类取访问外部类，这就是视图技术的原理。
private class SubList extends AbstractList<E> implements RandomAccess {
private final AbstractList<E> parent;
private final int parentOffset;
private final int offset;
int size;
SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
this.parent = parent;
this.parentOffset = fromIndex;
this.offset = offset + fromIndex;
this.size = toIndex - fromIndex;
this.modCount = ArrayList.this.modCount;
}
public E set(int index, E e) {
rangeCheck(index);
checkForComodification();
E oldValue = ArrayList.this.elementData(offset + index);
ArrayList.this.elementData[offset + index] = e;
return oldValue;
}
public E get(int index) {
rangeCheck(index);
checkForComodification();
return ArrayList.this.elementData(offset + index);
}
public int size() {
checkForComodification();
return this.size;
}
public void add(int index, E e) {
rangeCheckForAdd(index);
checkForComodification();
parent.add(parentOffset + index, e);
this.modCount = parent.modCount;
this.size++;
}
public E remove(int index) {
rangeCheck(index);
checkForComodification();
E result = parent.remove(parentOffset + index);
this.modCount = parent.modCount;
this.size--;
return result;
}
protected void removeRange(int fromIndex, int toIndex) {
checkForComodification();
parent.removeRange(parentOffset + fromIndex,
parentOffset + toIndex);
this.modCount = parent.modCount;
this.size -= toIndex - fromIndex;
}
public boolean addAll(Collection<? extends E> c) {
return addAll(this.size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
int cSize = c.size();
if (cSize==0)
return false;
checkForComodification();
parent.addAll(parentOffset + index, c);
this.modCount = parent.modCount;
this.size += cSize;
return true;
}
public Iterator<E> iterator() {
return listIterator();
}
public ListIterator<E> listIterator(final int index) {
checkForComodification();
rangeCheckForAdd(index);
final int offset = this.offset;
return new ListIterator<E>() {
int cursor = index;
int lastRet = -1;
int expectedModCount = ArrayList.this.modCount;
public boolean hasNext() {
return cursor != SubList.this.size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= SubList.this.size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (offset + i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[offset + (lastRet = i)];
}
public boolean hasPrevious() {
return cursor != 0;
}
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (offset + i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[offset + (lastRet = i)];
}
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = SubList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (offset + i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[offset + (i++)]);
}
// update once at end of iteration to reduce heap write traffic
lastRet = cursor = i;
checkForComodification();
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor - 1;
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
SubList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = ArrayList.this.modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(offset + lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
SubList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = ArrayList.this.modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (expectedModCount != ArrayList.this.modCount)
throw new ConcurrentModificationException();
}
};
}
·············································································································································································································
遍历：
-
ListIterator listIterator()
返回此列表元素的列表迭代器（按适当顺序）。 -
ListIterator listIterator(int index)
返回列表中元素的列表迭代器（按适当顺序），从列表的指定位置开始。
首先讲一下ListIterator接口：
public interface ListIterator<E.> extends Iterator
ListIterator是一个接口，继承自Iterator
API:
- 遍历：
- 正向遍历
boolean hasNext()
//以正向遍历列表时，如果列表迭代器有多个元素，则返回 true（换句话说，如果 next 返回一个元素而不是抛出异常，则返回 true）。
E next()
//返回列表中的下一个元素。 - 逆向遍历
boolean hasPrevious()
//如果以逆向遍历列表，列表迭代器有多个元素，则返回 true。
E previous()
//返回列表中的前一个元素。
public class MyDemo02 {
public static void main(String[] args) {
List list = new ArrayList();
list.add("hello");
list.add("world");
list.add("java");
//正向遍历
for (ListIterator it = list.listIterator();it.hasNext();){
//有人问，list中存的本来就是String类型啊，为什么取出来要进行强转呢？
//在List中是用父类引用指向子类对象，即用Object类的引用指向String类的对象
//所以要进行强转
String s = (String)it.next();
System.out.println(s);
}
//逆向遍历
//现在知道为啥cursor为啥的取到size()这个位置了吧
//正向遍历从0开始遍历，逆向遍历从size()开始遍历
for(ListIterator it = list.listIterator(list.size());it.hasPrevious();){
String s = (String)it.previous();
System.out.println(s);
}
}
}
- 获取位置：
int previousIndex()
//返回对 previous 的后续调用所返回元素的索引。
int nextIndex()
//返回对 next 的后续调用所返回元素的索引。
public class MyDemo_03 {
public static void main(String[] args) {
List list = new ArrayList();
list.add("hello");
list.add("world");
list.add("java");
//it位于左边界0时
ListIterator it = list.listIterator(0);
int pre = it.previousIndex();
int next = it.nextIndex();
System.out.println(pre + "," + next);
//it位于中间时
ListIterator it2 = list.listIterator(2);
int pre2 = it2.previousIndex();
int next2 = it2.nextIndex();
System.out.println(pre2 + "," + next2);
//it位于右边界size()时
ListIterator it3 = list.listIterator(3);
int pre3 = it3.previousIndex();
int next3 = it3.nextIndex();
System.out.println(pre3 + "," + next3);
}
}
- 修改列表：
void add(E e)
//将指定的元素插入列表（可选操作）。该元素直接插入到 next 返回的下一个元素的前面（如果有），或者 previous 返回的下一个元素之后（如果有）
//简单说就是将元素e插入光标后面的位置。
public class MyDemo04 {
public static void main(String[] args) {
List list = new ArrayList();
list.add("hello");
list.add("world");
list.add("java");
//在list中所有元素值为"world"后面插入元素"hello Kitty"
for(ListIterator it = list.listIterator();it.hasNext();){
String s = (String)it.next();
if(s.equals("world")){
it.add("hello Kitty");
}
//注意：ListIterator中的add方法和List中的add方法不一样
/* List
void add(String item)
向滚动列表的末尾添加指定的项*/
//这样写会报 ConcurrentModificationException 并发修改异常
if(s.equals("world")){
int index = it.nextIndex();
list.add(index,"hello Kitty");
}
}
System.out.println(list);
//在list中所有元素值为"world"前面插入元素"hello Kitty"
//逆序遍历即可
for(ListIterator it = list.listIterator(list.size());it.hasPrevious();){
String s = (String)it.previous();
if(s.equals("world")){
it.add("hello Kitty");
}
}
System.out.println(list);
}
}
- 修改列表：
void remove()
//删除的是最近返回的元素
public class MyDemo05 {
public static void main(String[] args) {
List list = new ArrayList();
list.add("hello");
list.add("world");
list.add("java");
// 如果最近没有返回元素，会怎样 报错 IllegalStateException 非法状态异常
/*ListIterator it = list.listIterator();
it.remove();*/
/*ListIterator it = list.listIterator();
it.next();
it.add("Allen");
//报错 IllegalStateException 非法状态异常 最近返回的元素移除之前不能修改集合的结构
it.remove();
System.out.println(list);*/
//在list中移除所有元素值为"world"
for (ListIterator it = list.listIterator(); it.hasNext(); ) {
String s = (String) it.next();
if (s.equals("world")) {
it.remove();
}
//注意：ListIterator中的remove方法和List中的remove方法不一样
/* List
void remove(String item)
E remove(int index)
删除指定位置的元素，并把被删除的元素返回。index范围[0,size()-1]*/
//这样写会报 ConcurrentModificationException 并发修改异常
if (s.equals("world")) {
int index = it.nextIndex();
list.remove(index);
}
}
System.out.println(list);
//逆序遍历也可以删除"world"
for (ListIterator it = list.listIterator(list.size()); it.hasPrevious(); ) {
String s = (String) it.previous();
if (s.equals("world")) {
it.remove();
}
}
System.out.println(list);
}
}
- 修改列表：
void set(E e)
//替换最近返回的元素
public class MyDemo06 {
public static void main(String[] args) {
List list = new ArrayList();
list.add("hello");
list.add("world");
list.add("java");
//将"java"修改成"javaSE"
for (ListIterator it = list.listIterator(); it.hasNext(); ) {
if ("java".equals(it.next())) {
it.set("javaSE");
}
}
System.out.println(list);
//我们发现调用List的set方法并不会报并发修改异常的错
//为啥呢么？
//只有通过List修改集合的结构的时候才会报错 ConcurrentModificationException
//现在只是改了集合某个位置的元素值，集合结构并没有增加一个元素或减少一个元素
//所以并不会报错
for (ListIterator it = list.listIterator(); it.hasNext(); ) {
if ("java".equals(it.next())) {
int index = it.previousIndex();
list.set(index,"javaSE");
}
}
System.out.println(list);
ListIterator it = list.listIterator();
it.next();
it.add("Allen");
//报错 IllegalStateException 非法状态异常 最近返回的元素移除之前不能修改集合的结构
it.set("javaSE");
System.out.println(list);
}
}
·············································································································································································································
数组
Q1: 数组我们都很熟悉，那你理解的数组是什么样的呢？它的最主要特点是什么呢？
A1:数组的本质是固定大小的连续的内存空间，并且这片连续的内存空间又被分割成等长的小空间。它最主要的特点是随机访问。
数组的长度是固定的
数组只能存储同一种数据类型的元素
注意：在Java中只有一维数组的内存空间是连续，多维数组的内存空间不一定连续。
那么数组又是如何实现随机访问的呢？
寻址公式：i_address = base_address + i * type_length
Q2: 为什么数组的索引是一般都是从0开始的呢？
假设索引不是从0开始的，而是从1开始的，那么我们有两种处理方式：
- 寻址公式变为： i_address = base_address + (i – 1) * type_length
或者 - 浪费开头的一个内存空间，寻址公式不变。
在计算机发展的初期，不管是CPU资源，还是内存资源都极为宝贵，所以在设计编程语言的时候，索引就从0开始了，而我们也一直延续了下来。
扩展：现在的编程语言有些索引是从1开始的，甚至有些编程语言还支持负数索引。
Q3: 为什么数组的效率比链表高？
CPU、内存和IO设备，它们传输数据的速率是存在很大差异的。
CPU一天，内存一年；内存一天，IO十年。
那么根据木桶理论：木桶能装多少水，取决于最短的那块木板。程序的性能主要取决于IO设备的性能？也就是说，我们提升CPU和内存的传输速率收效甚微。
实际是这样的吗？当然不是！那我们是怎么解决它们之间的速率差异的呢？
CPU 和 内存
高速缓存（预读）
编译器的指令重排序
内存和 IO
缓存：将磁盘上的数据缓存在内存。
CPU 和 IO
中断技术
通道
数组可以更好地利用CPU的高速缓存！因为数组中的数据数连续存放的，链表中的数据不是连续存放的。根据局部性原理，会优先加载到缓存中。（局部性原理是指CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中。
）
·············································································································································································································
数组的基本操作
添加 (保证元素的顺序)
最好情况：在末尾添加，O(1)
最坏情况：在开头添加，移动n个元素，O(n)
平均情况：移动 n/2 个元素，O(n)
删除 (保证元素的顺序)
最好情况：O(1)
最坏情况：移动n-1个元素，O(n)
平均情况：移动(n-1)/2个元素，O(n)
改进的删除算法，将删除后的元素标记为删除
查找
a. 根据索引查找元素：O(1)
b. 查找数组中与特定值相等的元素
①大小无序：O(n)
②大小有序（折半查找）：O(log2n)
双向链表：
很容易验证，前面那些操作，双向链表和单链表的时间复杂度是一样的。那为什么在工程上，我们用的一般是双向链表而不是单链表呢 (比如JDK中的 LinkedList & LinkedHashMap)？
那自然是双向链表有单链表没有的独特魅力——它有一条指向前驱结点的链接。
增加 (在某个结点前面添加元素)
删除 (删除该结点)
查找
a. 查找前驱结点
b. 根据索引查找元素
c. 查找链表中与特定值相等的元素
① 元素大小无序
② 元素大小有序
总结：虽然双向链表更占用内存空间，但是它在某些操作上的性能是优于单链表的。
思想：用空间换取时间。
循环链表我们用的一般比较少，但是当处理的数据具有环形结构时，就特别适合用循环链表，比如约瑟夫问题。接下来我们讨论下单链表和双向链表。
单链表：
增加(在某个结点后面添加)
删除(在某个结点后面删除)
查找
a. 根据索引查找元素
b. 查找链表中与特定值相等的元素
①元素大小有序
②元素大小无序
总结：链表增删快，查找慢。
·············································································································································································································
双向链表：
很容易验证，前面那些操作，双向链表和单链表的时间复杂度是一样的。那为什么在工程上，我们用的一般是双向链表而不是单链表呢 (比如JDK中的 LinkedList & LinkedHashMap)？
那自然是双向链表有单链表没有的独特魅力——它有一条指向前驱结点的链接。
增加 (在某个结点前面添加元素)
删除 (删除该结点)
查找
a. 查找前驱结点
b. 根据索引查找元素
c. 查找链表中与特定值相等的元素
① 元素大小无序
② 元素大小有序
总结：虽然双向链表更占用内存空间，但是它在某些操作上的性能是优于单链表的。
思想：用空间换取时间。
·············································································································································································································
缓存就是一种用空间换取时间的技术。
内存大小是有限的，所以缓存不能无限大。那么当缓存满的时候，再向缓存中添加数据，该怎么办呢？
缓存淘汰策略：
① FIFO (First In First Out)
② LFU (Least Frequently Used)（访问越少的数据越先淘汰）（可以用小顶堆来实现）
③ LRU (Least Recently Used)（淘汰最近最少未使用的数据）
LRU算法中我们就用到了链表！
添加 (认为尾节点是最近最少使用的数据)
a. 如果缓存中已经存在该数据
删除该结点，添加到头结点
b. 如果缓存中不存在该数据
① 缓存没满
添加到头结点
② 缓存满了
删除尾节点, 在头结点添加
·············································································································································································································
三道练习题：
- 求链表的中间元素
- 判断链表中是否有环
- 反转单链表
·············································································································································································································
作业：
1.LeetCode之加一
2.用链表实现一个LRU缓存 (大小为100)，要求实现添加一个数据的方法。(自己定义节点类，存储的数据类型为int)。
public class LRU {
private static final int CAPACITY = 100;
private int size;
private Node head = new Node(0); //Dummy node
private Node end = new Node(0); //Dummy node
public LRU() {
head.next = end;
end.prev = head;
}
private class Node {
int value;
Node prev;
Node next;
public Node(int value) {
this.value = value;
}
public Node(int value, Node prev, Node next) {
this.value = value;
this.prev = prev;
this.next = next;
}
}
public void add(int element) {
Node node = head.next;
while (node != end) {
if(node.value == element) break;
node = node.next;
}
// 存在
if (node != end) {
// 删除node
node.prev.next = node.next;
node.next.prev = node.prev;
// 在头部添加
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
} else {
Node x = new Node(element, head, head.next);
// 不存在，且容量未满
if (size < CAPACITY) {
head.next.prev = x;
head.next = x;
size++;
} else {
// 不存在，且容量满了
// 删除最后一个元素
end.prev = end.prev.prev;
end.prev.next = end;
// 在头部添加
head.next.prev = x;
head.next = x;
}
}
}
}
下一篇： 微信小程序 九宫格实例代码