表栈和队列.md

抽象数据类型ADT

• 带有一组操作和一些对象的集合，在ADT的定义中没有地方提到关于这组操作是如何实现的任何解释。

链表

• 简单链表
• 双向链表
• 循环链表

ArrayList实现

• 对于get和set的调用花费常数时间，但是对于add和remove的开销比较巨大
• 具有初始构造大小，查阅资料发现答案不一致，有说构造时容量为10的，也有说采用了懒加载机制，构造时大小为0，在add时在将空间设置为10的，源码版本不同带来了不同的结果。

LinkedList实现

• 对于add和remove的调用花费常数时间，但是对于set的开销比较大

例程

public static int sum(List<Integer> list){
	int total = 0;
    for(int i=0;i<N;i++){
        total+=list.get(i);
    }
    return total;
}
//当使用get方法时，对于ArrayList其运行时间为O(N)，LinkedList的运行时间为O(N^2)
//但是，如果改写为增强for循环，则运行时间均为O(N)

//迭代器删除，不适用于ArrayList
public static void removeEvensVer(List<Integer> list){
    Iterator<Integer> iterator = list.iterator();
    while (iterator.hasNext()) {
        if (iterator.next() % 2 == 0) {
            iterator.remove();
        }
    }
}
//Java8中的新写法
public static void removeEvensVer(List<Integer> list) {
    list.removeIf(integer -> integer % 2 == 0);
}
//removeIf()但满足规则时进行删除
//integer -> integer % 2 == 0为lambada表达式