Java Collection | Set 1 (List)

这一讲我们来谈谈 List 接口。List 接口是 Collection 接口的子接口。
关于 List 的解释，Oracle 的官方文档上是这么说的：

An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list.

Source: https://docs.oracle.com/javase/8/docs/api/java/util/List.html

由以上这段话我们可以得到以下信息：List 接口，是有序的。该接口可以对列表中的每一个元素的插入位置进行精确的控制，同时用户可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。

List 作为一个接口，本身无法实例化，但它拥有有很多实现类: AbstractList, AbstractSequentialList, ArrayList, AttributeList, CopyOnWriteArrayList, LinkedList, RoleList, RoleUnresolvedList, Stack, Vector 我们可以通过以下方法来构造 List 对象：

List l = new ArrayList();
List l = new LinkedList();
List l = new Stack();
List l = new Vector();

List 接口拥有以下常用方法：

void add(int index,Object O);
boolean addAll(int index, Collection c);
Object remove(int index);
Object get(int index);
Object set(int index, Object newElement);
int indexOf(Object o);
int lastIndexOf(Object o)
List subList(int fromIndex,int toIndex)

Source: https://docs.oracle.com/javase/8/docs/api/java/util/List.html

示例如下：

import java.util.*;

public class ListDemo{
    public static void main(String[] args){
	// Positional Access
	List l1 = new ArrayList();
	l1.add(0, 1);    // Add 1 at index 0
	l1.add(1, 2);    // Add 2 at index 1
	System.out.println(l1);  // [1, 2]

	List l2 = new ArrayList();
	l2.add(1);
	l2.add(2);
	l2.add(3);

	l1.addAll(1, l2); // will add list l2 from 1 index
	System.out.println(l1);     // [1, 1, 2, 3, 2]

	l1.remove(1);   // remove element from index 1
	System.out.println(l1);  // [1, 2, 3, 2]

	// prints elements at index 3
	System.out.println(l1.get(3));    // 2

	l1.set(0, 5);   // replace oth element with 5
	System.out.println(l1);   // [5, 2, 3, 2]

	// Search
	List<String> l = new ArrayList<>(5);
	l.add("Future");
	l.add("Googler");
	l.add("Future");
	System.out.println("First index of Future: " + l.indexOf("Future"));   // 0
	System.out.println("Last index of Future: " + l.lastIndexOf("Future")); // 2
	System.out.println("Elements that not present: "  +l.indexOf("Facebook")); // -1

	// Range review
	l.add("Andriod");
	l.add("FrontEnd");
	List<String> range = new ArrayList<>();
	range = l.subList(2, 4);
	System.out.println(range);   // [Future, Andriod]
    }
}

Source：http://www.geeksforgeeks.org/list-interface-java-examples/

在 List 接口的很多个实现类中，常用的有 ArrayList, LinkedList, Stack, Vector, 下面我们来逐一分析

ArrayList

Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to Vector, except that it is unsynchronized.)

Source: https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html

import java.util.*;

public class ArrayListDemo{
    public static void main(String[] args){
	ArrayList<Integer> l = new ArrayList<>(5);

	for (int i = 0; i < 5; i++){
   	    l.add(i);
	}
	System.out.println(l);  // [0, 1, 2, 3, 4]

	l.remove(3);  // remove element at index 3

	System.out.println(l);  // [0, 1, 2, 4]

	for (int i = 0; i < l.size(); i++){
   	    System.out.print(l.get(i) + " ");   // 0 1 2 4
	}
    }
}

How to sort and reverse ArrayList in Java

Collections.sort(A);
Collections.reverse(A);

LinkedList

LinkedList 的常用方法如下

boolean add(Object element);
void add(int index, Object element);
void addFirst(Object element);
void addLast(Object element);
boolean contains(Object element);
Object get(int index);
int indexOf(Object element);
Object remove(int index);
int size();
void clear();

示例如下

import java.util.LinkedList;

