linkedlist常用方法

㈠ LinkedList和ArrayList的区别

ArrayList

ArrayList是一个动态数组，也是我们最常用的集合。

它允许任何符合规则的元素插入甚至包括null。每一个ArrayList都有一个初始容量（10），该容量代表了数组的大小。随着容器中的元素不断增加，容器的大小也会随着增加。

在每次向容器中增加元素的同时都会进行容量检查，当快溢出时，就会进行扩容操作。

所以如果我们明确所插入元素的多少，最好指定一个初始容量值，避免过多的进行扩容操作而浪费时间、效率。size、isEmpty、get、set、iterator 和 listIterator 操作都以固定时间运行。

add 操作以分摊的固定时间运行，也就是说，添加 n 个元素需要 O(n) 时间（由于要考虑到扩容，所以这不只是添加元素会带来分摊固定时间开销那样简单）。

ArrayList擅长于随机访问。同时ArrayList是异步的。
LinkedList

同样实现List接口的LinkedList与ArrayList不同，ArrayList是一个动态数组，而LinkedList是一个双向链表。

所以它除了有ArrayList的基本操作方法外还额外提供了get，remove，insert方法在LinkedList的首部或尾部。由于实现的方式不同，LinkedList不能随机访问，它所有的操作都是要按照双重链表的需要执行。

在列表中索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）。

这样做的好处就是可以通过较低的代价在List中进行插入和删除操作。与ArrayList一样，LinkedList也是异步的。
如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List：

List list
= Collections.synchronizedList(new LinkedList(...));
综述:
1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。


2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。


3.对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。


这一点要看实际情况的。若只对单条数据插入或删除，ArrayList的速度反而优于LinkedList。但若是批量随机的插入删除数据，LinkedList的速度大大优于ArrayList.
因为ArrayList每插入一条数据，要移动插入点及之后的所有数据。

㈡ ArrayList 和LinkedList各自的特点是什么

1、ArrayList：动态数组。

用MSDN中的说法，就是Array的复杂版本，它提供了动态的增加和减少元素，实现了ICollection和IList接口，灵活的设置数组的大小等好处。

2、LinkedList：双向列表。

列表中的每个节点都包含了对前一个和后一个元素的引用。

List接口的大小可变数组的实现，位于API文档的java.util.ArrayList<E>。实现了所有可选列表操作，并允许包括 null 在内的所有元素。除了实现 List 接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。

size、isEmpty、get、set、iterator 和listIterator 操作都以固定时间运行。add 操作以分摊的固定时间 运行，也就是说，添加 n 个元素需要 O(n) 时间。其他所有操作都以线性时间运行（大体上讲）。

与用于 LinkedList 实现的常数因子相比，此实现的常数因子较低。

每个 ArrayList 实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向 ArrayList 中不断添加元素，其容量也自动增长。并未指定增长策略的细节，因为这不只是添加元素会带来分摊固定时间开销那样简单。

(2)linkedlist常用方法扩展阅读

常用方法：

1、boolean add(E e)：将指定的元素添加到此列表的尾部。

2、void add(int index, E element)：将指定的元素插入此列表中的指定位置。

3、boolean addAll(Collection<? extends E> c)：按照指定 collection 的迭代器所返回的元素顺序，将该 collection 中的所有元素添加到此列表的尾部。

4、boolean addAll(int index, Collection<? extends E> c)：从指定的位置开始，将指定 collection 中的所有元素插入到此列表中。

5、void clear()：移除此列表中的所有元素。

6、Object clone()：返回此 ArrayList 实例的浅表副本。

㈢ 在java中如何用LinkedList利用栈的基本操作实现将任意一个十进制整数转化为 R 进制

