javalist数据结构-Java数据结构-------List.pdf

javalist数据结构_Java数据结构-------List 三种List：ArrayList，Vector，LinkedList 类继承关系图 ArrayList和Vector通过数组实现，⼏乎使⽤了相同的算法；区别是ArrayList不是线程安全的，Vector绝⼤多数⽅法做了线程同步。 LinkedList通过双向链表实现。 源代码分析 1、添加元素到列表尾端(Appends the specified element to the end of this list.) ArrayList:当所需容量超过当前ArrayList的⼤⼩时，需要进⾏扩容，对性能有⼀定的影响。 优化策略：在能有效评估ArrayList数组初始值⼤⼩的情况下，指定其容量⼤⼩有助于性能提升，避免频繁的扩容。 public booleanadd(E e) { ensureCapacityInternal(size+ 1); //Increments modCount!! 确保内部数组有⾜够的空间 elementData[size++] = e;　//将元素放在数组尾部 return true; }priv Java中的List接口是集合框架的重要组成部分，它定义了一组有序的元素序列，允许有重复的元素。ArrayList、Vector和LinkedList都是List接口的实现类，它们各自具有不同的特性和使用场景。 1. ArrayList： ArrayList基于动态数组实现，提供快速的随机访问。在向ArrayList添加元素时，如果现有容量不足，会进行扩容。扩容策略是将原数组大小的1.5倍作为新的容量，以减小扩容的频率。这种设计在大多数情况下可以有效提高性能，但插入操作的时间复杂度在需要扩容时会升至O(n)。因此，若能预估ArrayList所需的初始容量，提前设置可以避免不必要的扩容，从而提高效率。以下是ArrayList添加元素到尾部的源码分析： ```java public boolean add(E e) { ensureCapacityInternal(size + 1); elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { if (elementData == EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } // ... ``` 2. Vector： Vector与ArrayList非常相似，同样是基于数组实现，但在多线程环境下，Vector提供了线程安全的保证，因为它的大部分方法都使用了synchronized关键字进行同步。这意味着在多线程环境下，多个线程可以安全地同时访问Vector，但这也导致了性能上的开销，因为每次访问都需要同步，降低了并发性能。 3. LinkedList： LinkedList使用双向链表实现，它在插入和删除元素时通常比ArrayList更高效，因为不需要移动大量的元素。但是，对于随机访问，LinkedList的性能较差，因为需要遍历链表找到指定位置的元素。以下是在LinkedList中添加元素到尾部的源码简化版： ```java public boolean add(E e) { linkLast(e); return true; } void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } ``` 4. 类继承关系： ArrayList和Vector都继承自AbstractList，实现了List接口，同时也实现了RandomAccess接口，表明它们支持快速随机访问。LinkedList则直接实现了List接口，没有实现RandomAccess，因为它不支持快速随机访问。 总结起来，选择ArrayList、Vector还是LinkedList主要取决于应用场景的需求。如果需要频繁的随机访问和较少的插入/删除操作，ArrayList是更好的选择；如果需要线程安全，可以选择Vector，但需要注意其性能开销；而如果插入和删除操作频繁，或者需要在列表头尾进行大量操作，LinkedList则是更好的选择。在实际使用中，根据业务需求权衡性能和功能，选择最适合的数据结构。