一.手写ArrayList

public class ArrayList {    private Object[] elementData;       //底层数组    private int size;                   //数组大小    public int size(){        /*         * 返回数组大小         */        return size;    }    public ArrayList(){        /*         * 无参构造器，通过显式调用含参构造器         */        this(10);    }    public ArrayList(int initialCapacity){        /*         * 1.含参构造器         * 2.要对传入的初始量的合法性进行检测         * 3.通过新建数组实现         */        if(initialCapacity<0){            try {                throw new Exception();            } catch (Exception e) {                // TODO Auto-generated catch block                e.printStackTrace();            }        }        elementData=new Object[initialCapacity];    }    public boolean isEmpty(){        /*         * 判断是否为空         */        return size==0;    }    public Object get(int index){
   //获取指定位置的元素        /*         * 1.获取指定下标的对象         * 2.下标合法性检测         */        rangeCheck(index);        return elementData[index];    }    public boolean add(Object obj){
   //在末尾添加元素        /*         * 添加对象（不指定位置）         * 注意数组扩容         */        ensureCapacity();        elementData[size]=obj;        size++;        return true;    }       public void add(int index,Object obj){
   //在指定位置添加元素        /*         * 插入操作（指定位置）         * 1.下标合法性检查         * 2.数组容量检查、扩容         * 3.数组复制（原数组，开始下标，目的数组，开始下标，长度）         */        rangeCheck(index);        ensureCapacity();        System.arraycopy(elementData, index, elementData, index+1,size-index);        elementData[index]=obj;        size++;    }    public Object remove(int index){
   //删除指定位置元素        /*         * 1.删除指定下标对象，并返回其值         * 2.下标合法性检测         * 3.通过数组复制实现         * 4.因为前移，数组最后一位要置为空         */            rangeCheck(index);            int arrnums=size-index-1;            Object oldValue=elementData[index];            if(arrnums>0){                System.arraycopy(elementData, index+1, elementData,index, arrnums);            }            elementData[--size]=null;            return oldValue;        }       public boolean remove(Object obj){
   //删除指定元素        /*         * 1.删除指定对象         * 2.通过遍历         * 3.equals的底层运用，找到下标，调用remove(int i)         */        for(int i=0;i
     