import java.util.LinkedList;
public class Stack {
public static void main(String[] args) {
calc(10, 8);
}
private static void calc(int x, int r) {
LinkedList<Integer> stack = new LinkedList<Integer>();// 初始化栈
while (x != 0) {// 只要X不为0重复做下列动作
// 将X％R入栈
int t = x % r;
stack.push(t);
x = x / r;
}
while (!stack.isEmpty()) {// 只要栈不为空重复做下列动作
int stackTop = stack.pollLast();// 栈顶出栈
System.out.println(stackTop);// 输出栈顶元素
}
}
}

㈣ ArrayList、LinkedList、HashMap 这三个分别的用法比如实现网站上的哪些功能的时候该选用哪一个

一般我们用ArrayList就可以了，LinkedList是双向链表，很少用。
ArrayList是List集合，里面放的是单一的任意不为空的对象，HashMap是一个哈希表，是key-value键值对。
着两者的用途是不一样的。使用的场景有很多很多，这里举两个例子：
1）比如你要查询数据库，将当前系统所有的用户都列出来，那么你就可以用ArrayList，将用户对像都放到ArrayList里，然后到页面上遍历出来。
2）如果你想缓存系统里所有用户的权限信息，并且以后随时可以根据用户名来获取相应的角色信息，那么你就可以用map来实现。可以map.put(userName, roleInfo);获取的时候，直接调用下map.get(userName)即可，是不是很方便？ 如果你放到List里，反而不方便了，因为要遍历。

㈤ arraylist 和 linkedlist 的区别

ArrayList

ArrayList是一个动态数组，也是我们最常用的集合。

它允许任何符合规则的元素插入甚至包括null。

每一个ArrayList都有一个初始容量（10），该容量代表了数组的大小。

随着容器中的元素不断增加，容器的大小也会随着增加。

在每次向容器中增加元素的同时都会进行容量检查，当快溢出时，就会进行扩容操作。

所以如果我们明确所插入元素的多少，最好指定一个初始容量值，避免过多的进行扩容操作而浪费时间、效率。

size、isEmpty、get、set、iterator 和 listIterator 操作都以固定时间运行。

add 操作以分摊的固定时间运行，也就是说，添加 n 个元素需要 O(n) 时间（由于要考虑到扩容，所以这不只是添加元素会带来分摊固定时间开销那样简单）。

ArrayList擅长于随机访问。

同时ArrayList是异步的。

LinkedList

同样实现List接口的LinkedList与ArrayList不同，ArrayList是一个动态数组，而LinkedList是一个双向链表。

所以它除了有ArrayList的基本操作方法外还额外提供了get，remove，insert方法在LinkedList的首部或尾部。

由于实现的方式不同，LinkedList不能随机访问，它所有的操作都是要按照双重链表的需要执行。

在列表中索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）。

这样做的好处就是可以通过较低的代价在List中进行插入和删除操作。

与ArrayList一样，LinkedList也是异步的。
如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List：

List list
= Collections.synchronizedList(new LinkedList(...));

综述:

1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。

2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。

3.对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。

这一点要看实际情况的。若只对单条数据插入或删除，ArrayList的速度反而优于LinkedList。但若是批量随机的插入删除数据，LinkedList的速度大大优于ArrayList.
因为ArrayList每插入一条数据，要移动插入点及之后的所有数据。

㈥ 有谁能告诉我LinkedList类的详细的使用介绍，或者介绍些书我看一下谢谢！！！

