我们说linkedlist不是一个基于索引的集合，为什么呢?

Question

我无法弄清楚linkedlist和arraylist之间的区别。下面的实现更让我困惑。到目前为止，我一直认为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));
    }
}

Answer 1

区别在于底层实现。数组是一个固定大小的内存块，分为多个块，每个块包含一个元素。使用索引号跳转到任何单个元素都很容易，并且修改一个元素不会影响数组的其余部分。向数组中添加元素的代价很高，因为实际上需要将整个数组复制到更大的空间中，以便为新元素腾出空间。(通过预先分配比实际需要更多的空间，可以使添加到数组末尾的速度更快，但最终您将需要再次复制整个数组。)

另一方面，链表由独立的内存块组成，每个内存块包含要存储的元素和指向列表中下一项的指针。添加到这样一个列表(给定一个指向您想要添加的位置的指针)是快速的，因为您只需要获取一个新的内存块并修改少量节点的指针，与整个列表的大小无关。代价是，为了获得指向中间任意节点的指针，需要从头遍历列表的长度。

这有点简化，但主要思想是每个底层数据类型适合"列表"抽象概念的不同应用，在选择更合适的操作之前，您需要考虑要执行的操作类型(查找，添加，删除等)。