ArrryList和LinkedList的区别

ArrayList和LinkedList都是List接口的实现类，在面试中经常被问到，所以写篇日志记录下。

所在位置

先来看看ArrayList和linkedList在JDK中所在的位置

从图中可以看出,ArrayList与LinkedList都是List接口的实现类,因此都实现了List的所有未实现的方法,只是实现的方式有所不同,(编程思想: 从中可以看出面向接口的好处, 对于不同的需求就有不同的实现!),而List接口继承了Collection接口,Collection接口又继承了Iterable接口,因此可以看出List同时拥有了Collection与Iterable接口的特性.

认识和理解ArrayList

ArrayList实现了List接口,它是以数组的方式来实现的,数组的特性是可以使用索引的方式来快速定位对象的位置,因此对于快速的随机取得对象的需求,使用ArrayList实现执行效率上会比较好.

public static void main(String[] args){
      List<String> list =new ArrayList<>();
      list.add("张三");
      list.add("李四");
      list.add("王五");
      list.add("赵六");
      System.out.println("使用迭代器进行遍历");
      Iterator it=list.iterator();
      while (it.hasNext()){
          System.out.println(it.next());
      }
      System.out.println("使用增强for循环");
      for (String name: list){
          System.out.println(name);

      }
  }

这里列举了两张遍历list集合的方法，迭代器和增强for循环

认识和理解linkedList

LinkedList是采用链表的方式来实现List接口的,它本身有自己特定的方法，如: addFirst(),addLast(),getFirst(),removeFirst()等. 由于是采用链表实现的,因此在进行insert和remove动作时在效率上要比ArrayList要好得多!适合用来实现Stack(堆栈)与Queue(队列),前者先进后出，后者是先进先出.

1.堆栈

public class StringStack {

    private LinkedList<String> linkedList=new LinkedList<>();

    /**
     * 将元素插入到linkedList的第一个元素
     * @param name
     */
    public void push(String name){
        linkedList.addFirst(name);
    }

    /**
     * 获取linkedList的第一个元素
     * @return
     */
    public String getTop(){
        return linkedList.getFirst();
    }

    /**
     * 删除linkedList的第一个元素
     */
    public String removeTop(){
        return linkedList.removeFirst();
    }

    public int size(){
        return linkedList.size();
    }

    public boolean isEmpty(){
        return linkedList.isEmpty();
    }

    public static void main(String[] args){
        StringStack stack=new StringStack();
        stack.push("张三");
        stack.push("李四");
        stack.push("王五");
        stack.push("赵六");
        stack.push("薛七");
        stack.push("钱八");
        stack.push("孙九");
        stack.push("周十");
        System.out.println("第一个元素是"+stack.getTop());
        System.out.println("链表的长度："+stack.size());
        System.out.println("全部元素:\t");
        while (!stack.isEmpty()){
            System.out.println(stack.removeTop());
        }
    }
}

2.实现队列类似

ArrayList和LinkedList相同点：

1.ArrayList和LinkedList类都位于java.util包中，均为可收缩数组，即可以动态的改变数组的长度。
2.ArrayList和LinkedList都是不同步的。
3.都位于java.util包中。
4.都是List接口的实现类，List中的元素都是有序、不可重复的。

ArrayList和LinkedList不同点：

1.ArrayList是由Array所支持的基于一个索引的数据结构，所以它提供对元素的随机访问，
复杂度为O(1)，但LinkedList存储一系列的节点数据，每个节点都与前一个和下一个节点相连接。
所以，尽管有使用索引获取元素的方法，内部实现是从起始点开始遍历，遍历到索引的节点然后返回元素，
时间复杂度为O(n)，比ArrayList要慢。
2.ArrayList和Vector底层是使用数组实现的；LinkedList底层使用双向循环链表数据结构实现；
3.相比较于ArrayList,LinkedList对于添加、删除一个元素会更快，因为在链表中插入元素时，不会涉及到更改数组的长度，或者更新索引。
4.linkedList比ArrayList消耗更多的内存，因为每个节点还存储着其前后节点的引用。

ArrayList和vector的区别

1.Vector是线程安全的，因为Vector基本上所有方法都加了排它锁(synchronized),而ArrayList是线程不安全的。
2.因为线程安全就必须设计到效率，所以ArrayList效率高于Vector.
3.自增长：ArrayList如果发现容量不足时，会自动进行容量扩容，新的大小为：

1	int newCapacity = (oldCapacity * 3)/2 + 1;

也就是原有容量的1.5倍+1。然后通过底层的复制方法将原有数据复制过来
Vector则是原始容量的2倍进行扩容。