Java 数据结构了解一下

所谓数据结构，就是数据组合在一起并进行管理的方式，这些方式有表、栈和队列、树、图等。数据结构除了储存数据还管理着数据。
算法呢，就是以某种方式得出所需要的一个数据或一组数据。实现方式可能是计算，或者遍历等。

*以上仅为个人理解，有误请指出。

一、线性表

概念：线性表是最基本、最简单、也是最常用的一种数据结构。其中数据元素的排列方式是线性的。

分类：按照元素储存结构可分为顺序表和链式表。

1.1 顺序表

元素的存储空间是连续的。比如数组。

2.2 链表：

元素的存储空间是离散的、单独的，元素之间的逻辑顺序是通过链表中的指针链接次序实现。链表也分为很多种，有单链表、双链表、循环链表，本文暂时分析单链表。

单链表中的数据是以结点来表示，每个结点的构成：元素（数据）+指针（指示后继元素的存储位置），下面来实现单链表。

2.2.1 单链表的创建和遍历
public class LinkList {
    // 2.头结点和当前结点
    public Node<String> head;
    public Node<String> current;

    /**
     *  3.添加新结点
     * @param data 要添加的结点的数据
     */
    public void add(String data){
        if(head == null){// 头结点为null，说明链表中没有元素
            // 创建结点并把新结点赋值给当前结点
            head = new Node<String>(data);
            current = head;
        } else {
            // 创建新节点赋值给当前结点的下一个结点，让表连起来
            current.next = new Node<String>(data);
            // 当指针向后移动一位，保证当前结点指向最新的结点
            // 这样再有新数据就一直向后链接
            current = current.next;
        }
    }

    /**
     * 4.打印单链表中所有结点数据
     * @param node 从该结点开始打印
     */
    public void printLinkList(Node node){
        if(node == null){
            return;
        }
        current = node;
        while (current != null){
            System.out.print(current.data);
            current = current.next;
        }
    }

    // 1.包含两部分 data（数据），next（下一个结点指针）
    class Node<E>{
        E data;
        Node<E> next;

        public Node(E data) {
            this.data = data;
        }
    }
}
  1. 创建结点。LinkList 表示单链表类，内部类 Node 表示单链表的元素。提供构造函数以便创建结点。
  2. 在单链表中创建变量头结点和当前结点，头结点主要用于记录首个结点信息，当前结点用于继续创建后续结点。
  3. 创建结点的函数：
    如果单链表中没有结点，则创建结点传入数据并赋值给头结点。这里头结点作为链表是否为空的重要属性，以及作为遍历单链表所有结点的起始结点。
    如果不为空链表，则创建新结点并赋值给当前的结点的下一个结点，作为连接用。然后将指针向后移动一位指向最新的结点，这样当再添加结点会赋值给最新的结点的 next 保证链接。
  4. 单链表的遍历：遍历的话需要传递某个结点作为参数，并赋值给当前结点，如果链表存在该结点则循环打印结点数据即可。如果想要遍历所有结点数据，就用到变量头结点 head 了，因为它是作为链表的第一个结点存在的，传入 head 就可以遍历所有的结点了。

测试：

public class Test {
    public static void main(String[] args){
        LinkList linkList = new LinkList();
        // 创建 LinkList 并添加数据
        // 这时链表为空，第一个元素会作为 head 保存。
        for (int i = 0; i < 10; i++){
            linkList.add("data"+i+"\n");
        }
        // 这时 head 已经有数据了，执行循环遍历即可
        linkList.printLinkList(linkList.head);
    }
}

结果：

遍历单链表

有关单链表的问题还有很多，参考：

链表面试题Java实现【重要】

相关问题简单实现：

  • 获取单链表长度：遍历之...
/**
 * @return 获取链表长度
 */
public int getLinkListLength(){
    if(head == null){
        return 0;
    }
    int length = 0;
    Node node = head;
    while (node != null){
        length++;
        node = node.next;
    }
    return length;
}
  • 反转一个单链表
/**
 * 反转链表，循环不会栈溢出
 * @param node
 * @return
 */
public Node reverseList(Node node){
    if(node == null || node.next == null){
        return node;
    }
    Node current = node;
    Node next = null;
    Node reverseHead = null;
    while (current != null){
        // 1.记录当前结点的下一个结点用于指针后移
        next = current.next;
        // 4.下一轮循环时，旧的表的下一结点链接到新表头
        current.next = reverseHead;
        // 2.将当前结点赋值给新表头
        reverseHead = current;
        // 3.指针后移
        current = next;
    }
    return reverseHead;
}

