数据结构

数据结构指数据的存储、组织方式。主要需要考虑两个方面：节省存储空间，提高操作（增删/查找）效率

有人认为“程序=数据结构 +算法”。

站队链散二红位。

逻辑/物理结构

逻辑结构：是指数据对象中数据元素之间的相互关系。

1. 集合结构：元素除了同属于一个集合外，它们之间没有其他关系
2. 线性结构：元素之间是一对一的关系
3. 树形结构：元素之间是一对多的关系
4. 图形结构：元素之间是多对多的关系

物理结构：指数据在计算机种的存储形式。

1. 顺序存储结构
2. 链式存储结构

线性表

线性表：零个或多个数据元素的有限序列。

线性表的顺序存储结构：指的是用一段地址连续的存储单元依次存储线性表的数据元素。

线性表的链式存储结构：用一组任意的存储单元存储线性表的数据元素，存储单元可以是连续的，也可以是不连续的。

栈与队列

栈：限定仅在表尾进行插入和删除操作的线性表

1. 把允许插入和删除的一端成为栈顶，另一端称为栈底
2. 栈又称为先进后出/后进先出的线性表

队列：只允许在一端进行插入操作，而在另一端进行删除操作的线性表

1. 允许插入的端称为队尾，允许删除的一端称为队头
2. 队列又称为先进先出的线性表

栈的Java实现

/**
 * 数组实现栈
 * @param <T>
 */
class Mystack1<T> {
    //实现栈的数组
    private Object[] stack;
    //数组大小
    private int size;

    Mystack1() {
        stack = new Object[10];//初始容量为10
    }

    //判断是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    //返回栈顶元素
    public T peek() {
        T t = null;
        if (size > 0)
            t = (T) stack[size - 1];
        return t;
    }

    public void push(T t) {
        expandCapacity(size + 1);
        stack[size] = t;
        size++;
    }

    //出栈
    public T pop() {
        T t = peek();
        if (size > 0) {
            stack[size - 1] = null;
            size--;
        }
        return t;
    }

    //扩大容量
    public void expandCapacity(int size) {
        int len = stack.length;
        if (size > len) {
            size = size * 3 / 2 + 1;//每次扩大50%
            stack = Arrays.copyOf(stack, size);
        }
    }
}

/**
 * 链表实现栈
 *
 * @param <T>
 */
class Mystack2<T> {
    //定义链表
    class Node<T> {
        private T t;
        private Node next;
    }
 
    private Node<T> head;
 
    //构造函数初始化头指针
    Mystack2() {
        head = null;
    }
 
    //入栈
    public void push(T t) {
        if (t == null) {
            throw new NullPointerException("参数不能为空");
        }
        if (head == null) {
            head = new Node<T>();
            head.t = t;
            head.next = null;
        } else {
            Node<T> temp = head;
            head = new Node<>();
            head.t = t;
            head.next = temp;
        }
    }
 
    //出栈
    public T pop() {
        T t = head.t;
        head = head.next;
        return t;
    }
 
    //栈顶元素
    public T peek() {
        T t = head.t;
        return t;
    }
 
    //栈空
    public boolean isEmpty() {
        if (head == null)
            return true;
        else
            return false;
    }
}

队列的Java实现

public class ArrayQueue {

    private String [] items;  //定义数组
    private int n = 0;           //数组大小
    private int head = 0;     //表示队头下标
    private int tail = 0;        //表示队尾下标

    //申请一个大小为capacity的数组
    public ArrayQueue(int capacity) {
        this.n = capacity;
        this.items = new String[capacity];  //初始化数组
    }

    public boolean enQueue(String item) {
        if (tail == n) {  //队列已经满了
            return false;
        }
        items[tail] = item;
        tail++;
        return true;
    }

    public String deQueue() {
        if (head == tail) {   //队列为空
            return null;
        }
        String item = items[head];
        head++;
        return item;
    }

}

单向链表的Java实现

/**
* 单向链表
* 定义链表上的节点
*/
public class Link {
   public int data;//节点的内容
   public Link next;//下一个节点

   //初始化
   public Link(int data) {
       this.data = data;
       this.next = null;
   }

   //打印节点内容
   public void displayLink(){
       System.out.println("{" + data + "}");
   }
}

/**
 * 单向链表
 */
