回过头来打基础，数据结构学习，其一

发表于 | 分类于

非科班出身，数据结构和算法一直算是我的弱项吧，虽然业务能力算是堆得可以。在算法之前，应当学习数据结构吧。要想在程序员这条路上长远走下去，基础的学习必不可少。so,here we are。

数组

数组是常用的一种线性结构。简单来说就是将所有的数据排成一排存放在系统分配的一个内存块上，通过使用特定元素的索引作为数组的下标，可以在常数时间内访问数组元素的这么一个结构；数组是内存中是连续存在的。

数组的优点

  • 简单且易用；
  • 访问元素快（查询操作的时间复杂度为O(1)）；

数组的缺点

  • 大小固定：数组的大小是静态的（在使用前必须制定数组的大小）；
  • 需要分配连续的内存空间：数组初始分配空间时，有时候无法分配能存储整个数组的内存空间，需要动态调整内存大小；
  • 基于位置的插入操作实现复杂：如果要在数组中的给定位置插入元素，那么可能就会需要移动存储在数组中的其他元素，这样才能腾出指定的位置来放插入的新元素；而如果在数组的开始位置插入元素（O(n)），那么这样的移动操作开销就会很大。

实现数组

public class Array<E> { //<>使用泛型封装

private E[] data;
private int size;//有多少个有效元素

/**
 * 构造函数，传入数组的容量capacity构造Array
 * @param capacity
 */
public Array(int capacity){
    data =(E[]) new Object[capacity];
    size=0;
}

//无参数的构造函数，默认容量为10
public Array(){
    this(10);
}

//获取数组中的元素个数
public int getSize(){
    return size;
}

//获取数组的容量
public int getCapacity(){
    return data.length;
}

//返回数组是否为空
public boolean isEmpty(){
    return size==0;
}

public void addLast(E e){
    add(size,e);
}

public void addFirst(E e){
    add(0,e);
}

//在index这个位置插入一个新元素e
public void add(int index,E e){

    if (index < 0 || index > size){
        throw new IllegalArgumentException("AddLast failed.Require index>=0 and index <= size.");
    }

    if (size==data.length){
        resize(2 * data.length);
    }

    //把index后面的元素往后挪
    for (int i=size-1;i>=index;i--){
        data[i+1]=data[i];
    }

    data[index]=e;
    size++;
}

//获取索引的index的元素
public E get(int index){
    if (index < 0 || index > size)
        throw new IllegalArgumentException("AddLast failed.Index is Illegal");
    return data[index];
}

//修改索引的index的元素为e
public void see(int index,E e){
    if (index < 0 || index > size)
        throw new IllegalArgumentException("AddLast failed.Index is Illegal");
    data[index]=e;
}


//查找数组中是否有元素e
public boolean contains(E e){
    for (int i=0;i<size;i++){
        if (data[i].equals(e)){
            return true;
        }
    }
    return false;
}

//查找数组中元素e所在的索引，如果不存在元素e，则返回-1
public int find(E e){
     for (int i=0;i<size;i++){
        if (data[i].equals(e)){
            return i;
        }
    }
    return -1;
}

//删除数组中index位置的元素，并返回删除的元素
public E remove(int index){
    if (index < 0 || index > size)
        throw new IllegalArgumentException("AddLast failed.Index is Illegal");
    E ret=data[index];
    for (int i=index+1;i<size;i++)
        data[i-1]=data[i];
    size--;
    data[size]=null;//loitering objects !=memory leak
    if (size==data.length/4 && data.length/2!=0){
        resize(data.length/2);
    }
    return ret;
}
//从数组中删除第一个元素，并返回删除的元素
public E removeFirst(){
    return  remove(0);
}

//从数组中删除最后一个元素，并返回删除的元素
public E removeLast(){
    return  remove(size-1);
}

//从数组中删除元素e
public void removeElement(E e){
    int index=find(e);
    if (index!=-1){
        remove(index);
    }
}

@Override
public String toString() {
    StringBuilder res = new StringBuilder();
    res.append(String.format("Array:size=%d ,capacity=%d\n", size, data.length));
    res.append('[');
    for (int i = 0; i < size; i++) {
        res.append(data[i]);
        if (i != size) {
            res.append(",");
        }
    }
    res.append(']');
    return res.toString();
}
//数组的容量重置为newCapacity大小
private void resize(int newCapacity) {
    E[] newData=(E[]) new Object[newCapacity];
    for (int i=0;i<size;i++){
        newData[i] = data[i];
    }
    data=newData;
}

}