这里的思路首先是循环，然后分别记录当前结点、下一个结点和反转后新链表的表头，接着就是循环的赋值：

  1. 记录当前结点的下一个结点，用于赋值给 current 实现指针后移。
  2. 将当前结点赋值给新表头，循环赋值不断替换，这样保证旧链表的最后一个结点是反转后链表的头结点。
  3. 指针后移，因为现在的 next 已经是刚才 current 的下一结点了。
  4. 下一轮循环时，旧的表的下一结点链接到新表头：因为第一轮循环 reverseHead 是 null，所以不用理会。到第二个循环时，这时的 reverseHead 经过第 1 步已经有值且值是初始结点，将 current.next 也就是第三个结点指向初始结点，然后再循环处理到最后实现反转。
  • 查找单链表中间结点
    一种思路是遍历获取链表长度再拿中间，这里记录不允许遍历的情况：
    /**
     * 查找单链表中间
     * @param head
     * @return
     */
    public Node findMidNode(Node head){
        if(head == null){
            return null;
        }
        // 定义两个
        Node first = head;
        Node second = head;
        // 两个同时移动，但是一个走一步另一个走两步
        while (second != null && second.next != null){
            first = first.next;
            second = second.next.next;
        }
        return first;
    }

思路是定义两个结点，起点一样，循环一个走一步一个走两步，这样当走的最快的走不下去时第一个就是中间结点了。

  • 合并两个有序链表，合并后依然有序
    例如：
    链表1：1 > 2 > 3 > 4
    链表2：2 > 3 > 4 > 5
    合并后：1 > 2 > 2 > 3 > 3 > 4 > 4 > 5
/**
 * 合并两个有序链表
 * @param head1 链表1 表头
 * @param head2 链表2 表头
 * @return
 */
public Node mergeList(Node head1,Node head2){
    // 如果两个链表都为 null 返回 null
    if(head1 == null && head2 == null){
        return null;
    }
    // 如果其中一个为 null，返回不为 null 的就是要的表头了
    if(head1 == null){
        return head2;
    }
    if(head2 == null){
        return head1;
    }

    Node head = null;
    Node current = null;
    // 判断首位，确认新表头
    if((int)head1.data < (int)head2.data ){
        head = head1;
        current = head1;
        head1 = head1.next;
    } else {
        head = head2;
        current = head2;
        head2 = head2.next;
    }

    while (head1 != null && head2 != null){
        if((int)head1.data < (int)head2.data){
            current.next = head1; // 循环比较，把较小的值链接到新表后
            current = current.next;// 指针后移
            head1 = head1.next;
        } else {
            current.next = head2;
            current = current.next;
            head2 = head2.next;
        }
    }
    // 经过上面循环，head1 还有值说明 head2 循环完毕
    if(head1 != null){
        // 后面是有序的，所以只要链接到当前结点即可
        current.next = head1;
    }
    // 同理，head1 循环完毕
    if(head2 != null){
        current.next = head2;
    }
    return head;
}

自行理会吧...233333.

二、栈

特点：先进后出（后进先出）。也就是说，保存在栈中的元素会像摞书本一样一个一个压在栈中，取出来的时候会一本一本拿。

栈模型（图片来源网络）

Java Stack 类：

Java Stack

  • push(): 往栈中添加数据
  • pop(): 返回栈顶的值并删除
  • peek(): 返回栈顶的值，但不删除
  • search(Object o): 返回元素 o 最后出现下标

一个简单的基于数组的实现：

public class Stack {
    // 记录栈顶坐标，同时也可依据该值获取栈顶元素
    private int top = -1;
    private Object[] data;

    public Stack(int capacity) throws Exception {
        if(capacity < 0){
            throw new Exception("Illegal capacity:"+capacity);
        }
        data = new Object[capacity];
    }

    public Object push(Object o) throws Exception {
        if(top == data.length - 1){
            throw new Exception("Stack is full!");
        }
        return data[++top] = o;
    }

    public Object pop() throws Exception {
        if(top == -1){
            throw new Exception("Stack is empty!");
        }
        return data[top--];
    }

    public void print(){
        System.out.print("bottom -> top: | ");
        for(int i = 0 ; i <= top ; i++){
            System.out.print(data[i]+" | ");
        }
        System.out.print("\n");
    }
}

一个简单的基于链表的实现：

public class LinkedStack {

    private LinkedList linkedList = new LinkedList();

    public void push(Object o){
        linkedList.addFirst(o);
    }

    public Object pop(){
        return linkedList.removeFirst();
    }

}

栈和队列的面试题Java实现【重要】

三、队列

特点：先进先出 即最先放入的元素最先被取出。元素存放时类似栈，按顺序排列。元素存储时从队尾放入，取出时则先从队头出队。

Queue示意图（Copy）
队列的创建：

一般情况下，队列创建的方式有两种：

  • 基于数组创建（顺序队列）
  • 基于链表创建（链式队列）

一个简单的队列的实现：