List 用于遍历一个数组时效率最高；比如在循环显示所有信息时经常用到；
Set中的元素是不能重复的，如果使用add(Object obj)方法添加已经存在的对象，则会覆盖前面的对象；虽然Set同List都实现了Collection接口，但是他们的实现方式却大不一样。List基本上都是以Array为基础。但是Set则是在HashMap的基础上来实现的，这个就是Set和List的根本区别。 Map 就是键值对map（键，值），键是Sting 类型 值是Object （对象类型），所以在知道某条信息的一项时查询其他项就用该方法，效率最高！（以上个人见解！）
详细：数组和其它容器的区别主要有三方面:效率,类型,和保存基本类型的能力.在Java中,数组是一种效率很高的存储和随机访问对象引用序列的方式.数组是一 个简单的线性序列,因此访问速度很快,但也损失了其它一些特性.创建一个数组对象后,大小就固定了,如果空间不够,通常是再创建一个数组,然后把旧数组中 的所有引用移到新数组中.数组可可以保存基本类型,容器不行.
容器类不以具体的类型来处理对象,而是将所有的对象都以Object类型来处理,所以我们可以只创建一个容器,任意的Java对象都可以放进去.容器类可 以使用包装类(Integer,Double等),以便把基本类型放入其中. List Set Map 都可以自动调整容量,数组不能.
Collection表示一组对象，这些对象也称为collection的元素。一些 collection允许有重复的元素，而另一些则不允许。一些collection是有序的，而另一些则是无序的。JDK中不提供此接口的任何直接实 现,它提供更具体的子接口（如 Set 和 List）实现.
Map 将键映射到值的对象。一个映射不能包含重复的键；每个键最多只能映射一个值.Map 接口提供三种collection视图，允许以键集、值集合或键值映射关系集的形式查看某个映射的内容。某些映射实现可明确保证其顺序，如 TreeMap(有序) 类；某些映射实现则不保证顺序，如 HashMap(无序) 类。Map可以像数组那样扩展成多维数组,只要把每个值也做成一个Map就行了.
Collection和Map是Java容器中的两种基本类型. 区别在于容器中每个位置保存的元素个数.Collection每个位置只能保存一个元素,包括List和Set.其中List以进入的顺序保存一组元素; 而Set中的元素不能重复.ArrayList是一种List,HashSet是一种Set,将元素添加入任意Collection都可以使用add() 方法.Map保存的是健值对.使用put()为Map添加元素,它需要一个健和一个值作参数.
ArrayList和LinkedList都实现了List接口,ArrayList底层由数组支持LinkedList由双向链表支持,因此,如果经常在表中插入或删除元素LinkedList比较适合,如果经常查询ArrayList比较适合.
Set的实现有TreeSet,HashSet,LinkedHashSet,HashSet查询速度最快,LinkedHashSet保持元素插入次序,TreeSet基于TreeMap,生成一个总是处于排序状态的Set.
Collection--List--Vector
Collection--List--ArrayList
Collection--List--LinkedList
Collection--Set--HashSet
Collection--Set--HashSet--LinkedHashSet
Collection--Set--SortedSet--TreeSet
Vector : 基于Array的List，其实就是封装了Array所不具备的一些功能方便我们使用，它不可能走入Array的限制。性能也就不可能超越Array。所以，在可能的情况下，我们要多运用Array。另外很重要的一点就是Vector“sychronized”的，这个也是Vector和ArrayList的唯一的区别。
ArrayList：同Vector一样是一个基于Array上的链表，但是不同的是ArrayList不是同步的。所以在性能上要比Vector优越一些，但是当运行到多线程环境中时，可需要自己在管理线程的同步问题。
LinkedList：LinkedList不同于前面两种List，它不是基于Array的，所以不受Array性能的限制。它每一个节点（Node）都包含两方面的内容：1.节点本身的数据（data）；2.下一个节点的信息（nextNode）。所以当对LinkedList做添加，删除动作的时候就不用像基于Array的List一样，必须进行大量的数据移动。只要更改nextNode的相关信息就可以实现了。这就是LinkedList的优势。
List总结：
1. 所有的List中只能容纳单个不同类型的对象组成的表，而不是Key－Value键值对。例如：[ tom,1,c ]；
2. 所有的List中可以有相同的元素，例如Vector中可以有 [ tom,koo,too,koo ]；
3. 所有的List中可以有null元素，例如[ tom,null,1 ]；
4. 基于Array的List（Vector，ArrayList）适合查询，而LinkedList（链表）适合添加，删除操作。
HashSet：虽然Set同List都实现了Collection接口，但是他们的实现方式却大不一样。List基本上都是以Array为基础。但是Set则是在HashMap的基础上来实现的，这个就是Set和List的根本区别。HashSet的存储方式是把HashMap中的Key作为Set的对应存储项。看看HashSet的add（Object obj）方法的实现就可以一目了然了。
public boolean add(Object obj)
{
return map.put(obj, PRESENT) == null;
}
这个也是为什么在Set中不能像在List中一样有重复的项的根本原因，因为HashMap的key是不能有重复的。
LinkedHashSet：HashSet的一个子类，一个链表。
TreeSet：SortedSet的子类，它不同于HashSet的根本就是TreeSet是有序的。它是通过SortedMap来实现的。
Set总结：
1. Set实现的基础是Map（HashMap）；
2. Set中的元素是不能重复的，如果使用add(Object obj)方法添加已经存在的对象，则会覆盖前面的对象；
List接口对Collection进行了简单的扩充，它的具体实现类常用的有ArrayList和LinkedList。你可以将任何东西放到一个List容器中，并在需要时从中取出。ArrayList从其命名中可以看出它是一种类似数组的形式进行存储，因此它的随机访问速度极快，而LinkedList的内部实现是链表，它适合于在链表中间需要频繁进行插入和删除操作。在具体应用时可以根据需要自由选择。前面说的Iterator只能对容器进行向前遍历，而ListIterator则继承了Iterator的思想，并提供了对List进行双向遍历的方法。
Set接口也是Collection的一种扩展，而与List不同的时，在Set中的对象元素不能重复，也就是说你不能把同样的东西两次放入同一个Set容器中。它的常用具体实现有HashSet和TreeSet类。HashSet能快速定位一个元素，但是你放到HashSet中的对象需要实现hashCode()方法，它使用了前面说过的哈希码的算法。而TreeSet则将放入其中的元素按序存放，这就要求你放入其中的对象是可排序的，这就用到了集合框架提供的另外两个实用类Comparable和Comparator。一个类是可排序的，它就应该实现Comparable接口。有时多个类具有相同的排序算法，那就不需要在每分别重复定义相同的排序算法，只要实现Comparator接口即可。集合框架中还有两个很实用的公用类：Collections和Arrays。Collections提供了对一个Collection容器进行诸如排序、复制、查找和填充等一些非常有用的方法，Arrays则是对一个数组进行类似的操作。
Map是一种把键对象和值对象进行关联的容器，而一个值对象又可以是一个Map，依次类推，这样就可形成一个多级映射。对于键对象来说，像Set一样，一个Map容器中的键对象不允许重复，这是为了保持查找结果的一致性;如果有两个键对象一样，那你想得到那个键对象所对应的值对象时就有问题了，可能你得到的并不是你想的那个值对象，结果会造成混乱，所以键的唯一性很重要，也是符合集合的性质的。当然在使用过程中，某个键所对应的值对象可能会发生变化，这时会按照最后一次修改的值对象与键对应。对于值对象则没有唯一性的要求。你可以将任意多个键都映射到一个值对象上，这不会发生任何问题（不过对你的使用却可能会造成不便，你不知道你得到的到底是那一个键所对应的值对象）。Map有两种比较常用的实现：HashMap和TreeMap。HashMap也用到了哈希码的算法，以便快速查找一个键，TreeMap则是对键按序存放，因此它便有一些扩展的方法，比如firstKey(),lastKey()等，你还可以从TreeMap中指定一个范围以取得其子Map。键和值的关联很简单，用pub(Object key,Object value)方法即可将一个键与一个值对象相关联。用get(Object key)可得到与此key对象所对应的值对象。

