List接口

• List接口
  • ArrayList
  • LinkedList
  • Vector（过时）
  • Stack（过时）

ArrayList

ArrayList就是 动态数组，它提供了
①动态的增加和减少元素
②实现了ICollection和IList接口
③灵活的设置数组的大小

ArrayList是一个其容量能够动态增长的动态数组。它继承了AbstractList，实现了List、RandomAccess, Cloneable, java.io.Serializable。
基本的ArrayList，长于随机访问元素，但是在List中间插入和移除元素时较慢。同时，ArrayList的操作不是线程安全的！
一般在单线程中才使用ArrayList，而在多线程中一般使用Vector或者CopyOnWriteArrayList。

特点

1. 动态数组：ArrayList是Java中的一个可调整大小的数组实现。它能够根据需要自动扩展其容量，因此被称为动态数组。

2. 线程不安全：ArrayList不是线程安全的，这意味着如果多个线程同时访问同一个ArrayList实例，并且至少有一个线程从结构上修改了列表，那么它必须保持外部同步。

3. 基于索引的快速访问：ArrayList实现了List接口，允许基于索引的快速访问，包括随机访问。这意味着，无论列表有多大，通过索引访问任何元素的速度都很快。

4. 允许空值和重复值：ArrayList可以包含null元素，并且同一个值可以在列表中重复多次。

5. 自动扩容：当ArrayList中的元素数量超过其当前容量时，它会自动扩容以容纳更多的元素。默认情况下，扩容的大小为当前容量的1.5倍，但具体实现可能会根据JVM和JDK版本有所不同。

底层数据结构

ArrayList的底层数据结构是动态数组（Dynamic Array），也常被称作可变数组（Resizable Array）。本质上，它是一个基于数组实现的列表，但它可以动态地改变其大小。在ArrayList中，数组用于存储元素，并且当数组达到其容量时，ArrayList会创建一个新的、更大的数组，并将旧数组的元素复制到新数组中，从而增加其容量。

常用方法

1. add(E e)：向列表的末尾添加指定的元素。

2. add(int index, E element)：在列表的指定位置插入指定的元素。如果索引超出范围，会抛出IndexOutOfBoundsException。

3. remove(int index)：移除列表中指定位置的元素，并返回被移除的元素。如果索引超出范围，会抛出IndexOutOfBoundsException。

4. remove(Object o)：移除列表中首次出现的指定元素（如果存在）。如果列表不包含该元素，则列表不会改变。

5. get(int index)：返回列表中指定位置的元素。如果索引超出范围，会抛出IndexOutOfBoundsException。

6. set(int index, E element)：用指定元素替换列表中指定位置的元素，并返回原来位置的元素。如果索引超出范围，会抛出IndexOutOfBoundsException。

7. size()：返回列表中的元素数量。

8. isEmpty()：如果列表不包含元素，则返回true。

9. clear()：移除列表中的所有元素，使列表变为空列表。

10. contains(Object o)：如果列表包含指定的元素，则返回true。

11. indexOf(Object o)：返回列表中首次出现的指定元素的索引，如果列表不包含该元素，则返回-1。

12. lastIndexOf(Object o)：返回列表中最后一次出现的指定元素的索引，如果列表不包含该元素，则返回-1。

LinkedList

Java中的LinkedList是一个重要的集合类，具有一系列独特的特点、底层数据结构以及丰富的常用方法。

特点

1. 基于双向链表：LinkedList内部使用双向链表数据结构来存储元素，这意味着每个元素都包含指向列表中前一个和后一个元素的引用。这种结构使得在链表中进行插入和删除操作非常高效。

2. 动态扩容：与ArrayList类似，LinkedList也具有动态扩容的能力，尽管其扩容方式不同于基于数组的ArrayList。由于LinkedList是基于链表的，其“扩容”实际上是通过在链表中添加新的节点来实现的，而不是像ArrayList那样需要复制整个数组。

