Java数据结构

一、线性数据结构

1、Java一维数组的创建

（1）预先定义数组的内存空间

int[] arr = new int[3];　　 // new int[3]是代表创建3个内存地址空间　　 // 地址空间的序号是按照0开始的，也就是说0为1号位置
    arr[1] =2;　//每二个内存地址空间都赋一个值 第二个位置赋值 2
    arr[2] =4;　//第二个内存地址空间赋值为 4
    arr[0] =3;　//第一个内存地址空间赋值为 3//for循环遍历arr每一个数组元素并且打印
    for (int i=0;i<arr.length;i++) {
        System.out.println(arr[i]);
    }

（2)   ArrayList的创建和使用

import java.util.ArrayList;import java.util.LinkedList;public class Case {    public static void main(String[] args){        ArrayList data = new ArrayList();        //add是增加某个元素        data.add(1);        data.add(3);        data.add(2);        data.add(4);        for (int i=0;i< data.size();i++) {            //get是通过索引获取元素            System.out.println(data.get(i));        }        System.out.println("------------------------");            //移除某个索引上的元素        data.remove(2);        for (int i=0;i< data.size();i++) {            System.out.println(data.get(i));        }        System.out.println("------------------------");        /**         * data有1，2，4三个元素         */        　　 //判断ArrayList是否为空            System.out.println(data.isEmpty());            //获取某个元素的索引            System.out.println(data.indexOf(4));    }

ArrayList的内存地址是相邻的，假设动态数组A有3个元素a1,a2,a3.如果a1地址为1，则a2,a3为2，3.所以他的遍历速度很快，获得元素很快，弊端就是插入和删除节点时速度较慢，就比如在1号索引插入数据a4则a4的内存地址为2，那么原先1号地址的a₂以及后面的元素将全部后移。　　

　  (3) LinkedList的创建和使用(基于链表的数据结构)

public static void main(String[] args) {
        //创建链表（import java.util.LinkedList）
        LinkedList<Object> data = new LinkedList<>();
        //add(index,element)增加
        data.add(0,2);
        data.add(3);
        data.add(4);
        data.add(5);
        for(int i=0;i<data.size();i++) {
            System.out.println(data.get(i));
        }
       //判断是否包含元素3
        System.out.println(data.contains(3));
    }

链表数据结构，的内存地址是不连续的具体如下图所示：

 　　　　得益于其内存地址无规律，其链表结构图也从侧面反应了，在某个地方增加节点（删除）其后续节点不需要移动，所以其增删性能优于动态数组。

二、非线性结构

其结构如下图所示：

 　　　　A,B,C称为节点，连接节点之间的线称为边。CDF成为叶节点（因为它们没有字节点），而A为根节点。

常见的树型：二叉树（树的每个节点最多只能有两个子节点）

　　（1）二叉搜索树要求：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 　　　它的左、右子树也分别为二叉排序树。