漫画算法读书笔记(一) 数据结构基础

数组

  • 数据是由有限个相同类型的变量所组成的有序集合；
  • 物理存储方式是顺序存储访问方式是随机访问；
  • 利用下标查找数组元素和修改数组元素的时间复杂度是O(1)；
  • 中间插入，删除数组元素的时间复杂度是O(n)。
  • 适合读操作多，写操作少的场景
  • 基本操作
    • 读取
    • 更新
    • 删除
    • 插入
      • 尾部插入
      • 中间插入
      • 超范围插入(双倍扩容)

链表

  • 链表是一种链式数据结构，右若干节点组成，每个节点包含指向下一个节点的指针；
  • 物理存储方式是随机存储，访问方式是顺序访问；
  • 查找链表节点的时间复杂度是O(n)；
  • 中间插入、删除节点的时间复杂度是O(1)；
  • 适合插入删除元素多的场景；
  • 基本操作：
    • 查找节点
    • 更新节点
    • 插入节点
      • 尾部插入
      • 头部插入
      • 中间插入
    • 删除元素
      • 尾部删除
      • 中间删除
      • 头部删除

栈

  • 栈是一种线性逻辑结构
  • 可以用数组实现，也可以用链表时间
  • 遵循先入后出的原则(FILO)
  • 基本操作
  • 出栈
  • 入栈

队列

  • 队列也是一种线性逻辑结构
  • 可以用数组实现，也可以用链表实现
  • 遵循先进先出的原则(FIFO)
  • 基本操作
    • 入队
    • 出队

散列表

  • 又叫哈希表，存储Key-Value的集合，对于某一个key，散列表可以在接近O(1)的时间内进行读写操作，散列表通过哈希函数实现key和数组下标的转换；
  • 通过开放寻址法和链表法来解决哈希冲突的问题。
  • 基本操作
    • 写操作
    • 读操作
    • 扩容

数组链表复杂度对比

类型 查找 更新 插入 删除
数组 O(1) O(1) O(n) O(n)
链表 O(n) O(n) O(1) O(1)

逻辑结构与物理机构

  • 逻辑结构
    • 线性结构: 顺序表、栈、队列
    • 非线性结构：树、图
  • 物理结构
    • 顺序存储结构：数组
    • 链式存储结构：链表

附 相关代码

手写数组

代码在 github 上， write-array 分支

package org.jake.write.array;

/**
 * The type Self array.
 */
public class SelfArray {
    //数组集合 用于存放数据
    private int[] array;
    //当前数组的大小
    private int size;

    /**
     * 构造函数 初始化array
     *
     * @param capacity 初始化大小
     */
    public SelfArray(int capacity) {
        this.array = new int[capacity];
        size = 0;
    }


    /**
     * 插入一条数据
     *
     * @param index   插入的位置
     * @param element 插入的元素
     */
    public void insert(int index, int element) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("数组下标越界");
        }
        //如果size 大于等于数组的长度了 先进行扩容
        if (size >= array.length) {
            resize();
        }
        //从右到左循环，每个元素向右移动
        for (int i = size - 1; i > index; i--) {
            array[i + 1] = array[i];
        }
        array[index] = element;
        //size 增加一位
        size++;
    }

    /**
     * 删除元素
     *
     * @param index 删除元素的坐标
     * @return 删除的元素
     */
    public int delete(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("数组下标越界");
        }
        //获取删除的元素
        int deletedElement = array[index];
        //从左到右 以此左移一位
        for (int i = index; i < size; i++) {
            array[i] = array[i + 1];
        }
        size--;
        return deletedElement;
    }

    /**
     * Output.
     */
    public void output(){
        for(int i=0; i<size; i++){
            System.out.println(array[i]);
        }
    }

    /**
     * 扩容 扩容的大小为当前容器的两倍
     */
    private void resize() {
        int[] newArr = new int[array.length * 2];
        System.arraycopy(array, 0, newArr, 0, array.length);
        array = newArr;
    }
}

手写链表

代码在 github 上， write-linkedlist 分支

Node.class

package org.jake.write.linked.list;

public class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
    }
}

SelfLinkedList.class

package org.jake.write.linked.list;

/**
 * The type Self linked list.
 */
public class SelfLinkedList {

    //头节点指针
    private Node head;
    //尾节点指针
    private Node last;
    //链表的实际长度
    private int size;