注意
在remove()方法中，数组缩容的大小条件为size == data.length / 4 && data.length / 2 != 0，这里是为了复杂度抖动。（如在扩容，缩容的条件上反复触发）

栈和队列

有老师说，栈就是递归，我觉得这种说法非常正确。确实，递归就和栈一样，是一种后进先出的数据结构。

什么是栈（LIFO Last In First Out）
栈也是一种线性结构，是一种后进后出的数据结构。栈只能从一端添加元素，也只能从一端取出元素，这个端称为栈顶。相比数组，栈对应的操作是数组的子集。

栈的应用
Undo操作（撤销），括号匹配等。

栈的实现
从栈的结构来看，栈只需要实现这几个操作就可以了。

int getSize();//获取栈中的元素个数
boolean isEmpty();//栈是否为空
void push(E e);//把元素压入栈顶
E pop();//把栈顶的元素弹出
E peek();//看一下栈顶的元素


//使用我们编写的数组来实现栈

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

    Array<E> array;

    public ArrayStack(int capacity){
        array = new Array<E>(capacity);
    }

    public ArrayStack(){
        array = new Array<E>();
    }

    @Override
    public int getSize(){
        return array.getSize();
    }

    @Override
    public boolean isEmpty(){
        return array.isEmpty();
    }

    public int getCapacity(){
        return array.getCapacity();
    }

    @Override
    public void push(E e){
        array.addLast(e);
    }

    @Override
    public E pop(){
        return array.removeLast();
    }

    @Override
    public E peek(){
        return array.getLast();
    }

    @Override
    public String toString(){
        StringBuilder res=new StringBuilder();
        res.append("Stack");
        res.append('[');
        for (int i=0;i<array.getSize();i++){
            res.append(array.get(i));
            if (i!=array.getSize()-1)
                res.append(',');
        }
        res.append("] top");
        return res.toString();
    }
}

什么是队列（FIFO First In First Out）
队列也是一种线性结构，队列只能从一端（队尾）添加元素，只能从另一端（队首）取出元素，队列的操作也是数组的子集。

队列的实现
队列需要实现的方法。

    int getSize();//队列的元素数量
    boolean isEmpty();//队列是否为空
    void enqueue(E e);//把元素入队
    E dequeue();//元素出队
    E getFront();//获取队首的元素

    //同样使用数组来实现
public class ArrayQueue<E> implements Queue<E> {
    private Array<E> array;

    public ArrayQueue(int capacity){
        array = new Array<E>(capacity);
    }

     public ArrayQueue(){
        array = new Array<E>();
    }

    @Override
    public int getSize(){
        return array.getSize();
    }

    @Override
    public boolean isEmpty(){
        return array.isEmpty();
    }

    public int getCapacity(){
        return array.getCapacity();
    }

    @Override
    public void enqueue(E e){
        array.addLast(e);
    }

    @Override
    public E dequeue(){
        return array.removeFirst();
    }

    @Override
    public E getFront(){
        return array.getFirst();
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Queue");
        res.append("front [");
        for (int i = 0; i < array.getSize(); i++) {
            res.append(array.get(i));
            if (i != array.getSize()-1) {
                res.append(",");
            }
        }
        res.append("] tail");
        return res.toString();
    }

}

链表

什么是链表
链表也是一张常用的线性数据结构，是最简单的动态数据结构。这里学习的是单链表，单链表中的每个结点不仅包含值，还包含链接到下一个结点的引用字段。通过这种方式，单链表将所有结点按顺序组织起来。
![单链表示例][1]

链表的优点

  • 真正的动态，不需要维护容量的问题
  • 插入元素时间快（复杂度为O(1)）

对于数组，创建时需要分配一定的内存空间，如果空间不够，则需要开辟一块更大的内存空间，然后依次把原来数组里的元素复制过去，这样会花费大量的时间，以及一定的内存浪费。而对于链表，初始时仅需要分配一个元素的内存空间，添加新的元素也很方便，不需要任何的内存复制和查询分配的操作。