public class Queue {

    public Node head;
    public Node current;

    /**
     * 与链表添加数据方式类似
     * @param data 数据
     */
    public void addNode(int data){
        if(head == null){
            head = new Node(data);
            current = head;
        } else {
            current = new Node(data);
            current = current.next;
        }
    }

    /**
     * 出队列永远都是队头的数据
     * @return head 的数据
     * @throws Exception
     */
    public int pop() throws Exception {
        if(head == null){
            throw new Exception("队列为空");
        }
        Node node = head; //要出队的Node
        head = node.next; //指针后移，因为头已经出队
        return node.data;
    }

    class Node{
        Node next;
        int data;
        public Node(int data){
            this.data = data;
        }
    }
}

四、树（多数资料来自百度百科）

  树状图是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
  每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树；

定义：

树（tree）是包含n（n>0）个结点的有穷集，其中：
(1) 每个元素称为结点（node）；
(2) 有一个特定的结点被称为根结点或树根（root）。
(3) 除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。


树
相关概念：
  • 树的高度/深度，结点的层次（Level）：从根开始定义起，根为第一层，根的子结点为第二层。依次类推，如上图的树深度/高度为 4。
  • 森林：m（m>=0）棵互不相交的树的集合。
种类：
  • 无序树：树中任意节点的子结点之间没有顺序关系，可以互换，这种树称为无序树,也称为自由树;
  • 有序树：树中任意节点的子结点之间有顺序关系，这种树称为有序树；
  • 二叉树：每个节点最多含有两个子树的树称为二叉树；
  • 完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
完全二叉树
  • 满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。
各种树
  • 哈夫曼树：给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

二叉树

二叉树的结点：
class TreeNode<E>{
    E data;
    TreeNode left;
    TreeNode right;

    public TreeNode(E data){
        this.data = data;
    }
}
二叉树的创建：
private List<TreeNode> datas;//存储所有的节点
public TreeNode root;//根节点

public BinaryTree(){
}

public void createTree(Object[] objs){
    datas = new ArrayList<>();
    for (Object object : objs) {
        datas.add(new TreeNode(object));
    }
    root=datas.get(0);//将第一个元素作为根节点
    for(int i = 0; i < objs.length/2; i++){
        datas.get(i).left = datas.get(i*2+1);
        if(i*2+2 < datas.size()){// 避免下标越界
            datas.get(i).right = datas.get(i*2+2);
        }
    }
}
二叉树的遍历：

二叉树的遍历方式有很多，如果限制了从左到右的方式，主要可以分为四种：

  1. 前序/先序遍历
    先访问根结点，然后前序遍历左子树，再前序遍历右子树。
//前序/先序遍历
public void preorder(TreeNode<E> root){
    if(root == null){
        return;
    }
    System.out.print(root.data+"");
    preorder(root.left);
    preorder(root.right);
}
  1. 中序遍历
//中序遍历
public void inorder(TreeNode<E> root){
    if(root == null){
        return;
    }
    inorder(root.left);
    System.out.print(root.data+"");
    inorder(root.right);
}
  1. 后序遍历
//后序遍历
public void postorder(TreeNode<E> root) {
    if (root == null){
        return;
    }
    postorder(root.left);
    postorder(root.right);
    System.out.println(root.data + " ");
}

三种遍历方式都用到了递归，从代码上看区别就是打印数据的位置。

二叉树的高度：

同样是利用递归以及左右子结点判断逐渐增加高度。

public int height(TreeNode root) {
    if (root == null)
        return 0;// 递归结束：空树高度为0
    else {
        int i = height(root.left);
        int j = height(root.right);
        return (i < j) ? (j + 1) : (i + 1);
    }
}
二叉树的结点数量：
public int size(TreeNode root) {
    if (root == null) {
        return 0;
    } else {
        return 1 + size(root.left) + size(root.right);
    }
}
二叉树的结点插入：
public String insert(int value) {
    String error = null;

    TreeNode node = new TreeNode(value);
    if (root == null) {
        root = node;
        root.left  = null;
        root.right = null;
    } else {
        TreeNode current = root;
        TreeNode parent = null;
        while (true) {
            if (value < (int)current.data) {
                parent = current;
                current = current.left;
                if (current == null) {
                    parent.left = node;
                    break;
                }
            } else if (value > (int)current.data) {
                parent = current;
                current = current.right;
                if (current == null) {
                    parent.right = node;
                    break;
                }
            } else {
                error = "having same value in binary tree";
                System.out.print(error);
            }
        } // end of while
    }
    return error;
}
二叉树的结点删除：
/**
 * 删除结点
 * @param value
 * @return
 */