㈦ Java中的linklist有哪些用法，list.add,list.getFirst(),这些是什么意思

ArrayList Vector LinkedList 区别与用法

ArrayList 和Vector是采用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，都允许直接序号索引元素，但是插入数据要设计到数组元素移动等内存操作，所以索引数据快插入数据慢，Vector由于使用了synchronized方法（线程安全）所以性能上比ArrayList要差，LinkedList使用双向链表实现存储，按序号索引数据需要进行向前或向后遍历，但是插入数据时只需要记录本项的前后项即可，所以插入数度较快！

线性表，链表，哈希表是常用的数据结构，在进行Java开发时，JDK已经为我们提供了一系列相应的类来实现基本的数据结构。这些类均在java.util包中。本文试图通过简单的描述，向读者阐述各个类的作用以及如何正确使用这些类。

Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│ └Stack
└Set
Map
├Hashtable
├HashMap
└WeakHashMap

Collection接口
Collection是最基本的集合接口，一个Collection代表一组Object，即Collection的元素（Elements）。一些Collection允许相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接继承自Collection的类，Java SDK提供的类都是继承自Collection的“子接口”如List和Set。
所有实现Collection接口的类都必须提供两个标准的构造函数：无参数的构造函数用于创建一个空的Collection，有一个Collection参数的构造函数用于创建一个新的Collection，这个新的Collection与传入的Collection有相同的元素。后一个构造函数允许用户复制一个Collection。
如何遍历Collection中的每一个元素？不论Collection的实际类型如何，它都支持一个iterator()的方法，该方法返回一个迭代子，使用该迭代子即可逐一访问Collection中每一个元素。典型的用法如下：
Iterator it = collection.iterator(); // 获得一个迭代子
while(it.hasNext()) {
Object obj = it.next(); // 得到下一个元素
}
由Collection接口派生的两个接口是List和Set。

