欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-31 08:22:41
...

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