Data Structure


数据结构 Java版


Introduction

基础

数据结构

数组 链表 栈 队列

基础算法讲解

复杂度分析 递归算法 排序算法

进阶

树 散列表 图 堆

进阶算法

Hash

字符串匹配算法 (bf \ kpm …)

堆排序

算法思想

分支 贪心 动态规划

Day 1

Target : 线性表 \\ 数组数据结构: ArrayList \\ 链表数据结构:LinkedList \\ 栈:Stack 队列

线性表

每个数据最多只有前后2个方向

数组

线性表 一组连续的内存空间存储一组具有相同类型的数据

元素访问

a[i] = baseAddress + i * dataTypeSize
  • 插入

需要移动插入位置后的所有元素

也可将第K位的元素移动到最后

  • 删除

删除连续 如果不搬移数据 内存就会有空洞

删除时先进行标记 等到无空间时 再进行真正的删除

PS: JVM标记清楚垃圾回收算法


ArrayList :: 数组在Java中的应用

ArrayList底层采用数组进行储存

源码分析 (节选)

常量

// 默认创建的长度是 10
private static final int DEFAULT_CAPACITY = 10;
// 空元素
private static final Object[] EMPTY_ELEMENTDATA = {};
// 空元素
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 存放数据的数组
transient Object[] elementData;
// 元素个数
private int size;
// 最大长度 Integer最大值-8 = 2147483639
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

空参构造函数

public ArrayList() {
        // 存储数据元素 = 空的元素集
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

方法

public boolean add(E e){
        // 对长度进行确认
        ensureCapacityInternal(size + 1);
        // elementData[size] = e;
        // size ++;
        elementData[size++] = e;
        return true;
    }
private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
private void ensureExplicitCapacity(int minCapacity) {
        // TODO: Not clear
        modCount++;

        // 判断size+1后是否大于当前的存储长度
        if (minCapacity - elementData.length > 0)
            // 调用grow() 函数进行加长
            grow(minCapacity);
    }
// 传入 当前存储的数据 size+1
private static int calculateCapacity(Object[] elementData, int minCapacity) {
        // 检查存储的数据是否为空
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            // 返回 10和size+1的最大值
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        // 否则返回 size+1
        return minCapacity;
    }

grow()

private void grow(int minCapacity) {
        // overflow-conscious code

           // 存储目前元素个数
        int oldCapacity = elementData.length;
        // 新长度 = 旧 + 旧 * 0.5
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 增长后仍达不到所需要的长度 即 size+1
        if (newCapacity - minCapacity < 0)
            // 新长度 = 所需要的长度
            newCapacity = minCapacity;
        // 新长度突破上限
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            // 调用 hugeCapacity() 进行处理
            newCapacity = hugeCapacity(minCapacity);
        // 调整后的存储的元素 = 当前存储的元素拷贝到增长后的数组中
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

元素获取

public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

// 范围检查
private void rangeCheck(int index) {
        // 检查是否越界
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

Day2

LinkedList 双向链表

变量

// 默认长度为 0
transient int size = 0;
// 整个链表的头结点和尾节点
transient Node<E> first;
transient Node<E> last;

构造方法

public LinkedList(){

}

添加一个元素

public boolean add(E e) {
    linkLast(e);
    return true;
  }

// 将e拼接到最后
void linkLast(E e) {
    // 链尾节点暂存
    final Node<E> l = last;
    // 新节点 构建 : 
    //       前节点是当前节点的尾节点 内容是e 尾节点 Null
    final Node<E> newNode = new Node<>(l, e, null);
    // 链尾节点 = 新节点  将新节点放到链的尾节点处
    last = newNode;
    // 如果改变前的链尾为空 即链什么都没
    if (l == null)
        // 前节点为 新节点
        first = newNode;
    else
        // 链尾的后节点为新
        l.next = newNode;
    // 长度增加
    size ++;
    modCount++;
  }

// 节点的构造
private static class Node<E> {
        // 内容
        E item;
        // 前节点
        Node<E> next;
        // 后节点
        Node<E> prev;

        // 有参构造方法
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

获取元素

public E get(int index) {
        // 检查 index是否合法
        checkElementIndex(index);
        // 返回
        return node(index).item;
    }
private void checkElementIndex(int index) {
        // 抛出异常
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
private boolean isElementIndex(int index) {
        // 是否大于0 且不越界
        return index >= 0 && index < size;
    }
Node<E> node(int index) {
        // assert isElementIndex(index);

        // 折中查找
        // 小于长度的一半 从前找
        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;
        }
    }

LeetCode 206 - Reverse Linked List

Solution 1

class Solution {
    public ListNode reverseList(ListNode head) {
        // 当前元素
        ListNode curr = head;
        // 当前元素的前一个
        ListNode prev = null;
        while(curr != null){
            // 获取下一个元素
            ListNode nextNode = curr.next;
            // 当前节点指向前一个节点
            curr.next = prev;
            prev = curr;
            curr = nextNode;

        }
        return prev;

    }
}

Solution 2

class Solution {
    public ListNode reverseList(ListNode head) {
        //递归终止条件是当前为空,或者下一个节点为空
        if (head==null || head.next==null) {
            return head;
        }
        //这里的cur就是最后一个节点
        ListNode cur = reverseList(head.next);
        //如果链表是 1->2->3->4->5,那么此时的cur就是5
        //而head是4,head的下一个是5,下下一个是空
        //所以head.next.next 就是5->4
        head.next.next = head;
        //防止链表循环,需要将head.next设置为空
        head.next = null;
        //每层递归函数都返回cur,也就是最后一个节点
        return cur;
    }
}

transient 变量修饰符,如果用transient声明一个实例变量 当对象存储时 它的值不需要维持 即不持久化 也就是说不会为这个变量分配内存来保存



本文作者:Ge15emium
版权声明:本博客所有文章除特别声明外,均采用 CC BY-SA 3.0协议 。转载请注明出处!