～、结构
ArrayList位数组结构，LinkedList为双向链表结构。
～、空间
ArrayList有固定容量，超出容量后需要扩容，在数组尾部可能保存有占位的null元素
LinkedList无固定容量，但每个元素都放在节点中，每个节点都有2个额外的定位指针（prev 和 next），第一个和最后一个节点的prev和next都指向null
～、方法及效率对比
—：add
1、add()
ArrayList在数组的最后追加，额外操作仅仅是数组满了的扩容
LinkedList在链表的最后追加同addLast()，每次创建一个新节点（新节点的prev指针指向之前的最后一个节点last），last的next指针指向新节点。每次都需给2个指针赋值。效率不如ArrayList
2、add(int index, E element)
ArrayList在数组的指定index位置添加元素element，每次都需调用System.arraycopy() 拷贝数组
LinkedList只是创建一个prev指针指向index前一个元素，next指针指向index元素的节点，并将index前节点的next指针和index节点的prev指针指向新节点。与前面的在最后添加差不多，此时效率要远远高于ArrayList
3、在结构最前面添加，ArrayList只能用 add(0, e)。而LinkedList除add(0, e)外还可以用addFirst(e)。同样LinkedList效率高于ArrayList
—：get
1、get(int index）
ArrayList直接取数组下标得到元素值
LinkedList需要遍历链表取到index位置的节点，再得到节点的item值。效率受链表长度和index在链表位置的影响
2、get遍历
for遍历
ArrayList数组长度及循环次数，一个元素只循环一次。LinkedList每取一个数都重新遍历链表，一个元素最多遍历 链表长/2次。
foreach遍历
先将集合转Iterator，循环次数都为元素的个数。
ArrayList2种方式都可，LinkedList要求使用foreach
—：remove
1、remove(int index)
ArrayList删除指定下标的元素，需调用System.arraycopy()函数，再将最后一个元素赋null
LinkedList删除指定下标的节点，改变index节点的prev节点的next为index的next，index的next节点的prev为index的prev，再清理index节点的item为null。效率也比ArrayList好。
2、remove(Object o)
删除数组或链表中第一次出现的与o相等的元素，先查找再删除，删除步骤同第一点。
3、remeve()，removeFirst()，removeLast()
3个方法都只是LinkedList所有。removeFirst()和remove()方法删除第一个节点。removeLast()删除最后一个节点。
—：set
1、set(int index, E element)
替换index位置的元素为element。
ArrayList直接取数组下标赋值。
LinkedList首先遍历链表取到index位置的节点，再将节点的item赋值。如果链表比较大切index在链表中间位置会很浪费时间。
网友评论