一、常见的数据结构
数组、链表、栈、队列、哈希表、树、图和堆
二、常见数据结构各自的优缺点
数组
优点：访问元素速度快，支持随机访问。
缺点：插入、删除操作效率低，大小固定。
链表
优点：插入、删除操作效率高，动态大小。
缺点：访问速度慢，无法随机访问。
栈
优点：操作简单，先进后出（LIFO）结构，适用于递归问题。
缺点：只能访问栈顶元素，无法遍历。
队列
优点：先进先出（FIFO）结构，适用于任务调度等场景。
缺点：只能访问队头、队尾，无法随机访问。
树
优点：层次结构清晰，快速查找、插入和删除（例如二叉搜索树）。
缺点：可能退化为链表（不平衡时），需要额外的平衡维护。
三、数据结构在Java代码中的书写方式
1.链表类
//链表类
public class Linked {private Node head;private Node tail;private int size;public int size(){return size;}public void add(int a){Node n=new Node(a);if (head==null){//头节点为null，说明整个链表是空的head=n;tail=n;}else {//如果链表不为空，则把新节点添加到尾结点的后面tail.next=n;tail=n;}size++;}public int get (int index){if (index>size-1){throw new RuntimeException("链表长度越界");}if (index<0){throw new RuntimeException("链表长度小于0");}Node n=head;for (int i=0;i<index;i++){n=n.next;}return n.data;}public void delete(int index){Node n=head;if (index==0){head=head.next;n.next=null;size--;return;}for (int i = 0; i < index-1; i++) {n=n.next;}//n2是被删除节点，n是被删除节点的前驱结点Node n2=n.next;//让被删除节点的前驱节点指向被删除节点的后继节点n.next=n2.next;n2.next=null;size--;}public String toString(){StringBuilder str=new StringBuilder();Node n=head;while (n!=null){str.append(n.data);n=n.next;if (n!=null){str.append(" -> ");}}return str.toString();}public static void main(String[] args) {Linked l=new Linked();l.add(1);l.add(2);l.add(3);l.add(4);l.add(5);System.out.println(l);System.out.println(l.get(1));l.delete(3);System.out.println(l);}
}根据以上代码以及原理自行写出链表节点类的代码？
//链表结点类
public class Node {int data;Node next;public Node(int data){this.data=data;}}2.自定义队列类
//自定义队列类
public class MyQueue {private int[] data=new int[10];int index;public void add(int i){data[index]=i;index++;}public int pop(){int v=data[0];for (int i=0;i<index;i++){data[i]=data[i+1];}index--;return v;}public int size(){return index;}
}
public class MyStack {private Linked linked=new Linked();public void add(int i){linked.add(i);}public int pop(){int v = linked.get(linked.size() - 1);linked.delete(linked.size()-1);return v;}public int size(){return linked.size();}
}3.二叉树类
public class Tree {private TreeNode root;public void add(int v){TreeNode node=new TreeNode(v);if (root==null){root=node;}else {//如果要添加的数据小于根节点，则添加到左边add(root,node);
// if(v < root.data){
// TreeNode n = root.left;
// TreeNode parent = root;
// while (n != null){
// if(n.data > v){
// n = n.left;
// parent = parent.left;
// }else {
// n = n.right;
// parent = parent.right;
// }
// }
// if(v < parent.data){
// parent.left = node;
// }else{
// parent.right = node;
// }
// }}}private void add(TreeNode p,TreeNode v){if (v.data<p.data){if (p.left==null){p.left=v;}else {add(p.left,v);}}else {if (p.right==null){p.right=v;}else {add(p.right,v);}}}public void preOrder(){preOrder(root);}private void preOrder(TreeNode n){if (n==null){return;}System.out.print(n.data +"->");preOrder(n.left);preOrder(n.right);}public void midOrder(){midOrder(root);}private void midOrder(TreeNode n){if (n==null){return;}midOrder(n.left);System.out.print(n.data+"->");midOrder(n.right);}public static void main(String[] args) {Tree t=new Tree();t.add(10);t.add(5);t.add(3);t.add(2);t.add(4);t.add(7);t.add(6);t.add(8);t.add(15);t.add(13);t.add(12);t.add(14);t.add(17);t.add(16);t.add(18);t.preOrder();System.out.println();t.midOrder();}
}根据以上代码以及原理自行写出二叉树节点类的代码？
//二叉树结点类
public class TreeNode {int data;TreeNode left;TreeNode right;public TreeNode(int data){this.data=data;}}
