Java基础-集合(二）

集合基础知识（List）

List的实现类的源码实现：ArrayList、LinkedList

ArrayList源码：

public void MyArrayList(){
    //创建一个Object数组elementData，用来存放ArrayList的内容
    private Object[] elememtData;
    
    //由于数组可能需要进行扩容，所以用size来记录数组已经使用的长度
    private int size;
    
public void add(Object obj){
    //初始化数组，长度为10
    elementData = new Object[10];
    //如果数组的已经使用的长度超过或者等于数组的长度，那么就要扩容
    if (size>=elementData.length){
        //扩容的方法是利用一个临时数组，临时数组的长度初始化为原数组的两倍
        Object[] tmp = new Object[elementData.length*2];
        System.arraycopy(elementData,0,tmp,0,size);
        //利用arraycopy方法将elementData的内容复制到临时数组，并将elementData指向临时数组，引用临时数组
        elementData = tmp;
        }
        //将添加的obj放入数组的下一个位置
        elementData[size++] = obj;
    }
        

ArrayList的优点：因为是数组，所以遍历很快
ArrayListr的缺点：因为要判断数组的长度，所以添加会麻烦一点

LinkedList源码：
Node:

public class Node(){
    //用来保存当前节点
    public Object obj;
    //存放前一个节点
    public Node prev;
    //存放在一个节点
    public Node next;
    //构造函数，初始化节点
    public Node(Object obj, Node prev, Node next) {
		super();
		this.obj = obj;
		this.prev = prev;
		this.next = next;
	}
	//由于有的节点没有prev或者next，所有构造一个无参的构造函数
	public Node() {
		
	}
    
    public setObj(Object obj){
        this.obj = obj;
        }

LinkedList:

public class LinkedList(){
    private Node first;
    private Node last;
    public void add(Object obj){
        Node node = new Node();
        if (node == null){
            node.prev = null;
            node.next = null;
            node.setObj(obj);
            first = node;
            last = node;
        }else{
            node.prev = last;
            node.next = null;
            node.setObj(obj);
            //last原本next指向null,现在加入了一个节点后,next要指向添加的节点
            last.next = node;
            //更新last为添加的节点
            last = node;
        }
            

LinkedList的优点：插入删除很快，只需要移动指针就可以了
LinkedList的缺点：遍历很慢，因为需要不断的移动指针，消耗很大