public boolean delete(int value) {
    TreeNode current = root;    //需要删除的节点
    TreeNode parent = null;     //需要删除的节点的父节点
    boolean isLeftChild = true;   //需要删除的节点是否父节点的左子树

    while (true) {
        if (value == (int)current.data) {
            break;
        } else if (value < (int)current.data) {
            isLeftChild = true;
            parent = current;
            current = current.left;
        } else {
            isLeftChild = false;
            parent = current;
            current = current.right;
        }

        //找不到需要删除的节点，直接返回
        if (current == null)
            return false;
    }

    //分情况考虑
    //1、需要删除的节点为叶子节点
    if (current.left == null && current.right == null) {
        //如果该叶节点为根节点，将根节点置为null
        if (current == root) {
            root = null;
        } else {
            //如果该叶节点是父节点的左子节点，将父节点的左子节点置为null
            if (isLeftChild) {
                parent.left  = null;
            } else { //如果该叶节点是父节点的右子节点，将父节点的右子节点置为null
                parent.right = null;
            }
        }
    }
    //2、需要删除的节点有一个子节点，且该子节点为左子节点
    else if (current.right == null) {
        //如果该节点为根节点，将根节点的左子节点变为根节点
        if (current == root) {
            root = current.left;
        } else {
            //如果该节点是父节点的左子节点，将该节点的左子节点变为父节点的左子节点
            if (isLeftChild) {
                parent.left = current.left;
            } else {  //如果该节点是父节点的右子节点，将该节点的左子节点变为父节点的右子节点
                parent.right = current.left;
            }
        }
    }
    //2、需要删除的节点有一个子节点，且该子节点为右子节点
    else if (current.left == null) {
        //如果该节点为根节点，将根节点的右子节点变为根节点
        if (current == root) {
            root = current.right;
        } else {
            //如果该节点是父节点的左子节点，将该节点的右子节点变为父节点的左子节点
            if (isLeftChild) {
                parent.left = current.right;
            } else {  //如果该节点是父节点的右子节点，将该节点的右子节点变为父节点的右子节点
                parent.right = current.right;
            }
        }
    }
    //3、需要删除的节点有两个子节点，需要寻找该节点的后续节点替代删除节点
    else {
        TreeNode successor = getSuccessor(current);
        //如果该节点为根节点，将后继节点变为根节点，并将根节点的左子节点变为后继节点的左子节点
        if (current == root) {
            root = successor;
        } else {
            //如果该节点是父节点的左子节点，将该节点的后继节点变为父节点的左子节点
            if (isLeftChild) {
                parent.left = successor;
            } else {  //如果该节点是父节点的右子节点，将该节点的后继节点变为父节点的右子节点
                parent.right = successor;
            }
        }
    }
    current = null;
    return true;
}

/**
 *
 * 得到后继节点，即删除节点的左后代
 */
private TreeNode getSuccessor(TreeNode delNode) {
    TreeNode successor = delNode;
    TreeNode successorParent = null;
    TreeNode current = delNode.right;

    while (current != null) {
        successorParent = successor;
        successor = current;
        current = current.left;
    }

    //如果后继节点不是删除节点的右子节点时，
    if (successor != delNode.right) {
        //要将后继节点的右子节点指向后继结点父节点的左子节点，
        successorParent.left = successor.right;
        //并将删除节点的右子节点指向后继结点的右子节点
        successor.right = delNode.right;
    }
    //任何情况下，都需要将删除节点的左子节点指向后继节点的左子节点
    successor.left = delNode.left;

    return successor;
}
测试：
public static void main(String[] args){

    BinaryTree binTree=new BinaryTree();
    Object[] objs={0,1,2,3,4,5,6,7,8,9};
    binTree.createTree(objs);
    binTree.insert(10);
    binTree.preorder(binTree.root);
//        binTree.inorder(binTree.root);
//        binTree.postorder(binTree.root);
//        System.out.print(binTree.height(binTree.root)+" ");
}

关于二叉树更多资料：

二叉树的java实现
二叉树之Java实现二叉树基本操作

五、图

暂时还没有用到图，等到用到的时候再来复习。

六、排序

有空记得自己实现。

必须知道的八大种排序算法【java实现】（一） 冒泡排序、快速排序

其它比较好的文章：

Android程序员面试会遇到的算法(part 1 关于二叉树的那点事) 附Offer情况
那些年，我们被问到的数据结构

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 214,100评论 6赞 493
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,308评论 3赞 388
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 159,718评论 0赞 349
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,275评论 1赞 287
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,376评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,454评论 1赞 292
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,464评论 3赞 412
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,248评论 0赞 269
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,686评论 1赞 306
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,974评论 2赞 328
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,150评论 1赞 342
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,817评论 4赞 337
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,484评论 3赞 322
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,140评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,374评论 1赞 267
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,012评论 2赞 365
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,041评论 2赞 351