public class LinkedList {
    private Link first;//第一个节点
    private int nElem;//链表中节点数量

    public LinkedList(){
        first = null;
        nElem = 0;
    }


    //添加头结点
    public void insertFirst(int value){
        Link newLink = new Link(value);
        newLink.next = first;//newLink-->old first
        first = newLink;//first-->newLink
        nElem ++;
    }

    //删除头节点
    public Link deleteFirst(){
        if(isEmpty()){
            System.out.println("链表为空");
            return null;
        }
        Link temp = first;
        first = first.next;
        nElem --;
        return temp;
    }

    /************************************************************
     ***下面是有序链表的插入***
     ***这样简单排序就可以用链表来实现，复杂度为O(N)
     ***定义一个方法，传入一个数组，
     ***在方法内，遍历数组并调用insert方法就可以将数组中的数据排好序
     ***********************************************************/
    public void insert(int value){
        Link newLink = new Link(value);//要插入的Link节点
        Link previous = null;//前一个link节点
        Link current = first;//因为是有序链表，从第一个开始
        while(current != null && value > current.data){//当前link不是空，插入的数据大于当前link值
            previous = current;//记录当前为前一个link节点
            current = current.next;//当前link向下找
        }
        if(previous == null){//前一个为null证明只有没有插入link节点，直接插入就行
            first = newLink;
        }else {
            previous.next = newLink;//插入这个link在小于value的link下，后边link为当前节点
        }
        newLink.next = current;//当前节点
        nElem ++;//有序链表长度+1
    }

    //查找特定的节点
    public Link find(int value){
        Link current = first;//从第一个开始查找
        while(current.data != value){
            if(current.next == null){//下一个为空
                return null;
            }else{
                current = current.next;//查找下一个节点
            }
        }
        return current;
    }

    //删除特定的节点
    public Link delete(int value){
        Link current = first;
        Link previous = first;//记录上一个Link,因为要删除节点，节点的指向要发生变化
        while(current.data != value){
            if(current.next == null){
                return null;
            }
            previous = current;
            current = current.next;
        }
        if(current == first){//如要要删除的是第一个
            first = first.next;
        }else{
            previous.next = current.next;//删除link的上一个指向为当前link的下一个link
        }
        nElem --;
        return current;
    }

    //查看链表中的数据
    public void displayList(){
        if(isEmpty()){//为空直接返回
            System.out.println("链表为空！");
            return;
        }
        Link current = first;
        while(current != null){
            current.displayLink();//调用link中的方法，打印当前link的值
            current = current.next;
        }
        System.out.println(" ");
    }

    //链表是否为空
    public boolean isEmpty(){
        return (first == null);
    }

    //链表中节点个数
    public int size(){
        return nElem;
    }
}

双向链表的Java实现

/**
 * 双向链表中的node
 */
public class Node {
    public long data;//当前node的数据值
    public Node next;//后一个node
    public Node previous;//前一个node

    public Node(long value) {
        this.data = value;
        this.next = null;
        this.previous = null;
    }

    //打印节点中node值
    public void displayLink(){
        System.out.print(data + " ");
    }
}

/**
 * 双向链表的具体实现
 */
public class DoubleLinkedList {
    private Node first;//头节点
    private Node last;//尾节点
    private int size;//链表长度

    public DoubleLinkedList() {
        this.first = null;
        this.last = null;
        this.size = 0;
    }

    //链表大小
    public int size(){
        return size;
    }

    //链表是否为空
    public boolean isEmpty(){
        return (first == null);
    }

    //插入头节点
    public void insertFirst(long value){
        Node newLink = new Node(value);
        if(isEmpty()){
            last = newLink;
        }else {
            //前first的node赋值为newLink
            first.previous = newLink;//newLink <-- oldFirst.previous
            //newLink的下一个node为first
            newLink.next = first;//newLink.next --> first
        }
        first = newLink;//first --> newLink//第一个赋值为新插入的
        size ++;
    }

    //插入尾节点
    public void insertLast(long value){
        Node newLink = new Node(value);
        if(isEmpty()){
            first = newLink;
        }else{
            last.next = newLink;
            newLink.previous = last;
        }
        last = newLink;//最后一个赋值为新插入的
        size ++;
    }