List接口
List是有序的Collection，使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于Java的数组。
和下面要提到的Set不同，List允许有相同的元素。
除了具有Collection接口必备的iterator()方法外，List还提供一个listIterator()方法，返回一个ListIterator接口，和标准的Iterator接口相比，ListIterator多了一些add()之类的方法，允许添加，删除，设定元素，还能向前或向后遍历。
实现List接口的常用类有LinkedList，ArrayList，Vector和Stack。

LinkedList类
LinkedList实现了List接口，允许null元素。此外LinkedList提供额外的get，remove，insert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。
注意LinkedList没有同步方法。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List：
List list = Collections.synchronizedList(new LinkedList(...));

ArrayList类
ArrayList实现了可变大小的数组。它允许所有元素，包括null。ArrayList没有同步。
size，isEmpty，get，set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。
每个ArrayList实例都有一个容量（Capacity），即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加，但是增长算法并没有定义。当需要插入大量元素时，在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。
和LinkedList一样，ArrayList也是异步的（unsynchronized）。

Vector类
Vector非常类似ArrayList，但是Vector是同步的。由Vector创建的Iterator，虽然和ArrayList创建的Iterator是同一接口，但是，因为Vector是同步的，当一个Iterator被创建而且正在被使用，另一个线程改变了Vector的状态（例如，添加或删除了一些元素），这时调用Iterator的方法时将抛出，因此必须捕获该异常。

Stack 类
Stack继承自Vector，实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

Set接口
Set是一种不包含重复的元素的Collection，即任意的两个元素e1和e2都有e1.equals(e2)=false，Set最多有一个null元素。
很明显，Set的构造函数有一个约束条件，传入的Collection参数不能包含重复的元素。
请注意：必须小心操作可变对象（Mutable Object）。如果一个Set中的可变元素改变了自身状态导致Object.equals(Object)=true将导致一些问题。

Map接口
请注意，Map没有继承Collection接口，Map提供key到value的映射。一个Map中不能包含相同的key，每个key只能映射一个value。Map接口提供3种集合的视图，Map的内容可以被当作一组key集合，一组value集合，或者一组key-value映射。