3. 线程不安全：LinkedList不是线程安全的，如果多个线程同时访问一个LinkedList实例而没有适当的同步，那么它可能会表现出非预期的行为。在多线程环境下，如果需要线程安全的数据结构，可以考虑使用Collections.synchronizedList(List<T> list)方法将LinkedList包装成线程安全的列表，或者使用ConcurrentLinkedQueue等并发集合。

4. 允许空值和重复值：与ArrayList相同，LinkedList也允许存储null元素，并且同一个值可以在列表中重复出现多次。

5. 高效的插入和删除：由于LinkedList是基于链表的，因此在链表的头部、尾部或任意位置插入和删除元素都非常高效，只需要修改相关节点的引用即可，时间复杂度通常为O(1)。

6. 较低的查询性能：与ArrayList相比，LinkedList在查询元素时的性能较低，因为它需要从链表的头部或尾部开始遍历到指定的索引位置。这种遍历方式相对较慢，尤其是当要查找的元素位于链表的中间或末尾时。

底层数据结构

LinkedList的底层数据结构是双向链表。每个节点（Node）都包含三个部分：存储的数据元素、指向前一个节点的引用（prev）以及指向后一个节点的引用（next）。这种结构使得在链表中进行插入和删除操作变得非常高效，因为只需要修改相邻节点的引用即可。

常用方法

LinkedList提供了丰富的常用方法，以下是其中一些主要的方法：

1. 添加元素

   • add(E e)：将指定元素添加到列表的末尾。
   • add(int index, E element)：在列表的指定位置插入指定元素。
   • addFirst(E e)：将指定元素插入此列表的开头。
   • addLast(E e)：将指定元素添加到此列表的末尾（相当于add(E e)）。

2. 删除元素

   • remove()：移除并返回此列表中的最后一个元素。
   • remove(int index)：移除列表中指定位置的元素。
   • remove(Object o)：移除列表中首次出现的指定元素（如果存在）。
   • removeFirst()：移除并返回此列表的第一个元素。
   • removeLast()：移除并返回此列表的最后一个元素。

3. 访问元素

   • get(int index)：返回列表中指定位置的元素。
   • getFirst()：返回此列表的第一个元素。
   • getLast()：返回此列表的最后一个元素。

4. 修改元素

   • set(int index, E element)：用指定元素替换列表中指定位置的元素。

5. 检查

   • isEmpty()：如果列表不包含元素，则返回true。
   • contains(Object o)：如果列表包含指定的元素，则返回true。

6. 遍历

   • 可以使用for-each循环、迭代器（Iterator）或列表迭代器（ListIterator）来遍历LinkedList。

7. 其他

   • size()：返回列表中元素的数量。
   • clear()：移除列表中的所有元素。
   • toArray()：返回包含列表中所有元素的数组。

LinkedList的这些方法使得它非常适合于需要频繁进行插入和删除操作的场景，但在需要频繁查询元素的场景下可能不是最佳选择。

Vector（过时）

Java中的Vector是一个基本的、广泛应用的数据结构，它具有一系列独特的特点、底层数据结构以及丰富的常用方法。以下是关于Vector的详细解答：

特点

1. 动态扩容：

   • Vector的容量可以根据需要自动增长。当元素数量超过了当前容量时，Vector会自动增加容量以容纳更多的元素。

2. 线程安全：

   • Vector是线程安全的，即多个线程可以同时访问和修改Vector的内容。这是通过在每个方法上添加synchronized关键字来实现的，但这也可能导致性能下降。

3. 存储任意类型元素：

   • Vector可以存储任意类型的对象，包括基本类型的包装类对象。

4. 有序性：

   • Vector中的元素是按照插入顺序进行存储的，可以根据索引位置来访问和修改元素。

5. 支持随机访问：

   • 由于Vector中的元素是按照索引顺序存储的，因此可以通过索引来快速访问和修改元素。

6. 可以进行遍历和搜索：

   • Vector提供了多种方法来遍历和搜索元素，如使用Iterator迭代器或使用contains()方法进行元素搜索。

