Java面接でよく使われるデータ構造

面接でよく使われるデータ構造
面接時のデータ構造は必須の内容であるべきで、今日はもっとよく聞くデータ構造、チェーンテーブル、ツリーの実現を2つ用意しました.
チェーンテーブル
線形テーブルの順序記憶構造の特徴は、論理関係において隣接する2つの要素が物理的位置においても隣接することであることを知っているので、テーブルのいずれかの要素にランダムにアクセスすることができ、その記憶位置も簡単で直感的な式で表すことができる.しかし、この特徴の弱点は、挿入や削除操作時に大量の要素を移動することである.そこでチェーンテーブルを導入する:論理的に隣接する要素が物理的な位置でも隣接することを要求しないが、ランダムアクセスの特徴を失った.
上のコード:

//      
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本の子木(すなわち、二叉木には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();
            }
        }
    }
}