Java 面试常用的数据结构

面试常用的数据结构

面试时数据结构应该算是必问的内容, 今天准备了两个更常问的数据结构,链表和二叉树的实现

链表 (线性链表)

我们知道线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻,因此可以随机存取表中任一元素,它的存储位置也用一个简单,直观的公式来表示. 然而,从另一方面来看这个特点铸成的弱点: 在插入或删除操作时,需移动大量元素. 于是就引进了链表: 不要求逻辑上相邻的元素在物理位置上也相邻,但是失去了随机存取的特点.

上代码:

// 链表的实现
public class Test {
    public static void main(String[] args) {
        NodeManager nodeManager = new NodeManager();
        nodeManager.addNode("找");
        nodeManager.addNode("到");
        nodeManager.addNode("一");
        nodeManager.addNode("个");
        nodeManager.addNode("好");
        nodeManager.addNode("工");
        nodeManager.addNode("作");
        nodeManager.delNode("好");
        nodeManager.print();
    }
}
//节点管理类
class NodeManager {

    private Node root;//根节点

    //添加节点
    public void addNode(String data) {
        if (root == null) {
            root = new Node(data);
        } else {
            root.addNode(data);
        }
    }
    //删除节点
    public void delNode (String data) {
        if (root.data.equals(data)){
            root = root.next;
        } else {
            root.delNode(data);
        }
    }
    //打印节点
    public void print() {
        if (root != null) {
            System.out.print(root.data + " ->");
            root.print();
        }
    }



    // 节点类
    class Node {
        private String data;//数据源
        private Node next;//指针域

        public Node(String data) {
            this.data = data;
        }
        //添加方法
        public void addNode(String data) {
            if (this.next == null) {
                this.next = new Node(data);
            } else {
                this.next.addNode(data);
            }
        }
        //删除方法
        public void delNode(String name) {
            if (this.next != null) {
                if (this.next.data.equals(name)) {
                    this.next = this.next.next;
                } else {
                    this.next.delNode(name);
                }
            }
        }
        //打印方法
        public void print() {
            if (this.next != null) {
                System.out.print(this.next.data + "->");
                this.next.print();
            }
        }
    }
}

二叉树

是另一种树型结构, 它的特点是每个结点至多只有两颗子树(即二叉树中不存在度大于2的结点), 并且,二叉树的子树有左右之分, 其次不能任意颠倒.

// 二叉树数据结构的实现
public class Test {
    public static void main(String[] args) {
        BinaryTreeManger binaryTreeManger = new BinaryTreeManger();

        binaryTreeManger.add(1);
        binaryTreeManger.add(3);
        binaryTreeManger.add(4);
        binaryTreeManger.add(8);
        binaryTreeManger.add(6);
        binaryTreeManger.print();
    }
}

class BinaryTreeManger{

    private Node root;//根节点

    public void add(int data) {
        if (root == null) {
            root = new Node(data);
        } else {
            root.addNode(data);
        }
    }
    public void print() {
        root.print();
    }
    class Node{
        private int data;
        private Node left; //左子树
        private Node right; //右子树

        public Node(int data) {
            this.data = data;
        }
        //添加节点
        public void addNode(int data) {
            //首先判断大小，来决定将data放在那个子树上
            if (data > this.data){//当前数据较大，放在右子树
                if (this.right == null) {
                    this.right = new Node(data);
                } else {
                    this.right.addNode(data);
                }
            } else { //较小放在左子树上
                if (this.left == null) {
                    this.left = new Node(data);
                } else {
                    this.left.addNode(data);
                }

            }

        }
        //中序遍历 左 -> 根 -> 右
        public void print() {
            if (this.left != null) {
                this.left.print();
            }
            System.out.print(data);
            if (this.right != null) {
                this.right.print();
            }
        }
    }
}