祎夏

2021-01-24 11:43 已编辑 Java

关注

Java数据结构总结

https://www.jianshu.com/p/8e54797ec3e0

Java数据结构

1、数组

数组是一种连续存储线性结构，元素类型相同，大小相等，数组是多维的，通过使用整型索引值来访问他们的元素，数组尺寸不能改变。

数组的优点

存取速度快

数组的缺点

实现必须知道数组的长度
插入删除元素很慢
空间通常是由限制的
需要大块联系的内存块
插入删除元素的效率很低。

2、链表

n个节点离散分配，彼此通过指针相连，每个节点只有一个前驱节点，每个节点只有一个后续节点，首节点没有前驱节点，尾节点没有后续节点。

确定一个链表我们只需要头指针，通过头指针就可以把整个链表都能推出来。

头结点不存储数据。

图片说明

链表的优点

空间没有限制
插入删除元素很快

链表的缺点

存取速度很慢

链表的细分

单向链表：一个节点指向下一个节点。
双向链表：一个节点有两个指针域，一个指向前一个元素，一个指向后一个元素。
循环链表：能通过任何一个节点找到其他所有的节点，将两种（双向、单向）链表的最后一个节点指向第一个节点从而实现循环。

注意：操作链表要时刻记住的是：节点中指针指向的就是另一个节点！

Java实现链表

数据域、指针域

public class Node {
    // 数据域
    public int val;
    // 指针域，指向下一个节点
    public Node next;

    public Node(int val) {
        this.val = val;
    }
}

相关算法

插入节点
遍历
查找
清空
销毁
求长度
排序
删除节点
去重

创建节点&增加节点

/*
创建头结点：Node head = new Node(val);
然后找到尾结点进行插入
*/
public static void addNode(int val, Node head) {
    Node newNode = new Node(val);
    Node tmp = head;
    while(tmp.next != null) {
        tmp = tmp.next;
    }
    tmp.next = newNode;
}

遍历链表

/*
遍历链表中的数据
*/
public static void traverse(Node head) {
    Node tmp = head.next;
    while(tmp != null) {
        System.out.println("链表数据：" + tmp.data);
        tmp = tmp.next;
    }
}

3、栈和队列

栈

我们将栈可以看成一个放光盘的箱子，箱口跟光盘一样大。
往箱子里面放东西叫入栈。
从箱子里面取东西叫出栈。
箱子的底部叫做栈底。
箱子的顶部叫做栈顶。
先进后出，后进先出。

图片说明

Java实现栈

使用数组实现的叫静态链
使用链表实现的叫动态链

// 栈对象
public class Stack {
    public Node stackTop;
    public Node stackBottom;

    public Stack() {}

    public Stack(Node stackTop, Node stackBottom) {
        this.stackTop = stackTop;
        this.stackBottom = stackBottom;
    }
}

进栈操作

// 进栈
public static void pushStack(Stack stack, int value) {
    Node newNode = new Node(value);
    newNode.next = stack.stackTop;
    stack.stackTop = newNode;
}

遍历栈

// 只要栈顶元素的指针不指向栈底，那么就一直输出遍历结果
public static void traverse(Stack stack) {
    Node stackTop = stack.stackTop;
    while(stackTop != stack.stackBottom) {
        System.out.println("栈数据：" + stackTop.data);
        stackTop = stackTop.next;
    }
}

出栈操作

/*
在出栈之前看看该栈帧是否为空，不为空才出栈
将栈顶的元素的指针（指向下一个节点）赋值给栈顶指针（完成出栈）
*/
public static void popStack(Stack stack) {
    if(stack.stackTop != stack.stackBottom) {
        Node top = stack.stackTop;
        stack.stackTop = top.next;
        System.out.println("栈数据：" + top.val);
    }
}

队列

队列非常简单，头出尾进。
先进先出，后进后出。

图片说明

使用数组实现的叫静态队列
使用链表实现的叫动态队列

Java实现队列

public class Queue<E> {
    private Object[] data = null;
    // 队列容量
    private int maxSize;
    // 队列头，允许删除
    private int front;
    // 队列尾，允许插入
    private int rear;