底层数据结构

• Vector的底层数据结构是一个对象数组（Object[]）。这意味着Vector可以存储任何类型的对象。当Vector中的元素数量超过其当前容量时，它会创建一个更大的数组，并将现有元素复制到新数组中，这个过程被称为扩容。类似地，当从Vector中删除元素时，如果Vector的大小变得远小于其容量，则Vector会缩小为适当的大小，以节省内存。

常用方法

Vector提供了丰富的常用方法来操作其元素，以下是一些主要的方法：

1. 添加元素：

   • add(E e)：在Vector末尾添加指定的元素。
   • add(int index, E element)：在Vector的指定位置插入指定的元素。
   • addElement(E obj)：同add(E e)，但在较老的Java版本中更为常见。

2. 删除元素：

   • remove(int index)：移除Vector中指定位置的元素。
   • remove(Object o)：移除Vector中指定元素的第一个匹配项（如果存在）。
   • removeAll(Collection<?> c)：从Vector中移除包含在指定Collection中的所有元素。
   • removeElement(Object obj)：同remove(Object o)，但在较老的Java版本中更为常见。

3. 访问元素：

   • get(int index)：返回Vector中指定位置的元素。
   • elementAt(int index)：同get(int index)，但在较老的Java版本中更为常见。

4. 修改元素：

   • set(int index, E element)：用指定元素替换Vector中指定位置的元素。

5. 检查：

   • isEmpty()：如果Vector不包含元素，则返回true。
   • contains(Object o)：如果Vector包含指定的元素，则返回true。

6. 遍历：

   • 可以使用for-each循环、Iterator迭代器或ListIterator来遍历Vector。

7. 其他：

   • size()：返回Vector中元素的数量。
   • capacity()：返回Vector的当前容量。
   • clear()：从Vector中移除所有元素。

综上所述，Java中的Vector是一个功能强大的数据结构，适用于需要线程安全、动态扩容以及频繁索引操作的应用场景。然而，在单线程环境下或对性能有较高要求时，可能需要考虑使用其他数据结构如ArrayList。

Stack（过时）

Java中的Stack是一种遵循先进后出（LIFO，Last In First Out）原则的数据结构，它是Java集合框架的一部分，并且继承自Vector类。以下是关于Java中Stack的特点、底层数据结构以及常用方法的详细解答：

特点

1. 先进后出原则：Stack的核心特性是先进后出，即最后加入的元素会最先被移除。
2. 继承自Vector：Stack类继承自Vector类，因此它继承了Vector的所有方法，但Stack通过限制Vector的某些操作来确保其作为栈的行为。
3. 线程安全：由于Stack继承自Vector，并且Vector是线程安全的，因此Stack也是线程安全的。然而，这种线程安全性可能会导致在单线程环境下性能下降。
4. 动态扩容：与Vector一样，Stack也支持动态扩容，当元素数量超过当前容量时，会自动增加容量以容纳更多元素。

底层数据结构

Stack的底层数据结构是通过数组实现的，具体来说，它继承自Vector，而Vector是通过动态数组实现的。这意味着Stack内部也使用数组来存储元素，并且当元素数量超过数组容量时，会进行扩容操作。

常用方法

Stack类提供了一系列用于操作栈的常用方法，以下是一些主要的方法及其说明：

需要注意的是，由于Stack继承自Vector，它还继承了Vector的一些方法，如add、addElement、remove、removeAllElements、contains等。然而，在使用这些方法时需要谨慎，因为它们的行为可能与栈的先进后出原则不完全一致。例如，add和addElement方法将元素添加到栈的末尾（即栈底），而不是栈顶。因此，在大多数情况下，应该使用Stack特有的push方法来添加元素。

综上所述，Java中的Stack是一个功能强大的栈实现，它提供了丰富的方法来操作栈，并且具有线程安全性和动态扩容的特点。然而，在使用时需要注意其先进后出的原则以及与其他集合类（如Vector）的区别。