    /**
     * 插入元素
     *
     * @param data  插入的数据
     * @param index the index 插入的位置
     * @throws Exception the exception
     */
    public void insert(int data, int index) throws Exception {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("数组下标越界");
        }
        Node insertedNode = new Node(data);
        if (size == 0) {
            //如果是空链表的话  收尾节点都是当前节点
            head = insertedNode;
            last = insertedNode;
        } else if (index == 0) {
            //如果是插入头部 之前的头部节点成为新增节点的下一个节点，新增节点成为头部节点
            insertedNode.next = head;
            head = insertedNode;
        } else if (size == index) {
            //如果是尾部插入 之前的尾部节点的next节点 成为新增新增节点  新增节点成为尾节点
            last.next = insertedNode;
            last = insertedNode;
        } else {
            Node prevNode = get(index - 1);
            insertedNode.next = prevNode.next;
            prevNode.next = insertedNode;
        }
        size++;
    }


    /**
     * 节点的删除
     *
     * @param index the index
     * @return the node
     */
    public Node remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("数组下标越界");
        }
        Node removedNode = null;
        if (index == 0) {
            //删除头结点
            removedNode = head;
            head = head.next;
        } else if (index == size - 1) {
            //删除尾节点
            Node prevNode = get(index - 1);
            removedNode = prevNode.next;
            prevNode.next=null;
            last = prevNode;
        }else {
            //删除中间节点
            Node prevNode = get(index-1);
            Node nextNode = prevNode.next.next;
            removedNode = prevNode.next;
            prevNode.next= nextNode;
        }
        size--;
        return removedNode;
    }


    /**
     * Get node.
     *
     * @param index the index
     * @return the node
     */
    public Node get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("数组下标越界");
        }
        Node temp = head;
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp;
    }

    /**
     * Output.
     */
    public void output() {
        Node temp = head;
        while (temp != null) {
            System.out.println(temp.data);
            temp = temp.next;
        }
    }


}

手写栈

代码在 github 上， write-stack 分支

Stack.class

package org.yujuan.write.stack;

/**
 * The interface Stack.
 *
 * @param <E> the type parameter
 * @author yujuan
 * @time 2019 /09/26 10:09:37
 */
public interface Stack<E> {

    /**
     * Length int.
     *
     * @return the int
     * @author yujuan
     * @time 2019 /09/26 10:09:37
     */
    int length();

    /**
     * Pop e.
     *
     * @return the e
     * @author yujuan
     * @time 2019 /09/26 10:09:37
     */
    E pop();

    /**
     * Push.
     *
     * @param element the element
     * @author yujuan
     * @time 2019 /09/26 10:09:37
     */
    void push(E element);

    /**
     * Peek e.
     *
     * @return the e
     * @author yujuan
     * @time 2019 /09/26 10:09:37
     */
    E peek();

    /**
     * Empty boolean.
     *
     * @return the boolean
     * @author yujuan
     * @time 2019 /09/26 10:09:37
     */
    boolean empty();

    /**
     * Clear.
     *
     * @author yujuan
     * @time 2019 /09/26 10:09:37
     */
    void clear();
}

SelfStack.class

package org.yujuan.write.stack;

import java.util.Arrays;

public class SelfStack<E> implements Stack<E> {

    private int DEFAULT_SIZE = 16;
    private int capacity;

    private int size;

    private Object[] elementData;

    public SelfStack() {
        capacity = DEFAULT_SIZE;
        elementData = new Object[capacity];
    }

    public SelfStack(int initSize) {
        capacity = 1;
        //capacity 设置为initSize 的最小二次方
        while (capacity < initSize) {
            capacity <<= 1;
        }
        elementData = new Object[capacity];
    }

    @Override
    public int length() {
        return size;
    }

    @Override
    public E pop() {
        if (empty()) {
            throw new IndexOutOfBoundsException();
        }
        E oldValue = (E) elementData[size - 1];
        elementData[--size] = null;
        return oldValue;
    }

    @Override
    public void push(E element) {
        ensureCapacity(size + 1);
        elementData[size++] = element;
    }


    /**
     * 扩容
     *
     * @param minCapacity
     */
    private void ensureCapacity(int minCapacity) {
        if (minCapacity > capacity) {
            while (capacity < minCapacity) {
                capacity <<= 1;
            }
        }
        elementData = Arrays.copyOf(elementData, capacity);
    }

    @Override
    public E peek() {
        if (empty()) {
            throw new ArrayIndexOutOfBoundsException();
        }
        return (E) elementData[size - 1];
    }

    @Override
    public boolean empty() {
        return size == 0;
    }

    @Override
    public void clear() {
        for (int i = 0; i < size; i++) {
            elementData[i] = null;
        }
        size = 0;
    }
}

手写hashMap

代码在 github 上， write-hash-map 分支

Node.class

package org.jake.write.hash.map;

import java.util.Map;

public class Node<K, V> implements Map.Entry<K, V> {
    private K key;
    private V value;
    private Node<K, V> nextNode; //下一节点

    public Node(K key, V value, Node<K, V> nextNode) {
        super();
        this.key = key;
        this.value = value;
        this.nextNode = nextNode;
    }

    @Override
    public K getKey() {
        return this.key;
    }

    @Override
    public V getValue() {
        return this.value;
    }

    @Override
    public V setValue(V value) {
        this.value = value;
        return this.value;
    }

    public Node<K, V> getNextNode() {
        return nextNode;
    }

    public void setNextNode(Node<K, V> nextNode) {
        this.nextNode = nextNode;
    }

    public void setKey(K key) {
        this.key = key;
    }

    //判断是否还有下一个节点
        /*private boolean hasNext() {
            return true;
        }*/

}

SelfHashMap.class

package org.jake.write.hash.map;

/**
 * The type Self hash map.
 *
 * @param <K> the type parameter
 * @param <V> the type parameter
 */