Hashtable类
Hashtable继承Map接口，实现一个key-value映射的哈希表。任何非空（non-null）的对象都可作为key或者value。
添加数据使用put(key, value)，取出数据使用get(key)，这两个基本操作的时间开销为常数。
Hashtable通过initial capacity和load factor两个参数调整性能。通常缺省的load factor 0.75较好地实现了时间和空间的均衡。增大load factor可以节省空间但相应的查找时间将增大，这会影响像get和put这样的操作。
使用Hashtable的简单示例如下，将1，2，3放到Hashtable中，他们的key分别是”one”，”two”，”three”：
Hashtable numbers = new Hashtable();
numbers.put(“one”, new Integer(1));
numbers.put(“two”, new Integer(2));
numbers.put(“three”, new Integer(3));
要取出一个数，比如2，用相应的key：
Integer n = (Integer)numbers.get(“two”);
System.out.println(“two = ” + n);
由于作为key的对象将通过计算其散列函数来确定与之对应的value的位置，因此任何作为key的对象都必须实现hashCode和equals方法。hashCode和equals方法继承自根类Object，如果你用自定义的类当作key的话，要相当小心，按照散列函数的定义，如果两个对象相同，即obj1.equals(obj2)=true，则它们的hashCode必须相同，但如果两个对象不同，则它们的hashCode不一定不同，如果两个不同对象的hashCode相同，这种现象称为冲突，冲突会导致操作哈希表的时间开销增大，所以尽量定义好的hashCode()方法，能加快哈希表的操作。
如果相同的对象有不同的hashCode，对哈希表的操作会出现意想不到的结果（期待的get方法返回null），要避免这种问题，只需要牢记一条：要同时复写equals方法和hashCode方法，而不要只写其中一个。
Hashtable是同步的。

HashMap类
HashMap和Hashtable类似，不同之处在于HashMap是异步的，并且允许null，即null value和null key。，但是将HashMap视为Collection时（values()方法可返回Collection），其迭代子操作时间开销和HashMap的容量成比例。因此，如果迭代操作的性能相当重要的话，不要将HashMap的初始化容量设得过高，或者load factor过低。

WeakHashMap类
WeakHashMap是一种改进的HashMap，它对key实行“弱引用”，如果一个key不再被外部所引用，那么该key可以被GC回收。

总结
如果涉及到堆栈，队列等操作，应该考虑用List，对于需要快速插入，删除元素，应该使用LinkedList，如果需要快速随机访问元素，应该使用ArrayList。
如果程序在单线程环境中，或者访问仅仅在一个线程中进行，考虑异步的类，其效率较高，如果多个线程可能同时操作一个类，应该使用同步的类。
要特别注意对哈希表的操作，作为key的对象要正确复写equals和hashCode方法。
尽量返回接口而非实际的类型，如返回List而非ArrayList，这样如果以后需要将ArrayList换成LinkedList时，客户端代码不用改变。这就是针对抽象编程。