    public Queue() {
        this(10);
    }

    public Queue(int initialSize) {
        if(initialSize >= 0) {
            this.maxSize = initialSize;
            data = new Object[initialSize];
            front = rear = 0;
        } else {
            throw new RunntimeException("初始化大小不能小于0：" + initialSize);
        }
    }

    // 判空
    public boolean empty() {
        return rear == front ? true : false;
    }

    // 入队
    public boolean add(E e) {
        if(rear = maxSize) {
            throw new RuntimeException("队列已满，无法插入新的元素！");
        } else {
            data[rear++] = e;
            return true;
        }
    }

    // 出队
    public E poll() {
        if(empty()) {
            throw new RuntimeException("空队列异常！");
        } else {
            // 保留队列的front端的元素的值
            E value = (E)data[front];
            // 释放队列的front端的元素
            data[front++] = null;
            return value;
        }
    }

    // 队列长度
    public int length() {
        return rear - front;
    }

    public static void traverseQueue(Queue queue) {
        int i = queue.front;
        while(i != queue.rear) {
            System.out.println("队列值：" + queue.data[i]);
            i = (i + 1) % queue.data.length;
        }
    }
}

4、二叉树

树是一种非线性的数据结构，相对于线性的数据结构（链表、数组）而言，树的平均运行时间更短（往往与树相关的排序时间复杂度都不会高）

图片说明

现实中的树是有很多个分支的，分支下又有很多个分支，如果在程序中实现这个会非常麻烦。因为本来树本来就是非线性的，而我们计算机是线性存储的，太过复杂的话无法设计出来。

因此，就有了简单又经常用的二叉树，顾名思义，就是每个分支对多有两个的树。

一棵树至少会有一个节点（根节点）
树由节点组成，每个节点的数据结构包括一个数据和两个分叉

图片说明

Java实现二叉树

// 首先，使用Java类定义节点
public class TreeNode {
    private int value;
    private TreeNode leftNode;
    private TreeNode rightNode;
    public TreeNode (int value) {
        this.value = value;
    }
    // getter&setter
}

目标实现如下图的树

图片说明
第一步：创建5个节点

TreeNode treeNode1 = new TreeNode(10);
TreeNode treeNode2 = new TreeNode(9);
TreeNode treeNode3 = new TreeNode(20);
TreeNode treeNode4 = new TreeNode(15);
TreeNode treeNode5 = new TreeNode(35);

第二步：连接节点

treeNode1.setLeftNode(treeNode2);
treeNode1.setRightNode(treeNode3);
treeNode3.setLeftNode(treeNode4);
treeNode3.setRightNode(treeNode5);

遍历二叉树

二叉树遍历有三种方式：

中序遍历：先访问根节点，然后访问左节点，最后访问右节点（根 --> 左 --> 右）
先序遍历：先访问左节点，然后访问根节点，最后访问右节点（左 --> 根 --> 右）
后序遍历：先访问左节点，然后访问右节点，最后访问根节点（左 --> 右 --> 根）

中序遍历

public static void inTraverseBTree(TreeNode rootTreeNode) {
    if(rootTreeNode != null) {
        System.out.println(rootTreeNode.getValue());
        inTraverseBTree(rootTreeNode.getLeftNode());
        inTraverseBTree(rootTreeNode.getRightNode());
    }
}

考点

查找树的深度
查找最大值
查找树节点的数量

5、堆和堆栈

堆内存用来存放由new创建的对象和数组。
在堆中分配的内存，由Java虚拟机的垃圾回收器来管理。
“堆栈”就是“栈”，称呼不同而已。
栈的优势是，存取速度比堆要快，仅此于直接位于CPU中的寄存器。但缺点是，存在栈中的数据大小和生存期必须是确定的，缺乏灵活性。另外，栈数据可以共享。
堆的优势是可以动态地分配内存大小，生存期也不必事先告诉编译器，java的垃圾回收器会自动收走这些不再使用的数据。但缺点是，由于要在运行时动态分配内存，存取速度较慢。