梅庄

java语言程序设计-基础篇-进阶篇-读书笔记5

发表于 | 分类于
第20章读书小结(lists&stacks&queues&priority queues)

Lists, Stacks, Queues，and Priority Queues

参考博客

Collections

The Collection interface defines the common operations for lists, vectors, stacks, queues, priority queues and sets
Collection和Map是两个不同的接口

List和Set

Collection派生出了两个子接口，一个是List另一个则是Set。
List:称为可重复集，顾名思义，该集合中是允许存放重复元素的，那么何为重复元素？

　　　　重复元素指的并非是同一个元素，而是指equals方法比较为true的元素。
Set:称为不可重复集，所以，该集合中是不能将相同的元素存入集合两次，同List，

　　　　这里相同指的也是两个元素的equals比较结果为true。 不会出现true的情况

集合持有对象的引用

集合当中 放的都是引用 是地址

集合中存储的都是引用类型的元素，那么引用类型变量实际上存储的是对象的“地址”，所以实际上集合只存储了元素对象在堆中的地址。

而并不是将对象本身存入了集合中。

  • Sets 用于存储nonduplicate元素
  • Lists 用于存储有序元素
  • Stacks 后进先出
  • PriorityQueues 先进先出 Collection中存储的是object retainAll:保留同时存在于集合C和该集合的元素
    removeAll:从该集合中移除C中的所有元素
    toArray:为该集合的元素返回一个Object数组
    1
    2
    ArrayList<Double> list = new ArrayList();
    List<Double> list2 = (List<Double>) list.clone();

list中元素改变不会影响list2

Iterators

用来遍历
Each collection is Iterator

1
2
3
4
5
Iterator<String> iterator = collection.iterator();
while (iterator.hasNext()) 
{         
    System.out.print(iterator.next().toUpperCase() + " "); 
}

也可以改用foreach loop

1
2
for (String element: collection)  
    System.out.print(element.toUpperCase() + " ");

Lists

实现了Collection接口，用来存放有序的元素
The List interface extends Collection to define an ordered collection with duplicates allowed.

add（index, element):用于在指定下标出插入一个元素
addAll(index, collection):用于在指定下标出插入一个元素的集合
remove(index):用于删除指定下标处的元素
set(index, element):在index处设置一个新元素
indexOf(element):用于获取指定元素在list中第一次出现的下标
lastIndexOf(element):用于获取指定元素在List中最后一次出现时的下标
subList(fromIndex, toIndex):可以获得一个子list

ListIterator接口继承了Iterator接口，以增加对list的双向遍历能力
数组的大小是可以动态增大或减小的。然而数组一旦被创建，它的大小是固定的。
如果应用程序不需要再list中插入或删除元素，那么数组是效率最高的数据结构

ArrayList

ArrayList使用可变大小的数组（resizable-array)实现List接口
ArrayList用于数组存储元素，这个数组是动态创建的。如果元素个数超过了数组的容量，就创建一个更大的新数组，并将当前数组中的所有元素都复制到新数组中。
适合通过下标随机访问元素，而不会在线性表起始位置插入或删除元素

.Each ArrayList instance has a capacity, which is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically. An ArrayList does not automatically shrink.
trimToSize():将数组容量减小到list的大小
ArrayList可以用no-arg constructororArrayList(Collection), orArrayList(initialCapacity)创建

LinkedList

LinkedList在链表中存储元素。
如需要在线性表的起始位置上插入或删除元素，选

LinkedList is a linked list implementation of the List interface.
提供从list两端提取、插入和删除的方法
A LinkedList can be constructed using its no-arg constructor or LinkedList(Collection).

实例&比较

输出

线性表可以存储相同（identical)的元素
ArrayList获取元素（retrieve elements)的效率比较高
LinkedList is efficient for inserting and removing elements at the beginning of the list.
两种线性表在中间或者末尾位置插入和删除元素方面具有相同的性能

The get(i) method is available for a linked list, but it is a time-consuming operation. Do not use it to traverse all the elements in a list as shown in (a). Instead you should use an iterator as shown in (b). Note that a foreach loop uses an iterator implicitly.

Tip

asList从可变长（variable-length)list of arguments 中创建线性表

1
2
List<String> list1 = Arrays.asList("red", "green", "blue");
List<Integer> list2 = Arrays.asList(10,20,30,40,50);

需要注意的是，这样返回的集合我们不能对其增删元素，否则会抛出异常。并且对集合的元素进行的修改会影响数组对应的元素。

Comperator

