首页 > 代码库 > The difference (advantages & disavanteges ) between Arraylist and Linkedlist

The difference (advantages & disavanteges ) between Arraylist and Linkedlist

先放总结: ArrayList 在时间复杂度上表现出 查询快  更改操作消耗大的特点,而LinkedList则表现出 查询相对耗费大,而更改快的特点 所以两种list可以择优使用!

首先 放上自己打的一段 模仿 残缺的 LinkedList 代码:

  1 public class linkListDemo {
  2     /**
  3      * first refer to the first ele
  4      * last refer to the last ele , Object
  5      * */
  6     private Node first = null;
  7     private Node last  = null;
  8     
  9     
 10     /**
 11      * the size of the list
 12      * */
 13     private int size = 0;
 14     
 15     
 16     
 17     /**
 18      * add a new node to the last position
 19      * */
 20     public void addLast(Object ele){
 21         
 22         //create a new node which pose on the next position of the previous one
 23         Node node = new Node(ele);
 24         
 25         //size would not be lower than zero ,so we don‘t need out-of-bound check
 26         if(size == 0){
 27             /**
 28              * no doubt that the first and last ele of the very first element is itself 
 29              * */
 30             
 31             /**
 32              * set the first and last node of the linkedlist
 33              * */
 34             this.last  = node; //belongs to a linkedlist
 35             this.first = node; //belongs to a linkedlist
 36         }
 37         else{
 38             this.last.next = node;
 39             node.prev = this.last;
 40             this.last = node;
 41         
 42         
 43         }
 44         size++;
 45     }
 46     
 47     /**
 48      * remove operation a node in the linkedlist
 49      * */
 50     public void remove(Node nd){
 51         
 52     }
 53     /**
 54      * add a new node to the first position
 55      * */
 56     public void addFirst(){
 57         
 58     }
 59     
 60     /**
 61      * class node , which contain its previous node and next node , as well as its own element
 62      * */
 63      class Node {
 64          /**
 65           * ele , pre ,next
 66           * */
 67          Node(Object ele){
 68              this.ele = ele;
 69          }
 70         //element 
 71         private Object ele;
 72         
 73         //previous 
 74         Node prev;
 75         
 76         //next
 77         Node next;
 78         
 79     
 80         
 81     /**
 82      * overwrite toString method 
 83      * */
 84     }
 85     public String toString(){
 86         
 87         //the first node
 88         Node currentNode = this.first;
 89         if(size == 0){
 90             String str = "[]";
 91             return null;
 92         }
 93         else{
 94             StringBuffer sb = new StringBuffer();
 95             sb.append("[");
 96             for(int i = 0 ; i < size; i++){
 97                 
 98                 //add element
 99                 sb.append(currentNode.ele);
100                 currentNode = currentNode.next;
101                 
102                 //add ","
103                 if(i != (size - 1)){
104                     sb.append(",");
105                 }
106             }
107             sb.append("]");
108             
109             //@return
110             return sb.toString();
111         }
112     
113     }
114 }

 

还有  ArrayLIst 的:

 1 /**
 2  * @command 学习仿作一个Arrayist
 3  * */
 4 public class MyArrayList {
 5     /**主体数组*/
 6     Object[] elementData;
 7     /**初始化后的数组元素个数*/
 8     private int size = 0;
 9     /**默认长度*/
10     private static final Integer DEFAULT_CAPACITY = 10;
11     /**empty list that has initialized*/
12     private static final Object[] EMPTY_ELEMENTDATA = http://www.mamicode.com/null;
13     /** Constructor 
14      * @throws Exception */
15     public MyArrayList() throws Exception{
16         this(DEFAULT_CAPACITY);
17     }
18     /**
19      * Constructs an empty list with the specific initial capacity
20      * @param initialCapacity the initial capacity of the list
21      * @exception IllegalArgumentException if the specific capacity 
22      * is negative
23      * 
24      * */
25      public MyArrayList(Integer initialCapacity)throws IllegalArgumentException {
26         if(initialCapacity > 0){
27         this.elementData = http://www.mamicode.com/new Object[initialCapacity];
28         }else if (initialCapacity ==0){
29             this.elementData =http://www.mamicode.com/ EMPTY_ELEMENTDATA;
30         }else {
31             //真的是 实践学习得最多 :throw exception 时要用new  因为你这个是一个新的异常 如果不用new 默认当是方法
32             throw new IllegalArgumentException("Illegal capacity : " + initialCapacity);
33         }
34     }
35     public static void add(Object obj){
36         
37     }
38     
39     /**
40      * return true if the arraylist is empty
41      * else  return false
42      * */
43     public boolean isEmpty(){
44         return size == 0;
45     }
46     
47     /**
48      * return the element of the specific index
49      * */
50     public Object get(Integer index){
51         rangeCheck(index);//checked
52         return elementData[index];
53     }
54     
55     /**
56      * to check whether if the index is out-of-bound
57      * */
58     private void rangeCheck(Integer index) {
59         // TODO Auto-generated method stub
60         if(index > size){
61             throw new IndexOutOfBoundsException("index");// actually Java api used outofboundmsg(which is a defined string
62         }
63     }
64 }

 

The difference (advantages & disavanteges ) between Arraylist and Linkedlist