我們說鏈表不是一個基於索引的集合，爲什麼？

我無法弄清楚鏈表和數組列表之間的區別。下面的實現讓我更加困惑。 Uptil現在我假定LinkedList不是基於索引的數據結構。我們說鏈表不是一個基於索引的集合，爲什麼？

package com.rnd.core.collections; 

import java.util.ArrayList; 
import java.util.LinkedList; 
import java.util.List; 

public class LinkedListTest { 
    public static void main(String[] args) { 
     List<String> myLinkedList = new LinkedList<String>(); 
     myLinkedList.add("Spring"); 
     myLinkedList.add("Struts"); 
     myLinkedList.add("EJB"); 
     myLinkedList.add("Hibernate"); 
     myLinkedList.add(1, "Collections"); 
     myLinkedList.add(1, "JMS"); 

     System.out.println(""+myLinkedList.subList(1, 3)); 
     System.out.println("Search result for \"Hibernate\":" + myLinkedList.contains("Hibernate")); 
     System.out.println("Search result for \"Hibernate\":" + myLinkedList.contains("ibatis")); 
     for(String item: myLinkedList){ 
      System.out.println(item.toString());  
     } 

     System.out.println("<><>"+myLinkedList.get(1)); 

     List<String> myArrayList = new ArrayList<String>(); 

     myArrayList.add("Spring"); 
     myArrayList.add("Struts"); 
     myArrayList.add("EJB"); 
     myArrayList.add("Hibernate"); 
     myArrayList.add(1, "Collections"); 
     myArrayList.add(1, "JMS"); 

     myArrayList.subList(1, 2); 
     System.out.println("*****************"+myArrayList.subList(1, 3)); 

    } 

}

任何幫助將不勝感激在這方面。

來源

2014-07-19 Ankit

不同之處在於底層實現。一個數組是固定大小的內存塊，分成塊，每個塊都有一個元素。使用索引號跳轉到任何單個元素很容易，修改一個元素不會影響數組的其餘部分。向數組中添加一個元素是很昂貴的，因爲你基本上需要將整個數組複製到一個更大的空間中，爲新元素騰出空間。（通過預先分配比實際需要的空間更多的空間，可以使數組末尾更快，但最終需要再次複製整個數組。）

另一方面，鏈接列表由獨立的內存塊，每個內存塊都包含要存儲的元素以及指向列表中下一項的指針。添加到這樣一個列表（給定一個指向你要添加的位置的指針）是快速的，因爲你只需要獲取一個新的內存塊並修改少量節點的指針，而與列表的大小無關作爲一個整體。成本是，爲了得到一個指向中間任意節點的指針，你需要從頭開始遍歷列表的長度。

這是一種簡化，但主要思想是每個底層數據類型都適合不同應用程序的「列表」的抽象概念，並且您需要考慮操作類型（查找，添加，刪除等），你想在選擇哪一個更合適之前執行。

來源

2014-07-19 12:54:32 chepner

我們說鏈表不是一個基於索引的集合，爲什麼？

回答

相關問題