这部分参考大牛博客
Comparator可以用于比较没有实现Comparable的类的对象
实现Comparable接口来比较元素，比如String,Date,Calendar,BigInteger,BigDecimal以及基础类型包装类。
Comparable接口定义了compareTo方法，用于比较实现了Comparable接口的同一个类的两个元素
一旦Java类实现了Comparable，其比较逻辑就已经确定；如果希望在排序的操作中临时指定比较规则，可以采用Comparator接口回调的方式。
当元素自身提供的比较规则 不能满足我们对排序的需求时，我们就可以提供一个比较器，来指定比较规则
若元素没有实现Comparable接口，需要创建一个实现java.util.Comparator< T >接口的类并重写compare方法

1
public int compare(T element1, T element2)

比如：

为了使数据结构能够成功序列化，比较器（如果提供）必需实现Serializable接口

Comparator适用场景
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
class TestListD3{
    public static void main(String[] args) {
        
        List<String> list = new ArrayList<String>();
        list.add("你好");
        list.add("李绪春");
        list.add("张飞");
        list.add("刘苍松");
        list.add("范传奇");
        Collections.sort(list);
        /*
         * Collections提供了一个重载的sort方法
         * static void sort(List list,Comparator c)
         * 该方法根据给定的比较器对集合元素进行大小的比较
         * 后进行自然排序
         */
        /*
         * 使用匿名内部类定义比较器（推荐做法）
         * 临时用一下  所以 可以直接写成  匿名内部类
         * 当我们需要使用某一个借口的实现类的实例或一个类的子类实例时，这时我们使用
         * 内部类的最佳时机，匿名内部类的特点是不需要声明类，且只有一个实例
         */
        Comparator com = new Comparator<String>(){
            public int compare(String o1, String o2) {
                /*
                 * 排序后 字符多的在前
                 */
                return o2.length()- o1.length();
            }
        };
        Collections.sort(list,com);
        System.out.println(list);
        
    }
}

Comparator用于比较没有实现Comparable的类的对象
Comparable用于比较实现Comparable的类的对象

回顾Comparable

以下是实现Comparable后进行比较
实现Comparable接口需要实现compareTo(E o)方法
定义如下：

1
2
3
public interface Comparable<E>{
    public int compareTo(E o);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
public class ComparableRectangle extends Rectangle
    implements Comparable<ComparableRectangle>{
	    public ComparableRectangle(double width, double height){
		    super(width, height);
		}
		@Override
		public int compareTo(ComparableRectngle o)
		{
		    if(getArea() > o.getArea())    return 1;
			else if(getArea() < o.getArea()) return -1;
			else return 0;
		}
	}

Comparable适用场景

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
class Cell implements Comparable<Cell>{
    private int row;
    private int col;
    @Override
    /*
     * 比较规则 ：谁的行数大谁大
     *  
     *  谁的行数小 谁大
     */
    public int compareTo(Cell o){
        return this.row- o.row;
//        return o.row-this.row ;
        
    }
}
/**
 * 对Cell类进行自然排序
 * @author Administrator
 *
 */
class TestListD2{
    public static void main(String[] args) {
        List<Cell> list = new ArrayList<Cell>();
        list.add(new Cell(2,3));
        list.add(new Cell(5,1));
        list.add(new Cell(3,2));
        System.out.println(list);
        /*
         * 若集合中的元素没有实现Comparable接口
         * 那么调用sort方法编译不通过
         */
        Collections.sort(list);
        System.out.println(list);
    }
}

Static Methods for Lists and Collections

The Collections class contains the
for Lists : sort, binarySearch, reverse, shuffle, copy and fill methods
for collections : max, min, disjoint, and frequency

sort in ascending order

sort in descending order

binarySearch

To use binarySearch,the list must be sorted in increasing order.
If the key is not in the list , the method returns -(insertion point + 1)
The insertion point is where the item would fall in the list if it were present


reverse

reverse the elements in a list

shuffle

shuffle(List) randomly reorder the element elements in a list.

1
Collections.shuffle(List, Random);

copy(det, src)

copy(det, src)：copy all the elements from a source list to a copy destination list on the same index


The copy method performs a shallow copy: only the references of the elements from the source list are copied. (疑问)

nCopies(int n, Object o)

nCopies create an immutable list that consists of n copies of the specified object.

The list created from the nCopies method is immutable, so you cannot add, remove, or update elements in the list.

fill(List list, Object o)

fill：replace all the elements in the list with the specified element.

输出:【black, black, black】

disjoint(collection1, collection2)

disjoint returns true if the two collections have no elements in common.

frequency(collecion, element)

frequency finds the number of occurrences of the element in the collection