public class LinkedListDemo{
    public static void main(String[] args){

	LinkedList <String> l = new LinkedList<String>();

	l.add("A");
	l.add("B");
	l.add("C");
	l.add("D");
	l.add("E");
	l.add("F");
	l.add("G");
	System.out.println(l);    // [A, B, C, D, E, F, G]

	l.remove("B");
	l.remove(3);
	l.removeFirst();
	l.removeLast();
	System.out.println(l);   // [C, D, F]

	System.out.println("list contains element E: " + l.contains("E"));  // false
	System.out.println("list size: " + l.size());   // 3
	System.out.println("Element returned by get() : " + l.get(2));   // F
	l.set(2, "Y");
	System.out.println("LinkedList after change: " + l);  // [C, D, Y]
    }
}

Vector

vector 与 ArrayList 极其相似，但它拥有更多的方法：

void ensureCapacity(int minCapacity);

Vector v = new Vector();

v.ensureCapacity(22);  // ensuring capacity

// cheking capacity
System.out.println("Minimum capacity: " + v.capacity());  // 22

boolean equals(Object o)

Vector v1 = new Vector();

v1.add(1);
v1.add(2);
v1.add("Future");
v1.add("Googler");
v1.add(4);

// second vector
Vector v2 = new Vector();

v2.add(1);
v2.add(2);
v2.add("Future");
v2.add("Googler");
v2.add(4);

if(v1.equals(v2)){
    System.out.println("both vectors are equal");
}

void trimToSize()

This method trims the capacity of this vector to be the vector’s current size.

// create default vector of capacity 10
Vector v = new Vector();

v.add(1);
v.add(2);
v.add("Future");
v.add("Googler");
v.add(4);

// checking initial capacity
System.out.println("Initial capacity: " + v.capacity());

// trim capacity to size
v.trimToSize();

// checking capacity after triming
System.out.println("capacity after triming: " + v.capacity());

值得注意的是该方法：

void setElementAt(Object obj, int index);

替换的对象在第一个参数，索引位置在第二个参数

Stack

Stack 作为一种数据结构，其特点是后进先出 (Last In First Out)。Java 也提供了该数据结构的封装。

其方法主要有如下几种：push(Object element), pop(), peek( ), empty(), search(Object element)
示例如下

import java.util.Stack;

public class StackDemo{
    public static void main(String[] args){
	Stack<Integer> stack = new Stack<Integer>();

	// Pushes an element on the top of the stack.
	for (int i = 0; i < 5; i++){
  	    stack.push(i);
	}
	System.out.println("After push: " + stack);  // [0, 1, 2, 3, 4]

	/* Removes and returns the top element of the stack. An ‘EmptyStackException’
	exception is thrown if we call pop() when the invoking stack is empty.*/
	Integer temp1 = (Integer) stack.pop();
	System.out.println(temp1);   // 4
	System.out.println("After pop: " + stack);  // [0, 1, 2, 3]

	// Returns the element on the top of the stack, but does not remove it.
	Integer temp2 = (Integer) stack.peek();
	System.out.println(temp2);   // 3
	System.out.println(stack);   // [0, 1, 2, 3]

	/*determines whether an object exists in the stack. If the element is found, it
	returns the position of the element from the top of the stack. Else, it returns -1*/
	System.out.println(stack.search(0));   // 4
	System.out.println(stack.search(4));   // -1
    }
}

Stack 还有一种比较有趣的应用，这种数据结构可以用来配对括号或HTML标签

Stack 配对括号

比如在数学表达式中，会有很多圆括号，中括号，大括号
Parentheses: “(“ and “)”
Braces: “{“ and “}”
Brackets: “[“ and “]”
每一个开括号都必须与一个对应的闭括号匹配
如 [(1 + x) / (1 + y)] + 5 中 “[“ 与 “]” 要匹配

