美文网首页
数据结构Java源码分析

数据结构Java源码分析

作者: SimpleRRR | 来源:发表于2018-04-03 11:12 被阅读0次

    参考书籍《大话数据结构》,实现参考JDK1.8

    线性表:

    Java实现类有ArrayList,LinkedList

    ArrayList:

    动态容量数组的列表,扩展类有序数组
    int size;//数据大小
    Object[] data;//容量数组
    默认数组是空数组,容量为0,默认增加容量值是10,DEFAULT_CAPACITY

    扩容规则:传入扩容值为minCapacity,若当前数组是空数组,扩容值为max(minCapacity,DEFAULT_CAPACITY),否则判断minCapacity - size,若大于0默认将当前容量 + 当前容量扩大2倍为newCapacity,newCapacity若小于minCapacity,容量值为minCapacity,否则为newCapacity,然后进行数组拷贝生成新数组。

    添加/插入:添加时先检查是否需要扩容,然后给size+1赋值,插入操作是检查插入位置是否在范围,不在范围就抛异常,在范围进行检查是否需要扩容,然后进行数据移动拷贝arraycopy(data,index,data,index+1,size - index),data[size++] = o,底层C实现,时间复杂度O(n)
    删除:检查删除位置是否在范围,然后再进行数据移动拷贝(data,index + 1,data,index - 1, size - index - 1),data[--size] = null
    查找/搜索:指定位置查找,O(1),对象查找indexOf(Object) 顺序查找O(n),
    排序:冒泡排序O(n^2)
    优缺点:顺序储存,索引查找快,增删慢

    LinkedList(实现了Deque双端队列接口):

    链表:动态容量的双向链式列表,扩展类有单向链表,循环链表,双向链表,静态链表

    int size;//数据大小
    Node<E> first;//头节点
    Node<E> last;//尾节点

    class Node<E>{
    E item;//数据元素
    Node<E> prev;//节点前驱
    Node<E> next;//节点后驱
    }
    默认是空链表,容量为0

    扩容规则:无数量限制,添加多少元素增加多少节点,数量为size
    添加/插入

    //默认添加是从尾部插入
    Node l = last; 
    Node newNode = (l,o,null);
    last = newMode;
    if(l== null) first = newNode; 
    else l.next = newMode;
    size++;
    
    //头部插入
    Node l = first;
    Node newNode = (null,o,l);
    first = newMode; 
    if(l == null) last = newMode;
    else l.prev = newMode;size++;
    

    查找/搜索:双向链表通过传入的index/2判断从头部还是尾部遍历搜索,查找到节点E,次数为n/2,O(n)
    删除:remove()方法默认删除头部,传入obj进行删除的话,步骤是先查找到节点S,然后进行链接清除

    Node prev = s.prev;Node next = s.next;
    if(prev != null){prev.next = next;s.prev=null;}else{first=next};
    if(next != null){next.prev = prev;s.next=null;}else{last=next};
    s.item = null;
    size--;
    

    具有Collection的操作方法
    add();
    remove();

    具有队列Queue的操作方法
    peek(),element();
    offer();
    poll();
    E remove();

    peek()方法取出队列头部元素时候,不删除该元素,而poll()方法取出元素时会删除元素。如果遇到队列为空的情况是,两者都会返回null,element()会抛出异常

    双端队列Deque(继承队列接口,具有栈)的操作方法:
    所有的操作方法peekFirst,peekLast.....
    push()无空间会抛异常
    pop()无元素会抛异常

    优缺点:不受固定的存储空间限制,快速的插入和删除操作,整块集合插入为O(1),查询效率比顺序列表低,O(n)

    栈和队列:

    栈是限定仅在表尾进行插入和删除操作的线性表
    队列是只允许在一端进行插入操作,在另一端进行删除操作的线性表

    栈/队列的二种实现:数组实现栈,队列,链表实现简述(见上面LinkedList)
    ArrayDeque

    object[] elements;//元素数组
    int head;//头部数据的位置索引
    int tail;//尾部数据的位置索引

    扩容规则:默认长度16,传入值会转换成2^n,当头部head == tail时,说明没有位置可以储存数据,进行扩容2倍,然后将数据拷贝到新数组头部,head重新赋值0,tail赋值为原来的数组长度n

    private void doubleCapacity() {
            assert head == tail;
            int p = head;
            int n = elements.length;
            int r = n - p; // number of elements to the right of p
            int newCapacity = n << 1;
            if (newCapacity < 0)
                throw new IllegalStateException("Sorry, deque too big");
            Object[] a = new Object[newCapacity];
            System.arraycopy(elements, p, a, 0, r);
            System.arraycopy(elements, 0, a, r, p);
            elements = a;
            head = 0;
            tail = n;
        }
    

    添加/插入:设置后检测是否需要扩容

    public void addFirst(E e) {
            if (e == null)
                throw new NullPointerException();
            elements[head = (head - 1) & (elements.length - 1)] = e;
            if (head == tail)
                doubleCapacity();
        }
    
     public void addLast(E e) {
            if (e == null)
                throw new NullPointerException();
            elements[tail] = e;
            if ( (tail = (tail + 1) & (elements.length - 1)) == head)
                doubleCapacity();
        }
    

    删除:删除前后元素时间复杂度为O(1),然后修改head或者tail,删除对象会遍历数组O(n),找到相应下标,然后移动拷贝整个数组
    查找/搜索:获取前后元素为O(1)
    排序:无
    优缺点:查找元素,删除前后元素效率高,删除其他位置O(n)

    栈(LIFO,FILO)常用方法是void push(),E pop(),操作失败抛出异常,默认调用的是addFirst,removeFirst
    队列(FIFO)常用方法是boolean offer(E),E poll(),操作失败返回false,null,默认调用的是addLast,pollFirst

    零个或多个字符组成的有限序列
    String

    char[] value;//字符数组
    int hash;//hash值

    固定长度,构造方法不传如数组或串,默认为空串"",不可变类,操作形成新的String对象

    操作方法:
    String(char[] arr)
    String(String str)
    String(byte[] bytes)
    length()
    getChars(char[] buf,int len)
    isEmpty()
    charAt(int index)
    compareTo
    startWith
    indexOf
    subString
    replaceAll
    split
    concat

    startWith,endWitdh
    偏移length进行普通匹配算法O(n-m+1)

    indexOf
    普通匹配算法O(n-m+1)*m,KMP子串匹配算法O(n+m)

    replaceAll
    正则匹配实现

    HashMap KV对集合,字典

    相关文章

      网友评论

          本文标题:数据结构Java源码分析

          本文链接:https://www.haomeiwen.com/subject/whqmcftx.html