java容器——List接口

1、概念

List接口中的数据是有序可重复的。继承了Collection接口。
有三个实现类ArrayList、LinkedList、Vector。

ArrayList：
底层实现是数组。查询快，插入、删除慢。线程不安全，效率高。
LinkedList：
底层实现是链表。查询慢，插入、删除快。线程不安全，效率高。
Vector：
底层实现也是数组。线程安全，效率低。一般多个线程共享时使用，但是一般是局部变量，所以一般不使用。
Stack：
继承了Vector类。

2、ArrayList底层实现模拟（底层数组）

查询快：直接返回数组下标的存储的对象。
插入、删除慢：会需要进行数组扩容操作。而且在插入和删除时需要复制数组到新的数组，进行对象的移动，效率低。
（扩容机制： 数组默认长度为10，扩容时自动扩大为原容量的1.5倍）
（主要方法：add（obj）、get（index）、remove（obj）、remove（index））

/*** 自己实现一个ArrayList，帮助理解其底层实现;笔试一般写get，add，remove 底层通过数组实现。*/
public class MyArrayList {private Object[] elementDate;//底层是数组private int size;//对象的个数public int size() {return size;}public MyArrayList() {this(10);//初始数组长度设为固定值}public MyArrayList(int initialCapacity) {//也可以在初始化ArrayList时就指定数组长度if (initialCapacity < 0) {try {throw new Exception();} catch (Exception e) {e.printStackTrace();}}elementDate = new Object[initialCapacity];}/*** 扩容*/private void extendCap() {if (size + 1 > elementDate.length) {//如果size+1超过数组长度Object[] newArray = new Object[size * 2 + 1];//先建立一个新的数组，昌都市现在size的两倍+1System.arraycopy(elementDate, 0, newArray, 0, elementDate.length);// 数组拷贝elementDate = newArray;//使源数组等于新建数组}}
/*** index处存放obj，数组后移* @param index* @param obj*/public void add(int index, Object obj) {checkIndex(index);//检查indexextendCap();//扩容System.arraycopy(elementDate, index, elementDate, index + 1, size- index );elementDate[index] = obj;size++;}public void add(Object obj) {// 应当先扩容extendCap();// 赋值elementDate[size] = obj;// 自增size++;}/*** 判断是否为空* @return*/public boolean isEmpty() {return size == 0;}public Object get(int index) {checkIndex(index);return elementDate[index];}public void set(int index, Object obj) {elementDate[index] = obj;}private void checkIndex(int index) {if (index <= size - 1 && index >= 0) {} else {throw new IndexOutOfBoundsException("index:" + index + "  size:"+ size);}}public void remove(Object obj) {for (int i = 0; i < size; i++) {if (get(i).equals(obj)) {// 注意底层调用的是equals方法而不是==remove(i);// 底层是只删除第一个}}}public void print() {for (int i = 0; i < size; i++) {System.out.print("  " + elementDate[i]);}}public void remove(int index) {checkIndex(index);int numMoved = size - index - 1;if (numMoved > 0) {System.arraycopy(elementDate, index + 1, elementDate, index,numMoved);elementDate[--size] = null;}}
}

3、LinkedList底层实现模拟（底层链表）

查询慢：查询都需要从头结点开始循环遍历查询指定节点的对象。
增加、删除快：直接改变结点的前后结点指向，不需要移动数据。

（1）构造链表的结点类

/*** 构造节点类* @author Linlin Zhao* */
public class Node {Node previous;//前一个节点Object obj;//对象Node next;//下一个节点/*** 构造器* * @param previous* @param obj* @param next*/public Node(Node previous, Object obj, Node next) {super();this.previous = previous;this.obj = obj;this.next = next;}/*** 构造器*/public Node() {}}

（2）链表实现LinkedList

/*** 自己实现一个MyLinkedList，帮助理解其底层实现;一般考add和remove* * @author Linlin Zhao* */
public class MyLinkedList {private Node first;//头结点private Node last;//尾结点private int size;//节点个数public void add(Object obj) {Node n = new Node();if (first == null) {//若没有头结点，直接将对象放在头结点n.previous = null;n.obj = obj;n.next = null;first = n;last = n;} else {// 直接往last结点后加新的结点n.previous = last;n.next = null;n.obj = obj;last.next = n;last = n;}size++;}public int size() {return this.size;}public Object get(int index) {checkIndex(index);Node tempNode = node(index);return tempNode.obj;}private void checkIndex(int index) {if (index < size && index >= 0) {} else {throw new IndexOutOfBoundsException("index:" + index + "  size:"+ size);}}public void remove(int index) {checkIndex(index);Node tempNode = node(index);if (tempNode != null) {Node upNode = tempNode.previous;Node downNode = tempNode.next;upNode.next = downNode;downNode.previous = upNode;}size--;}/*** 即通过节点遍历实现索引的功能* * @param index* @return*/private Node node(int index) {Node tempNode = null;if (first != null) {tempNode = first;for (int i = 0; i < index; i++) {tempNode = tempNode.next;}}return tempNode;}public void add(int index, Object obj) {checkIndex(index);Node tempNode = node(index);if (tempNode != null) {Node upNode = tempNode.previous;Node downNode = tempNode.next;Node add = new Node();add.next = downNode;add.obj = obj;add.previous = upNode;size++;}}
}

4、Vector底层实现

Vector的底层实现与ArrayList十分相似，也是通过数组实现。最大的区别就是Vector是线程安全的，绝大多数方法都用synchronized修饰。