public class SelfHashMap<K, V> {
    /**
     * The Table.
     */
    private Node<K, V>[] table = null;

    /**
     * The constant DEFAULT_INITIAL_CAPACITY.
     */
    private static int DEFAULT_INITIAL_CAPACITY = 16;

    /**
     * The constant DEFAULT_LOAD_FACTOR.
     */
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * The constant size.
     */
    private static int size;

    /**
     * Put v.
     *
     * @param k the k
     * @param v the v
     * @return the v
     */
    @SuppressWarnings("unchecked")
    public V put(K k, V v) {
        if (table == null) {
            table = new Node[DEFAULT_INITIAL_CAPACITY];
        }

        //如果size大于阈值则进行扩容
        if (size > DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR) {
            resize();
        }

        //2.计算出index角标
        int index = getIndex(k, DEFAULT_INITIAL_CAPACITY);

        //3.将k-v键值对放进相对应的角标，如果计算出角标相同则以链表的形势存放
        Node<K, V> node = table[index];
        if (node == null) {
            table[index] = new Node<>(k, v, null);
            size++;
            return table[index].getValue();
        } else {
            Node<K, V> newNode = node;

            //循环遍历每个节点看看是否存在相同的key
            while (newNode != null) {
                //这里要用equals 和 == 因为key有可能是基本数据类型，也有可能是引用类型
                if (k.equals(newNode.getKey()) || k == newNode.getKey()) {
                    newNode.setValue(v);
                    size++;
                    return v;
                }
                newNode = node.getNextNode();
            }
            table[index] = new Node<K, V>(k, v, table[index]);
            size++;

            return table[index].getValue();
        }

    }

    /**
     * Gets index.
     *
     * @param key    the key
     * @param length the length
     * @return the index
     */
    public int getIndex(K key, int length) {
        int hashCode = key.hashCode();
        int index = hashCode % length;
        return index;
    }

    /**
     * Get v.
     *
     * @param k the k
     * @return the v
     */
    public V get(K k) {
        int index = getIndex(k, DEFAULT_INITIAL_CAPACITY);
        Node<K, V> node = table[index];
        if (k.equals(node.getKey()) || k == node.getKey()) {
            return node.getValue();
        } else {
            Node<K, V> nextNode = node.getNextNode();
            while (nextNode != null) {
                if (k.equals(nextNode.getKey()) || k == nextNode.getKey()) {
                    return nextNode.getValue();
                }
            }
        }
        return null;
    }

    /**
     * Resize.
     */
    @SuppressWarnings("unchecked")
    public void resize() {
        //1.创建新的table长度扩展为以前的两倍
        int newLength = DEFAULT_INITIAL_CAPACITY * 2;
        Node<K, V>[] newtable = new Node[newLength];
        //2.将以前table中的取出，并重新计算index存入
        for (int i = 0; i < table.length; i++) {
            Node<K, V> oldtable = table[i];
            while (oldtable != null) {
                //将table[i]的位置赋值为空,
                table[i] = null;

                //方法1：重新计算index，然后按照put时候的方法进行放值，此种方法会不停的new 对象会造成效率比较低
                /*K key = oldtable.getKey();
                int index = getIndex(key, newLength);
                newtable[index] = new Node<K, V>(key, oldtable.getValue(), newtable[index]);
                oldtable = oldtable.getNextNode();*/

                //方法2：
                //计算新的index值
                K key = oldtable.getKey();
                int index = getIndex(key, newLength);

                //将以前的nextnode保存下来
                Node<K, V> nextNode = oldtable.getNextNode();

                //将newtable的值赋值在oldtable的nextnode上，如果以前是空，则nextnode也是空
                oldtable.setNextNode(newtable[index]);
                newtable[i] = oldtable;

                //将以前的nextcode赋值给oldtable以便继续遍历
                oldtable = nextNode;
            }

        }
        //3.将新的table赋值回老的table
        table = newtable;
        DEFAULT_INITIAL_CAPACITY = newLength;
        newtable = null;
    }

    /**
     * Size int.
     *
     * @return the int
     */
    public int size() {
        return size;
    }
}

手写栈

代码在 github 上， write-queue 分支

package org.jake.write.queue;

public class SelfQueue {
    private int[] array;
    // 头指针
    private int front;
    //尾指针
    private int rear;

    public SelfQueue(int capacity) {
        this.array = new int[capacity];
    }

    /**
     * 入队
     *
     * @param element 入队的元素
     */
    public void enQueue(int element) throws Exception {
        //循环队列
        if ((rear + 1) % array.length == front) {
            throw new Exception("队列已满！");
        }
        array[rear] = element;
        rear = (rear + 1) % array.length;
    }

    /**
     * 出队
     */
    public int deQueue() throws Exception {
        if (rear == front) {
            throw new Exception("队列已空！");
        }
        int deQueueElement = array[front];
        //循环队列
        front = (front + 1) % array.length;
        return deQueueElement;
    }

    /**
     * 输出队列
     */
    public void output() {
        //循环队列
        for (int i = front; i != rear; i = (i + 1) % array.length) {
            System.out.println(array[i]);
        }
    }
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/jakaBlog/p/11767860.html