      =size){            try {                throw new Exception();            } catch (Exception e) {                // TODO Auto-generated catch block                e.printStackTrace();            }        }    }    private void ensureCapacity(){        /*         * 1.对容器容量的检查         * 2.数组扩容，通过数组复制来实现（量和值两者都要保障）         */        if(size==elementData.length){            Object[] newArray=new Object[size*2+1];            System.arraycopy(elementData, 0, newArray, 0, elementData.length);            elementData=newArray;        }    }    public int indexOf(Object obj) {
   //查询元素第一次出现的位置          //ArrayList中的元素可以为null，如果为null返回null的下标            if (obj == null) {                for (int i = 0; i < size; i++)                    if (elementData[i]==null)                        return i;            } else {                for (int i = 0; i < size; i++)                    if (obj.equals(elementData[i]))                        return i;            }            //如果没有找到对应的元素返回-1。            return -1;    }    public int lastIndexOf(Object obj) {
   //查询元素最后一次出现的位置        if (obj == null) {        //如果o为null从后往前找到第一个为null的下标            for (int i = size-1; i >= 0; i--)                if (elementData[i]==null)                    return i;        } else {        //从后往前找到第一个值为o的下标            for (int i = size-1; i >= 0; i--)                if (obj.equals(elementData[i]))                    return i;        }        return -1;    }}
     

二.手写LinkedList

package com.whzc.ywb.study.section03.linkedList;/** * 自己实现链表 * @author ywb * * @param 
     
       */public class LinkedList
      
        {    private class Node{        public E e;//元素        public Node next;//指针        public Node(E e,Node next) {
   //传入元素和指针            this.e = e;            this.next = next;        }        public Node(){
   //不传入元素和指针            this(null,null);//this是传入两个参数的构造器        }        public Node(E e){            this(e,null);        }                @Override        public String toString() {            return "Node [e=" + e + "]";        }    }        private Node dummyHead;    private int size;    public LinkedList(){        dummyHead = new Node(null,null);        size = 0;    }    public int getSize(){        return size;    }    public boolean isEmpty(){        return size == 0;    }    public void addFirst(E e){
   //在链表头添加元素        /*Node node = new Node(e);        node.next = head;        head = node;*/    //用下面一行代码代替        //head = new Node(e,head);//括号内的head是之前的链表的头结点，左边的head是现在的头结点        add(0,e);    }    public void addLast(E e){
   //在链表的尾部添加元素        add(size,e);    }    public void add(int index,E e){
   //在链表中间添加元素        if(index < 0 || index > size){            throw new IllegalArgumentException("索引越界异常");        }        Node prev = dummyHead;//定义一个指针指向头结点        for(int i = 0 ; i < index ; i++){            prev = prev.next;//将这个指针移动到要插入的位置的前一个元素        }        /*Node node = new Node(e);        node.next = prev.next;        prev.next = node;*/    //注意这两行代码的顺序。用下面一行代码实现        prev.next = new Node(e,prev.next);        size ++;    }    public E get(int index){        if(index < 0 || index > size){            throw new IllegalArgumentException("索引越界异常");        }        Node cur = dummyHead.next;        for(int i = 0 ; i < index ; i++){            cur = cur.next;        }        return cur.e;    }    public E getFirst(){        return get(0);    }    public E getLast(){        return get(size-1);    }    public void update(int index,E e){
   //修改某个元素        if(index < 0 || index > size){            throw new IllegalArgumentException("索引越界异常");        }        Node cur = dummyHead.next;        for(int i = 0 ; i < index ; i++){            cur = cur.next;        }        cur.e = e;    }    public boolean contains(E e){
   //查询链表中是否存在某个元素        Node node = dummyHead.next;        while (node != null){            if(node.e.equals(e)){                return true;            }            node = node.next;        }        return false;    }    public void delete(int index){
   //删除元素        if(index < 0 || index > size){            throw new IllegalArgumentException("索引越界异常");        }        Node prev = dummyHead;        for(int i = 0 ; i < index ; i++){            prev = prev.next;        }        /*prev.next = prev.next.next;//注意！！！ 这是错误的        prev.next.next = null;*/        Node cur = prev.next;        prev.next = cur.next;        cur.next = null;        size--;    }    public void deleteFirst(){        delete(0);    }    public void deleteLast(){        delete(size-1);    }    public void deleteElement(E e){        Node prev = dummyHead;        while(prev.next != null){            if(prev.next.e.equals(e))                break;            prev = prev.next;        }        if(prev.next != null){            Node delNode = prev.next;            prev.next = delNode.next;            delNode.next = null;            size --;        }    }}
      
     

三.分析ArrayList和LinkedList的区别

　　从底层上分析

　　　　　　ArrayList的底层是由数组实现的，而LinkedList的底层是由链表实现的。

　　　　　　ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间

　　从效率上分析

　　　　　　1.当随机访问List时（get和set操作），ArrayList比LinkedList的效率更高，因为LinkedList是线性的数据存储方式，所以需要移动指针从前往后依次查找。

　　　　　　2.当对数据进行增加和删除的操作时(add和remove操作)，LinkedList比ArrayList的效率更高，因为ArrayList是数组，所以在其中进行增删操作时，会对操作点之后所有数据的下标索引造成影响，需要进行数据的移动。

　　　　　　3.从利用效率来看，ArrayList自由性较低，因为它需要手动的设置固定大小的容量，但是它的使用比较方便，只需要创建，然后添加数据，通过调用下标进行使用；而LinkedList自由性较高，能够动态的随数据量的变化而变化，但是它不便于使用。

　　　　　　4.ArrayList主要控件开销在于需要在lList列表预留一定空间；而LinkList主要控件开销在于需要存储结点信息以及结点指针信息。对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。对 ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个开销是 统一的，分配一个内部Entry对象。

　　　　　　5.LinkedList集合不支持 高效的随机随机访问（RandomAccess），因为可能产生二次项的行为。