列表输出循环左移_Java Note-数据结构（3）列表
列表List
- 有序的Collection
- 允许重复元素
- {1,2,4,{5,2},1,3}
List主要实现：
ArrayList(非同步的)
- 以数组实现的列表，不支持同步
- 利用索引位置可以快速定位访问
- 不适合指定位置的插入、删除操作（插入或删除元素，会造成大规模元素左移或右移）
- 适合变动不大，主要用于查询的数据
- 和Java数组相比，其容量是可动态调整的
- ArrayList在元素填满容器时会自动扩充容器大小的50%
import java.util.ArrayList;
import java.util.Iterator;
//Vector 几乎和ArrayListһ一样，除了Vector本身是同步的
public class ArrayListTest {
public static void main(String[] a) {
ArrayList<Integer> al = new ArrayList<Integer>();//<>泛型
al.add(3); //ArrayList只能装对象，当add(3)时，会自动将普通int变量3自动装箱为Integer（3）的对象，然后放入容器
al.add(2);
al.add(1);
al.add(4);
al.add(5);
al.add(6);
al.add(new Integer(6));
System.out.print("The third element is ");
System.out.println(al.get(3));//返回第四个元素
al.remove(3); //删除第四个元素，后面元素往前挪动
al.add(3, 9); //将9插入到第3个元素，后面元素往后挪动
System.out.println("======遍历方法=============");
ArrayList<Integer> as = new ArrayList<Integer>(100000);
for (int i=0; i<100000; i++)
{
as.add(i);
}
traverseByIterator(as);
traverseByIndex(as);
traverseByFor(as);
}
public static void traverseByIterator(ArrayList<Integer> al)
{
long startTime = System.nanoTime();
System.out.println("============迭代器遍历==============");
Iterator<Integer> iter1 = al.iterator();
while(iter1.hasNext()){
iter1.next();
}
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println(duration + "纳秒");
}
public static void traverseByIndex(ArrayList<Integer> al)
{
long startTime = System.nanoTime();
System.out.println("============随机索引值遍历==============");
for(int i=0;i<al.size();i++)
{
al.get(i);
}
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println(duration + "纳秒");
}
public static void traverseByFor(ArrayList<Integer> al)
{
long startTime = System.nanoTime();
System.out.println("============for循环遍历==============");
for(Integer item : al)
{
;
}
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println(duration + "纳秒");
}
}
结果：
The third element is 4
======遍历方法=============
============迭代器遍历==============
12214400纳秒
============随机索引值遍历==============
8011800纳秒
============for循环遍历==============
9805000纳秒LinkedList(非同步)
- 以双向链表实现的列表，不支持同步（链表可快速插入和删除）
- 可被当作堆栈、队列、双端队列进行操作
- 顺序访问高效，随机访问较差，中间插入和删除高效
- 适用于经常变化的数据
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
public class LinkedListTest {
public static void main(String[] args) {
LinkedList<Integer> ll = new LinkedList<Integer>(); //使用泛型
ll.add(3);
ll.add(2);
ll.add(5);
ll.add(6);
ll.add(6); //加入了五个元素
System.out.println(ll.size());
ll.addFirst(9); //在头部增加9
ll.add(3, 10); //将10插入到第四个元素，四以及后续的元素往后挪动
ll.remove(3); //将第四个元素删除
LinkedList<Integer> list = new LinkedList<Integer>();
for (int i=0; i<100000; i++)
{
list.add(i);
}
traverseByIterator(list);
traverseByIndex(list);
traverseByFor(list);
}
public static void traverseByIterator(LinkedList<Integer> list)
{
long startTime = System.nanoTime();
System.out.println("============迭代器遍历==============");
Iterator<Integer> iter1 = list.iterator();
while(iter1.hasNext()){
iter1.next();
}
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println(duration + "纳秒");
}
public static void traverseByIndex(LinkedList<Integer> list)
{
long startTime = System.nanoTime();
System.out.println("============位置索引遍历==============");
for(int i=0;i<list.size();i++)
{
list.get(i);
}
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println(duration + "纳秒");
}
public static void traverseByFor(LinkedList<Integer> list)
{
long startTime = System.nanoTime();
System.out.println("============for循环遍历==============");
for(Integer item : list)
{
;
}
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println(duration + "纳秒");
}
}结果：
5
============迭代器遍历==============
8543401纳秒
============位置索引遍历==============
5024269101纳秒
============for循环遍历==============
7258300纳秒for循环和迭代器循环相差不大，位置索引速度慢约1000倍。
ArrayList和LinkedList比较
分别测试两种容器的头部数据添加，数据索引获取，头部数据删除的效率：
import java.util.ArrayList;
import java.util.LinkedList;
public class ListCompareTest {
public static void main(String[] args) {
int times = 10 * 1000;
// times = 100 * 1000;
// times = 1000 * 1000;
ArrayList<Integer> arrayList = new ArrayList<Integer>();
LinkedList<Integer> linkedList = new LinkedList<Integer>();
System.out.println("Test times = " + times);
System.out.println("-------------------------");
// ArrayList add
long startTime = System.nanoTime();
for (int i = 0; i < times; i++) {
arrayList.add(0,i);//每次都添加在头部，发生大规模元素后移
}
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println(duration + " <--ArrayList add");
// LinkedList add
startTime = System.nanoTime();
for (int i = 0; i < times; i++) {
linkedList.add(0,i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println(duration + " <--LinkedList add");
System.out.println("-------------------------");
// ArrayList get
startTime = System.nanoTime();
for (int i = 0; i < times; i++) {
arrayList.get(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println(duration + " <--ArrayList get");
// LinkedList get
startTime = System.nanoTime();
for (int i = 0; i < times; i++) {
linkedList.get(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println(duration + " <--LinkedList get");
System.out.println("-------------------------");
// ArrayList remove
startTime = System.nanoTime();
for (int i = 0; i < times; i++) {
arrayList.remove(0);//大面积数据移动
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println(duration + " <--ArrayList remove");
// LinkedList remove
startTime = System.nanoTime();
for (int i = 0; i < times; i++) {
linkedList.remove(0);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println(duration + " <--LinkedList remove");
}
}输出：
Test times = 10000
-------------------------
8077800 <--ArrayList add
1699300 <--LinkedList add
-------------------------
841000 <--ArrayList get
75722300 <--LinkedList get
-------------------------
7700200 <--ArrayList remove
1109100 <--LinkedList removeVector(同步)
- 和ArrayList类似，可变数组实现的列表
- Vector同步，适合在多线程下使用
- 性能较差
- 在非同步情况下，优先使用ArrayList
import java.util.ArrayList;
import java.util.Enumeration;
import java.util.Iterator;
import java.util.Vector;
public class VectorTest {
public static void main(String[] args) {
Vector<Integer> v = new Vector<Integer>();
v.add(1);//与ArrayList接近
v.add(2);
v.add(3);
v.remove(2);
v.add(1, 5);
System.out.println(v.size());
System.out.println("======遍历方法=============");
Vector<Integer> v2 = new Vector<Integer>(100000);
for (int i = 0; i < 100000; i++) {
v2.add(i);
}
traverseByIterator(v2);
traverseByIndex(v2);
traverseByFor(v2);
traverseByEnumeration(v2);
}
public static void traverseByIterator(Vector<Integer> v) {
long startTime = System.nanoTime();
System.out.println("============迭代器遍历==============");
Iterator<Integer> iter1 = v.iterator();
while (iter1.hasNext()) {
iter1.next();
}
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println(duration + "纳秒");
}
public static void traverseByIndex(Vector<Integer> v) {
long startTime = System.nanoTime();
System.out.println("============索引位置遍历==============");
for (int i = 0; i < v.size(); i++) {
v.get(i);
}
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println(duration + "纳秒");
}
public static void traverseByFor(Vector<Integer> v) {
long startTime = System.nanoTime();
System.out.println("============for循环遍历==============");
for (Integer item : v) {
;
}
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println(duration + "纳秒");
}
public static void traverseByEnumeration(Vector<Integer> v) {
long startTime = System.nanoTime();
System.out.println("============Enumeration遍历==============");
for (Enumeration<Integer> enu = v.elements(); enu.hasMoreElements();) {
enu.nextElement();
}
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println(duration + "纳秒");
}
}结果：
3
======遍历方法=============
============迭代器遍历==============
115492000纳秒
============索引位置遍历==============
14566000纳秒
============for循环遍历==============
10974600纳秒
============Enumeration遍历==============
23954500纳秒