同步性
Vector是同步的。这个类中的一些方法保证了Vector中的对象是线程安全的。而ArrayList则是异步的，因此ArrayList中的对象并不是线程安全的。因为同步的要求会影响执行的效率，所以如果你不需要线程安全的集合那么使用ArrayList是一个很好的选择，这样可以避免由于同步带来的不必要的性能开销。
数据增长
从内部实现机制来讲ArrayList和Vector都是使用数组(Array)来控制集合中的对象。当你向这两种类型中增加元素的时候，如果元素的数目超出了内部数组目前的长度它们都需要扩展内部数组的长度，Vector缺省情况下自动增长原来一倍的数组长度，ArrayList是原来的50%,所以最后你获得的这个集合所占的空间总是比你实际需要的要大。所以如果你要在集合中保存大量的数据那么使用Vector有一些优势，因为你可以通过设置集合的初始化大小来避免不必要的资源开销。
使用模式
在ArrayList和Vector中，从一个指定的位置（通过索引）查找数据或是在集合的末尾增加、移除一个元素所花费的时间是一样的，这个时间我们用O(1)表示。但是，如果在集合的其他位置增加或移除元素那么花费的时间会呈线形增长：O(n-i)，其中n代表集合中元素的个数，i代表元素增加或移除元素的索引位置。为什么会这样呢？以为在进行上述操作的时候集合中第i和第i个元素之后的所有元素都要执行位移的操作。这一切意味着什么呢？
这意味着，你只是查找特定位置的元素或只在集合的末端增加、移除元素，那么使用Vector或ArrayList都可以。如果是其他操作，你最好选择其他的集合操作类。比如，LinkList集合类在增加或移除集合中任何位置的元素所花费的时间都是一样的?O(1)，但它在索引一个元素的使用缺比较慢－O(i),其中i是索引的位置.使用ArrayList也很容易，因为你可以简单的使用索引来代替创建iterator对象的操作。LinkList也会为每个插入的元素创建对象，所有你要明白它也会带来额外的开销。
最后，在《Practical Java》一书中Peter Haggar建议使用一个简单的数组（Array）来代替Vector或ArrayList。尤其是对于执行效率要求高的程序更应如此。因为使用数组(Array)避免了同步、额外的方法调用和不必要的重新分配空间的操作。

㈧ 链表基本操作

structLink

{

intdata;

Link*Next;

}

///////////////////////////////////////////////////////////////////////////////

classLinkList//带头结点的链表

{

public:

voidSetNull();

voidCreateLink();

voidInsert(intx,intn);//在第x个元素后面插入n

intFindByNum(intx);//找到第x位置的元素，并返回该元素

intFindByValues(intn);//找到值等于n的元素，并返回该元素的位置

intGetLength();

voidprint();

Link*List;

};

//////////////////////////////////////////////////////////////////////////////////

voidLinkList::SetNull()

{

List=NULL;

}

voidLinkList::CreateLink()//输入整数建立链表，-1结束

{

Link*tail,*p;

List=tail=newLink;

List->Next=NULL;

intx;

cin>>x;

while(x>0)

{

p=newLink;

p->data=x;

if(List->Next==NULL)

List->Next=p;

else

tail->Next=p;

tail=p;

cin>>x;

}

tail->Next=NULL;//链表结束标志

}

voidLinkList::Insert(intx,intn)//在第x个元素后面插入n

{

if(List->Next==NULL)

{

cout<<"链表为空！"<<endl;;

}

else

{

Link*p,*q;

p=q=newLink;

q=List->Next;

inti=0;

while(i!=x-1)

{

if(q->Next==NULL)

{

cout<<"参数有误！"<<endl;

break;

}

else

{

q=q->Next;

}

i++;

}

p->data=n;

p->Next=q->Next;

q->Next=p;

}

}

voidLinkList::print()

{

if(List==NULL)

cout<<"链表为空,print"<<endl;

else

{

Link*p=newLink;

p=List->Next;

cout<<"打印链表：";

while(p)

{

cout<<""<<p->data<<",";

p=p->Next;

}

deletep;

cout<<endl;

}

}

intLinkList::FindByNum(intx)//找到第x位置的元素，并返回该元素

{

intn=0;

if(List==NULL)

cout<<"链表为空,print"<<endl;

else

{

Link*p=newLink;

inti=0;

p=List->Next;

while(i!=x-1)

{

if(p==NULL)

{

cout<<"参数有误！"<<endl;

break;

}

p=p->Next;

i++;

}

n=p->data;

}

returnn;

}

intLinkList::FindByValues(intn)

{

inti=1;

if(List==NULL)

cout<<"链表为空,print"<<endl;

else

{

Link*p=newLink;

p=List->Next;

while(p->data!=n)

{

if(p==NULL)

{

cout<<"未找到！"<<endl;

break;

}

p=p->Next;

i++;

}

}

returni;

}

