Java中的List——有序序列
List 在 java 中是个有序序列：
⼀、容量
ArrayList 中有⼀个容量概念，表⽰基础数组的⼤⼩（⽆参时默认为 10）。在需要的时候（⽐如 add操作）会⾃动增加其容量。LinkedList 没有这个概念。
TreeMap 也有容量，默认是 16.
⼆、改善的 search ⽅法
java中字符串转数组LinkedList 与 ArrayList 都很低效O(N)。⽐如 Collection 的 contain 和 remove ⽅法⽽⾔。他们均花费线性时间。下⾯对存、取、查这三类情况进⾏⽐较：
访问数组中第 n 个数据的时间花费是 O(1) （类似地 HashMap 中通过 key 访问 value，但其存取都是 O(1) ，因为其索引是⽆序的，⽽数组是有序的索引），但是要在数组中查⼀个指定的数据则是 O(N) 。当向数组中插⼊或者删除数据的时候，最好的情况是在数组的末尾进⾏操作，时间复杂度是 O(1) ，但是最坏情况是插⼊或者删除第⼀个数据，时间复杂度是 O(N) 。在数组的任意位置插⼊或者删除数据的时候，后⾯的数据全部需要移动，移动的数据还是和数据个数有关所以总体的时间复杂度仍然是 O(N) 。
在链表中查第 n 个数据以及查指定的数据的时间复杂度是 O(N) ，但是链表插⼊和删除数据的时间复杂度是 O(1) ，因为只需要调整指针就可以。
堆栈实现了⼀种后进先出的语义 (LIFO) ，可以使⽤数组或者是链表来实现它。队列实现了先⼊先出的语义 (FIFO) 。队列也可以使⽤数组和链表来实现
提⾼运⾏效率 O(logn)，可以使⽤ Collections.binarySearch(List list)，⼆分法进⾏查，需要对原集合/数组进⾏排序（双枢纽快速排序 O(n log(n))。
注意：
Collections.binarySearch 不⽀持 Set 集合，因为 HashSet/LinkedHashSet 使⽤的是哈希表，查询值（的位置/是否存在）只需要⽐较哈希值，时间效率是 O(1)。因此不需要⼆分搜索法查。
arrayList.add(311);
arrayList.add(233);
arrayList.add(999);
arrayList.add(777);
arrayList.sort((o1, o2) -> o1 - o2);
int index = Collections.binarySearch(arrayList, 777);
if (index >= 0) {
System.out.printf("到了，索引为%s", index);
}
三、改善的 remove ⽅法（此⽅法对 ArrayList ⽆效，ArrayList 由于 remove 会改变数组结构，结构重组将花费⼤量时间。）
foreach 增强 for循环，抛异常
public static void removeEvensVer2(List<Integer> lst) {
for(Integer x : lst) {
if (x % 2 == 0)
}
}
抛异常
java.util.ConcurrentModificationException
正的 for 循环，这会删除下标为偶数的元素，因为每次删除后，后⾯的元素的下标全部减1，相当于元素位置全部左移⼀位，再次删除时，会跳过⼀个元素进⾏删除。
for(int i = 0;i < list.size();i++){
}
倒的 for循环（全部删除）
for(int i = list.size()-1 ;i >= 0 ;i--){
}
新建⼀个要删除的List，最后⼀起删除。veAll(deleteList)。
使⽤ while循环（但是这个⽅法对于 LinkedList 来说有⼏个糟糕的操作：1，使⽤ get⽅法，去遍历，在遍历的时候 get也花费线性时间。2，remove 同理，remove⽅法本⾝也花费线性时间）
public static void removeEvensVer1(List<Integer> lst) {
int i = 0;
while (i < lst.size())
if ((i) % 2 == 0)
else
i++;
}
迭代器⾃带的 remove 处理 LinkedList：
当迭代到其节点时处理 remove 该节点的元素，仅花费常数时间。此外，LinkedList 除了 Collection 借⼝提供的 iterator⽅法之外，还有扩展的()返回⼀个扩展接⼝ ListIterator<E>，具有 hasPrevious() pevious() add(Anytype x) set(AnyType newVal) ⽅法。主要⽅便从末尾向前迭代，和在迭代时添加和改变值（对于 LinkedList 改变和添加值花费较少。）
public static void removeEvensVer3(List<Integer> lst) {
Iterator<Integer> itr = lst.iterator();
while (itr.hasNext())
if (() % 2 == 0)
}
四、排序
对于有序序列，可以使⽤ Collections.sort(List<T> list, <? super T> c) 按照⾃⼰的要求进⾏排序。
对于 TreeSet/TreeMap 基于红⿊树数据结构，可以按照元素的，或者创建 set 时提供的进⾏排序。
五、 ArrayList 与 LinkedList、Array 的区别
Array 固定长度，可以包含 primitives 基础类型与对象了；
ArrayList 基于数组结构，是⼤⼩可变数组的实现。ArrayList 只能包含对象，可以使⽤泛型；
LinkedList 基于双向链表结构，List接⼝的链接列表实现。实现所有可选的列表操作，并且允许所有元素（包括null）。除了实现List接⼝外，LinkedList类还为在列表的开头及结尾get、remove和insert元素提供了统⼀的命名⽅法。这些操作允许将链接列表⽤作堆栈、队列或双端队列（实现了 Queue 与 Deque 接⼝）。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论