我们来看如下几个例子：
正确：()(()){([{}])}
正确：()({)()
错误：(
错误：()(){]

如何运用 Stack 的 LIFO 特点来实现匹配括号的功能呢，思路如下：
从左到右扫描，遇到开括号 push 进 Stack，遇到对应的闭括号 pop 掉，如果最后 Stack 为空，说明这是一个有效的表达式

import java.util.Stack;

public class StackApp{
    public static boolean isMatched(String str){
	final String opening = "([{";
	final String closing = ")]}";

	Stack<Character> stack = new Stack<>();
	for (char c : str.toCharArray()){
	    if (opening.indexOf(c) != -1){
		stack.push(c);
	    }
	    else if (closing.indexOf(c) != -1){
		if (stack.isEmpty()){
		    return false;
		}
		else if (closing.indexOf(c) != opening.indexOf(stack.pop())){
		    return false;
		}
	    }
	}
	return stack.isEmpty();		
    }

    public static void main(String[] args){
 	System.out.println(isMatched("()()()[{}]"));   // true
	System.out.println(isMatched("{}(]"));    // false
	System.out.println(isMatched("[(])"));    // false
    }
}

既然我们可以判断一个数学表达式是否是有效的
那当然也可以计算该数学表达式的值
给定一个数学表达式，如：(1 + ((2 + 3) * (4 * 5))), 如何计算呢
E.W.Dijistra 在1960年代想出了一种算法，使用两个 Stack，思路如下：

Push operands onto the operand stack
Push operators onto the opertor stack
Ingore left parantheses
On encountering a right parenthesis,pop an operator, pop the requisite number of operands, and push onto the operand stack the result of applying that operator to those operands

Java 代码实现如下

import java.util.Stack;

public class Evaluate{
    public static void main(String[] args){
	Stack<Character> ops = new Stack<>();
	Stack<Double> value = new Stack<>();

	String str = "(1 + ((2 + 3) * (4 * 5)))";
	for (int i = 0; i < str.length(); i++){
	    char c = str.charAt(i);
	    if (c == '(' || c == ' ');    // Ignore left parathese and whitespaces
	    else if (c == '+' || c == '-' || c == '*' || c == '/') ops.push(c);
	    else if (c == ')'){
		char op = ops.pop();
		double v = value.pop();
		if (op == '+') v = value.pop() + v;
		if (op == '-') v = value.pop() - v;
		if (op == '*') v = value.pop() * v;
		if (op == '/') v = value.pop() / v;
		value.push(v);
	    }
	    else{
		try{
		    Double temp = Double.parseDouble(str.charAt(i) + "");
		    value.push(temp);
		} catch (Exception e){
		    System.out.println("The expression only allowed whitespace, number and operators.");
		}
	    }
	}
	System.out.println(value.pop());   // 101.0
    }
}

Reference: Algorithms (4th edition) (Page 128 - Page 129)

Stack 配对 HTML 标签

import java.util.Stack;

public class StackApp{
    public static boolean isHTMLMatched(String html){
	Stack<String> stack = new Stack<>();
	int j = html.indexOf("<");
	while (j != -1){
   	    int k = html.indexOf(">", j + 1);
 	    if (k == -1) return false;

	    String tag = html.substring(j + 1, k);
	    if (!tag.startsWith("/")){     // this is a opening tag
		stack.push(tag);
	    }
	    else {
		if (stack.isEmpty()) {
		    return false;
		}
		if (!tag.substring(1).equals(stack.pop())){
	  	    return false;
		}
	    }
	    j = html.indexOf("<", k + 1);
	}
	return stack.isEmpty();
    }

    public static void main(String[] args){
	String str = "<html><head><title></title></head><body></body></html>";
	System.out.println(isHTMLMatched(str));   // true
    }
}

---

关于 List 接口的讨论就到这里，以上内容如有疏漏或不足之处，欢迎与我讨论：
邮箱：entropy714@gmail.com
微信：cobain0714

Reference:

1. Geeksforgeeks
2. Oracle 官方文档
3. Data Structure and Algorithms in Java (7th edition) (Page 235 - Page237)