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

Java基础数据结构及其实现原理(一)

程序员文章站 2024-02-06 22:59:40
...

Java基础数据结构

Java类库中的基础数据结构

关注的问题:

  • 实现的方式 基础的数据结构
  • 是否有序 是否为空 是否重复

Java基础数据结构及其实现原理(一)

1, List

ArrayList的实现原理

实现原理:数组,可扩容

基本的特点:

  • 查询快
  • 增删慢
//无参构造 默认容量是空
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//有参构造
public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

添加的实现 基本就是数组的实现方式

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
//主要是动态扩容的实现


    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }


private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);//每次扩容为原来的容量的一半
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

删除的方式1. 指定元素删除2.指定坐标删除

//按照坐标删除
public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

//指定元素删除
public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
//不检测下标直接删除
private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }

迭代器的使用

待补充

LinkedList的实现原理

实现原理:双向链表

LinkedList 添加元素 删除元素 查看元素
链表 add(),set() remove() get()
队列 offer() poll() peek()
push() pop() -

插入方法:

public boolean add(E e) {
    linkLast(e);
    return true;
}
//添加新节点的方式 将新节点前驱-last 后继-null
void linkLast(E e) {
    final Node<E> l = last;
    //Node(Node<E> prev, E element, Node<E> next)
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    
    //判断链表是否有元素 有的话添加链表关系
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

//添加新节点的方式 前驱null 后继first
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    //判断链表是否有元素 有的话添加关系
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}
//按照下标添加
public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        //element要插入的节点
        //node(index)原来位置的节点
        linkBefore(element, node(index));
}
//添加指定节点 在succ前面添加节点
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    //Node(Node<E> prev, E element, Node<E> next)
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

删除方法

//指定对象的删除方法
public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

//指定下标的删除方法

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

//删除链表的操作
E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        //说明是链表首位
        first = next;
    } else {
        //链表前驱更改
        //节点的前驱节点的后继指向节点的后继
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        //链表后继更改
        //节点的后继节点的前驱指向节点的前驱
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}


//获取index位置的元素节点
Node<E> node(int index) {
    // assert isElementIndex(index);
	//双向链表,当节点index比size的一半大,反向搜索;反向正向
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

//删除头节点的操作
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    
    //关键
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

查找方法

//查找下标
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
//查找
相关标签: 数据结构与算法