链表的缺点

  • 没有随机访问的能力
  • 链表中额外的指针需要浪费内存

链表有许多不足，最大的问题在于访问某个元素的时间开销问题。数组是随存随取的，即存取其中任一一个元素的时间开销为O(1)，而链表在最差的情况下访问一个元素的时间为O(n)；

链表和数组的简单对比

  • 数组最好用于索引有语意的情况，最大的优点：支持快速查询；
  • 链表不适用于索引有语意的情况，最大的优点：动态；

链表的实现

public class LinkedList<E> {

    private class Node{
        public E e;
        public Node next;

        public Node(E e,Node next){
            this.e=e;
            this.next=next;
        }

        public Node(E e){
            this(e,null);
        }

        public Node(){
            this(null,null);
        }

        @Override
        public String toString(){
            return e.toString();
        }

    }

    private Node dummyHead;
    int size;

    public LinkedList(){
        dummyHead=null;
        size=0;
    }

    //获取链表中的元素个数
    public int getSize(){
        return size;
    }

    //返回链表是否为空
    public boolean isEmpty(){
        return size==0;
    }



    //在链表的index(0-based)位置添加新的元素e
    //在链表中不是一个常用的操作，这里作为练习使用
    public void add(int index,E e) {
        if (index<0 || index>size)
            throw new IllegalArgumentException("add faild,Illegal index");

        Node prev=dummyHead;
        //这个循环在移动prev来寻找index的前一位
        for (int i=0;i<index;i++){
            prev=prev.next;
        }

        prev.next=new Node(e,prev.next);

        size++;

    }



    //在链表头添加新的元素e
    public void addFirst(E e){
        add(0,e);
    }

    public void addLast(E e){
        add(size,e);
    }

    //获得链表的第index(0-based)个位置的元素
    //在链表中不是一个常用的操作，练习用
    public E get(int index){
        if (index<0 || index>size)
            throw new IllegalArgumentException("add failed,Illegal index");

        Node cur=dummyHead.next;
        for (int i=0;i<index;i++){
            cur =cur.next;
        }
        return cur.e;
    }

    //获取链表的第一个元素
    public E getFirst(){
        return get(0);
    }
    //获取链表的最后一个元素
    public E getLast(){
        return get(size-1);
    }

    //修改链表的第index(0-based)个位置的元素e
    //在链表中不是一个常用的操作，练习用
    public void set(int index,E e){
        if (index<0 || index>size)
            throw new IllegalArgumentException("set failed,Illegal index");

        Node cur=dummyHead;
        for (int i=0;i<index;i++){
            cur=cur.next;
        }
        cur.e=e;
    }

    public boolean contains(E e){
        Node cur=dummyHead.next;
        while (cur!=null){
            if (cur.e.equals(e)){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }

    //删除链表的第index(0-based)个位置的元素e
    //在链表中不是一个常用的操作，练习用
    public E remove(int index){
        if (index<0 || index>size)
            throw new IllegalArgumentException("remove failed,Illegal index");

        Node prev=dummyHead;
        for (int i=0;i<index;i++){
            prev=prev.next;
        }

        Node retNode=prev.next;
        prev.next=retNode.next;
        retNode.next=null;
        size--;

        return  retNode.e;
    }

    //从链表中删除第一个元素，返回删除的的元素
    public E removeFirst(){
        return remove(0);
    }

    //从链表中删除最后一个元素，返回删除的的元素
    public E removeLast(){
        return remove(size-1);
    }

    @Override
    public String toString(){
        StringBuilder res=new StringBuilder();

        Node cur=dummyHead;
        while (cur!=null){
            res.append(cur+"->");
            cur=cur.next;
        }
        res.append("NULL");
        return res.toString();
    }
}

链表虚拟头结点的作用
为了屏蔽掉链表头结点的特殊性；
因为头结点是没有前序结点的，所以我们不管是删除还是增加操作都要对头结点进行单独的判断，为了我们编写逻辑的方便，引入了一个虚拟头结点的概念；

线性结构，完。