    //删除头节点
    public Node deleteFirst(){
        if(first == null){
            System.out.println("链表为空");
            return null;
        }
        Node temp = first;
        if(first.next == null){//如果只有一个节点
            last = null;
        }else{
            first.next.previous = null;//就是first的下一个node的前指针为空
        }
        first = first.next;//第一个为第一个的下一个
        size --;
        return temp;
    }

    //删除尾节点
    public Node deleteLast(){
        if(last == null){//最后一个节点为空，证明没有
            System.out.println("链表为空");
            return null;
        }
        Node temp = last;//暂存要删除的最后一个
        if(last.previous == null){//只有一个节点
            first = null;
        }else{
            last.previous.next = null;//last的前一个的next为null
        }
        last = last.previous;
        size --;
        return temp;
    }

    //在key后面插入值为value的新节点
    public boolean insertAfter(long key,long value){
        Node current = first;//从第一个开始
        while(current.data != key){//对比传入的date
            current = current.next;//下一个
            if(current == null){//如果下一个为空，就是最后一个
                System.out.println("不存在值为" + value + "的节点！");
                return false;
            }
        }
        if(current == last){//当前值为最后一个
            insertLast(value);
        }else{
            Node newLink = new Node(value);//要插入的节点
            newLink.next = current.next;//插入节点的下一个为匹配节点的下一个
            current.next.previous = newLink;//匹配节点的前一个为新加入的节点
            newLink.previous = current;//插入的前一个为匹配节点
            current.next = newLink;//匹配节点的后一个节点为新加入的节点
            size ++;
        }
        return true;//插入成功
    }

    //删除指定位置的节点
    public Node deleteNode(long key){
        Node current = first;//当前节点为第一个节点
        while(current.data != key){
            current = current.next;
            if(current == null){
                System.out.println("不存在该节点");
                return null;
            }
        }
        if(current == first){//如果匹配的是第一个
            deleteFirst();
        }else if(current == last){
            deleteLast();//匹配的是最后一个
        }else{
            current.previous.next = current.next;//当前节点的前一个的后一个为 当前的后一个
            current.next.previous = current.previous;//当前节点的后一个的前一个为 当前的前一个
            size --;
        }
        return current;
    }

    //从头到尾遍历链表
    public void displayForward(){
        System.out.println("List(first --> last):");
        System.out.print("[");
        Node current = first;
        while(current != null){
            current.displayLink();//调用节点的显示方法
            current = current.next;
        }
        System.out.println("]");
    }

    //从尾到头遍历链表
    public void displayBackward(){
        System.out.println("List(last --> first)");
        System.out.print("[");
        Node current = last;
        while(current != null){
            current.displayLink();
            current = current.previous;
        }
        System.out.println("]");
    }

}

散列表（Hash表）

散列表（Hash Table，也叫作哈希表）是根据数据的关键码值 （Key-Value对）对数据进行存取的数据结构。散列表通过映射函数把 关键码值映射到表中的一个位置来加快查找。这个映射函数叫作散列函数，存放记录的数组叫作散列表。

Hash主要用于用信息安全加密和快速查询的应用场景。

◎ 信息安全：Hash主要被用于信息安全领域的加密算法中，它把 一些不同长度的信息转化成杂乱的 128 位编码，这些编码的值叫作Hash值。

◎ 快速查找：散列表，又叫作散列，是一种更加快捷的查找技 术。基于列表集合查找的一般做法是从集合中拿出一个元素，看它是 否与当前数据相等，如果不相等，则缩小范围，继续查找。而散列表 是完全另外一种思路，在知道key值以后，就可以直接计算这个元素在集合中的位置，不需要一次又一次的遍历查找。

Hash函数的输入与输出是多对一的关系。

树

树是一种为了实现快速查找的数据结构。

树是n（n>=0）个节点的有限集。父节点与子节点是一堆多的关系，子节点与父节点是多对一的关系。

节点拥有的子树数称为节点的度。度为0的节点称之为叶节点或终端节点。

节点的层次（Level）从根节点开始定义，根为第一层，根的孩子为第二层。树中节点的最大层次称为树的深度或高度。

二叉树

父节点，最多只能有两个子节点的树，称为二叉树。

1. 左节点和又节点是有顺序的。
2. 没有子节点，或者只有一颗子节点是可以的。

B树

所有的树极其变种都是为了提高查找效率。

什么是B树、B+树 (opens new window)

图

图表示元素与元素之间是多对多的关系。