一、单向链表和双向链表的区别

单链表是当前节点只包含下一个节点的信息。插入和删除节点都需要遍历链表才能确认要插入或者删除的节点的位置。不能随机查找，必须从第一个开始遍历，相对数组而言查找效率低。因为插入节点不需要对插入节点后面的节点进行移动（数组需要移动），相比数组和双向链表，单链表对数据的插入操作执行的比较快。（因为单链表的单向特性，算法题中一般设置为两个指针，一快一慢同时向前移动）

双向链表是在单向链表的每一个节点中，再设置一个指向其前驱节点的指针，所以双向链表的每一个节点有两个指针域，一个指向前一个节点，一个指向后一个节点。双向链表对节点的增删操作更复杂。需要多处理一个指针。但是可以找到节点的前驱和后继，可进可退。

引申：链表跟数组的区别？ 数组静态分配内存，链表动态分配内存；数组在内存中连续，链表不连续；数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n)；数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)。

二、LinkedList，ArrayList，vector的区别，以及它们的扩容机制。

Vector是线程安全的，ArrayList和LinkedList不是线程安全的。

ArrayList和Vector都是基于存储元素的数组来实现的。它们在内存中的存储空间是连续的，因此他们支持用序号(下标)来访问元素，同时索引数据的速度比较快。但是对数据的插入操作执行的比较慢。ArrayList和Vector区别就在于synchronize，ArrayList方法是不同步的，Vector绝大多数方法是同步的。

LinkedList是基于双向链表实现的。因为没有索引下标，在随机访问需要先遍历，效率比较低（但是每次循环遍历的时候，都会先判断一下，这个索引位于链表的前部分还是后部分，每次都会遍历链表的一半，而不是全部遍历），在添加和删除元素时不需要对数据进行移动，具有比ArrayList更好的性能。如果需要遍历List集合元素，对于ArrayList、Vector集合，应该使用随机访问方法(get)来遍历集合元素；对于LinkedList集合，则应该采用迭代器(Iterator)来遍历集合元素；

如果需要经常执行插入、删除操作来改变List集合的大小，则应该使用LinkedList集合，而不是ArrayList。如果只在集合的尾端增删数据时，使用ArrayList或者Vector效率较高。在多线程中使用容器时，用Vector比较安全。

扩容机制： Vector和ArrayList在更多元素添加进来时会请求更大的空间。Vector每次请求其大小的2倍空间，而ArrayList默认扩充为原来的1.5倍。ArrayList的扩容会产生一个新的数组，将原来数组的值复制到新的数组中。会消耗一定的资源。所以我们初始化ArrayList时，最好可以估算一个初始的大小。 而LinkedList还继承了Queue类的派生类Dueue（一个双向队列），实现了Queue接口,该接口比List提供了更多的方法,包括offer()、peek()、poll()等。 为什么ArrayList自动容量扩充选择扩充1.5倍？ ArrayList的扩容消费相对HashMap更小，所以允许ArrayList更频繁的扩容。