int LinkList::GetLength()//获得链表长度存入链首

{

inti=0;

if(List==NULL)

cout<<"链表为空"<<endl;

else

{

Link*p=newLink;

p=List->Next;

while(p)

{

p=p->Next;

++i;

}

List->data=i;

}

returni;

}

int_tmain(intargc,_TCHAR*argv[])

{

LinkListL;

L.SetNull();

cout<<"创建链表:";

L.CreateLink();

L.print();

cout<<"在第二个元素后面插入111";

L.Insert(2,111);

L.print();

cout<<"输出第二个位置的元素："<<L.FindByNum(2)<<endl;

cout<<"等于3的元素的位置是："<<L.FindByValues(3)<<endl;

L.GetLength();

cout<<"链表长："<<L.List->data;

return0;

}

㈨ ArrayList和LinkedList的区别

ArrayList和LinkedList

共性：ArrayList与LinkedList都是List接口的实现类，因此都实现了List的所有未实现的方法，只是实现的方式有所不同。

区别：List接口的实现方式不同

ArrayList实现了List接口，以数组的方式来实现的，因此对于快速的随机取得对象的需求，使用ArrayList实现执行效率上会比较好。

LinkedList是采用链表的方式来实现List接口的，因此在进行insert和remove动作时效率要比ArrayList高。适合用来实现Stack(堆栈)与Queue(队列)。

HashTable和HashMap

共性：都实现了Map接口。

区别：

(1)继承的父类不同

Hashtable继承自Dictionary类，而HashMap继承自AbstractMap类。

(2)线程安全性不同

Hashtable的方法是Synchronize的，而HashMap中的方法在缺省情况下是非Synchronize的。

(3)提供contains方法

HashMap把Hashtable的contains方法去掉了，改成containsValue和containsKey，因为contains方法容易让人引起误解。

Hashtable则保留了contains，containsValue和containsKey三个方法，其中contains和containsValue功能相同。

(4)key和value是否允许null值

Hashtable中，key和value都不允许出现null值。HashMap中，null可以作为键，这样的键只有一个；可以有一个或多个键所对应的值为null。

(5)两个遍历方式的内部实现上不同

HashMap使用了 Iterator；Hashtable使用Iterator，Enumeration两种方式 。

(6)hash值不同

哈希值的使用不同，HashTable直接使用对象的hashCode。而HashMap重新计算hash值。

(7)内部实现使用的数组初始化和扩容方式不同

HashTable在不指定容量的情况下的默认容量为11，增加的方式是 old*2+1；而HashMap为16，Hashtable不要求底层数组的容量一定要为2的整数次幂，而HashMap则要求一定为2的整数次幂。

㈩ java中Vector，ArraryList和LinkedList的区别

List接口一共有三个实现类，分别是ArrayList、Vector和LinkedList。List用于存放多个元素，能够维护元素的次序，并且允许元素的重复。3个具体实现类的相关区别如下：
1ArrayList是最常用的List实现类，内部是通过数组实现的，它允许对元素进行快速随机访问。数组的缺点是每个元素之间不能有间隔，当数组大小不满足时需要增加存储能力，就要讲已经有数组的数据复制到新的存储空间中。当从ArrayList的中间位置插入或者删除元素时，需要对数组进行复制、移动、代价比较高。因此，它适合随机查找和遍历，不适合插入和删除。
2Vector与ArrayList一样，也是通过数组实现的，不同的是它支持线程的同步，即某一时刻只有一个线程能够写Vector，避免多线程同时写而引起的不一致性，但实现同步需要很高的花费，因此，访问它比访问ArrayList慢。
3LinkedList是用链表结构存储数据的，很适合数据的动态插入和删除，随机访问和遍历速度比较慢。另外，他还提供了List接口中没有定义的方法，专门用于操作表头和表尾元素，可以当作堆栈、队列和双向队列使用。