知乎专栏 |
链表(Linked list)是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的地址
初始化
LinkedList<Integer> sequence = new LinkedList<>() {{ push(10); push(50); push(100); push(1000); }};
package cn.netkiller.test; import java.util.ArrayList; import java.util.Iterator; import java.util.LinkedList; import java.util.List; public class Test { public static void main(String[] args) { Test test = new Test(); ArrayList<Integer> arrayList = new ArrayList<Integer>(); LinkedList<Integer> linkedList = new LinkedList<Integer>(); int size = 10000 * 1000; int index = 5000 * 1000; System.out.println("arrayList add " + size); addData(arrayList, size); System.out.println("linkedList add " + +size); addData(linkedList, size); System.out.println(); System.out.println("arrayList get " + index + " th"); getIndex(arrayList, index); System.out.println("linkedList get " + index + " th"); getIndex(linkedList, index); System.out.println(); System.out.println("arrayList set " + index + " th"); setIndex(arrayList, index); System.out.println("linkedList set " + index + " th"); setIndex(linkedList, index); System.out.println(); System.out.println("arrayList add " + index + " th"); addIndex(arrayList, index); System.out.println("linkedList add " + index + " th"); addIndex(linkedList, index); System.out.println(); System.out.println("arrayList remove " + index + " th"); removeIndex(arrayList, index); System.out.println("linkedList remove " + index + " th"); removeIndex(linkedList, index); System.out.println(); System.out.println("arrayList remove Object " + index); removeObject(arrayList, index); System.out.println("linkedList remove Object " + index); removeObject(linkedList, index); System.out.println(); System.out.println("arrayList add"); add(arrayList); System.out.println("linkedList add"); add(linkedList); System.out.println(); System.out.println("arrayList iterator"); iterator(arrayList); System.out.println("linkedList iterator"); iterator(linkedList); System.out.println(); System.out.println("arrayList foreach"); foreach(arrayList); System.out.println("linkedList foreach"); foreach(linkedList); System.out.println(); System.out.println("arrayList forSize"); forSize(arrayList); System.out.println("linkedList forSize"); // forSize(linkedList); System.out.println("wait: ..."); System.out.println(); } private static void addData(List<Integer> list, int size) { long begin = System.currentTimeMillis(); for (int i = 0; i < size; i++) { list.add(i); } long end = System.currentTimeMillis(); System.out.println("cost time: " + (end - begin)); } private static void getIndex(List<Integer> list, int index) { long begin = System.currentTimeMillis(); list.get(index); long end = System.currentTimeMillis(); System.out.println("cost time: " + (end - begin)); } private static void setIndex(List<Integer> list, int index) { long begin = System.currentTimeMillis(); list.set(index, 1024); long end = System.currentTimeMillis(); System.out.println("cost time: " + (end - begin)); } private static void addIndex(List<Integer> list, int index) { long begin = System.currentTimeMillis(); list.add(index, 1024); long end = System.currentTimeMillis(); System.out.println("cost time: " + (end - begin)); } private static void removeIndex(List<Integer> list, int index) { long begin = System.currentTimeMillis(); list.remove(index); long end = System.currentTimeMillis(); System.out.println("cost time: " + (end - begin)); } private static void removeObject(List<Integer> list, Object obj) { long begin = System.currentTimeMillis(); list.remove(obj); long end = System.currentTimeMillis(); System.out.println("cost time: " + (end - begin)); } private static void add(List<Integer> list) { long begin = System.currentTimeMillis(); list.add(1024); long end = System.currentTimeMillis(); System.out.println("cost time: " + (end - begin)); } private static void iterator(List<Integer> list) { long begin = System.currentTimeMillis(); Iterator<Integer> ite = list.iterator(); while (ite.hasNext()) { ite.next(); } long end = System.currentTimeMillis(); System.out.println("cost time: " + (end - begin)); } private static void foreach(List<Integer> list) { long begin = System.currentTimeMillis(); for (Integer i : list) { //do nothing } long end = System.currentTimeMillis(); System.out.println("cost time: " + (end - begin)); } private static void forSize(List<Integer> list) { long begin = System.currentTimeMillis(); int size = list.size(); for (int i = 0; i < size; i++) { list.get(i); } long end = System.currentTimeMillis(); System.out.println("cost time: " + (end - begin)); } }