我正在研究java中的数据结构和算法，我无法理解本书的这一部分。
这是书中写的：
另一方面，如果我们通过在正面添加项目构建列表，
public static void makeList2( List<Integer> lst, int N )
{
lst.clear( );
for( int i = 0; i < N; i++ )
lst.add( 0, i );
}
linkedlist的运行时间为O（n），但是o（n 2 ）对于arraylist， 因为在阵列列表中，前面添加是O（n）操作。
我的问题是我不明白为什么运行时间有所不同？为什么在阵列列表中，在前面添加是O（n）操作？
答案在于名称。linkedlist vs. arraylist。由于linkedlist是一个动态结构，每次要添加到尾巴时都保持尾巴（也可以包含头指针）指针，这是设置一些新值并将尾指针设置为新添加值的简单问题。
带有阵列列表，正如亚伦·戴维斯（Aaron Davis）所述，您必须移动所有值。要记住的另一件事是，数组是一个有限的尺寸结构，因此每次达到最大值时，都需要调整它需要时间。由于这些原因，LinkedLists随着添加而更好。但是，由于阵列列表在其引擎盖下使用阵列，因此在查找方面会更快，因为它是记忆的连续块，而不是不同指针的集合。因此，在数组列表中查找o（1），而linkedlist是o（n）
这是一个非常有用的链接，描述了两者之间的区别：http：//beginnersbook.com/2013/12/difference-between-araylist-araylist-and-link-linkedlist-in--in-java/
arrayList的检索操作比linkedlist快，而insert，删除，linkedlist的更新操作速度比arraylist更快。有具体的原因。ArrayList是某种列表，当一个更改其中一个，创建新的arraylist并复制所有元素时，将对象彼此存储在彼此中，并且很容易轻松地穿越arraylist。现在，当我们谈论linkedlist时，它们不会以连续的方式存储在堆中，因为它们保存了下一个对象和以前的对象的地址，因此当我们更改时，它只会更改下一个和上一个对象的参考地址。因此，与ArrayList相比，检索很耗时，因为它可以通过地址跟踪以找到n'th索引元素。
1） arrayList get（int index）操作以恒定时间O（1）运行，而linkedlist get（int index）操作运行时间为o（n）。
ArrayList背后的原因比LinkedList快的原因是ArrayList使用基于索引的系统对其元素使用基于索引的系统，因为它在内部使用数组数据结构，另一方面，LinkedList不为其元素提供基于索引的访问，因为它是从迭代中迭代的，在指定元素索引中检索节点的开始或结束（以较近为准）。
2） insert（）或add（object）操作：linkedlist中的插入通常很快，与arraylist相比。
在linkedlist添加或插入中是o（1）操作。在ArrayList中，如果数组已满，即最坏的情况，则在调整数组和将元素复制到新数组中会有额外的费用，这使得在ArrayList O（n）中添加操作的运行时，否则是O（1）。p> 3）删除（int）操作：删除linkedlist中的操作通常与arraylist相同，即o（n）。在LinkedList中，有两个超载删除方法。一个是删除（），没有任何参数可以删除列表的头部并在恒定时间o（1）中运行。LinkedList中的另一个超载删除方法是删除（int）或删除（对象），该方法将对象或int作为参数删除。此方法遍历链接列表，直到它找到对象并将其与原始列表取消链接。因此，此方法运行时间为o（n）。
在ArrayList remove（int）方法中，涉及将元素从旧数组复制到新更新的数组，因此其运行时间为O（n）。
使用链接列表，您只需在列表的前面插入新节点的头指针即可。使用数组列表，您每次插入列表的前部时都必须在数组中移动每个元素。