表-List, ArrayList, LinkedList 实现学习笔记

1. 表的java实现

咱们程序员入门C语言一开始就介绍的

1.1 数组实现 

主要就是查询快，删除，插入 时间复杂度O(N)，比如删除第一个元素，那么后面的元素就要整体向前移动，而查询就比较简单了时间复杂度O(1)

1.2 链表实现 :  插入删除快，查询较复杂 

 

2. ArrayList 数组实现

    预先定义的基本属性

 

     // 默认的容量
    private static  final  int DEFAULT_CAPACITY = 10;
    // 长度
    private int size;
    // 元素
    private E [] items;

    用数组来保存list里面的元素。

 

2.1 capacity 容量 

capacity 是什么样一个概念：感觉很直观的理解就是一个预先估计的容量，为后面新来的元素有了一个准备，不必每次新添加元素这边都要做扩容处理影响效率（所以ArrayList在空间上这部分是浪费的）。

 

public void ensureCapacity(int newCapacity){
        if ( newCapacity < size) {
            return;
        }

        E [] old = items;
        items = (E []) new Objects [newCapacity];

        for (int i = 0; i < size(); i++) {
            items [i] = old[i];
        }
    }

 

 

 2.2 add 

public void add (E ele) {
    add(size(), ele) ;
}

public void add (int index, E ele) {
    if ( items.length == size()) {
        // 扩容机制 jdk 1.5 倍 + 1
ensureCapacity (size() * 2 + 1);
    }
    // 插入点，向后移动，后面有位置
for ( int i = size; i > index; i-- ) {
        items [i] = items [i - 1];
    }
    items[index] = ele;
}

 

 2.3 remove

 

 public E remove (int index) {
        E removeItem = items[index];
        // 向前缩进
        for ( int i = index; i < size() - 1; i++) {
            items [i] = items[i - 1];
        }
        size --;
        return removeItem;
    }

 3.LinkedList 实现

  3.1 Node 节点

   LinkedList 是双链表来实现的，由节点来构成的，因此我们同时定义了一个节点类Node(内部嵌套)

   

public class Node<E> {
        public E data;
        public Node<E> prev;
        public Node<E> next;

        public Node(E data, Node<E> prev, Node<E> next){
            this.data = data;
            this.prev = prev;
            this.next = next;
        }
    }

   初始化

  

public MyLinkedList () {
    clear();
}

public void clear () {
    beginMarker = new Node<E>(null, null, null);
    endMarker= new Node<E>(null, beginMarker, null);
    beginMarker.next = endMarker;
    size = 0;
}

 

3.2 Node 插入点，删除点

 由于链表添加删除，与操作位置上的节点有关系因此操作前要获取位置上的操作节点

 

public Node<E> getNode (int index){

        return getNode(index, 0, size()-1);
    }

    public Node<E> getNode (int index, int lower, int upper){
        Node<E> p;
        if(index < lower || index > upper) {
            throw new IndexOutOfBoundsException();
        }
        // 判断从前开始还是从后开始，减少循环次数
        if (index < size()/2) {
            p = beginMarker;
            for (int i = 0; i < index; i++){
                p = p.next;
            }
        }else {
            p = endMarker;
            for (int i = size(); i > index; i--) {
                p = p.prev;
            }
        }
        return p;
    }

 

3.3 Node 新增

    public void add(int index, E ele){
        addBefore( getNode(index, 0, size()), ele);
    }

    public void addBefore(Node<E> p, E e){
        Node<E> newNode = new Node<E>(e, p.prev, p);
        p.prev.next = newNode;
        p.prev = newNode;
        size ++;
    }

 

3.3 Node 删除

public void romove(int index){
       romove(getNode(index, 0, size()-1));
    }
    public void romove(Node<E> p){
        p.prev.next = p.next;
        p.next.prev = p.prev;
        size--;
    }

 4.总结

    ArrayList,LinkedList都是非同步的。这点区别于Vector