1 链表(Linked List)

1.1 单项链表(Singly Linked List)

1.1.1 图例

1.1.2 Java实现

public class ListNode {// 保存值int val;// 保存指针ListNode next;// 构造函数们public ListNode() {}public ListNode(int val) {this.val = val;}public ListNode(int val, ListNode next) {this.val = val;this.next = next;}// 重写toString方法方便输出@Overridepublic String toString() {return "ListNode{" +"val=" + val +", next=" + next +'}';}
}

1.1.3 常见方法

1) 测试类，创建单项链表并输出

public class ListNodeTest {public static void main(String[] args) {// 创建节点ListNode node1 = new ListNode(1);ListNode node2 = new ListNode(2);ListNode node3 = new ListNode(3);// 连起来node1.next = node2;node2.next = node3;node3.next = null;// 创建head指向链表头ListNode head;head = node1;System.out.println(head);}
}// 输出：ListNode{val=1, next=ListNode{val=2, next=ListNode{val=3, next=null}}}

1.2 双向链表(Doubly Linked List)

1.2.1 图例

1.2.2 Java实现

public class Node {Node prev;int data;Node next;public Node() {}public Node(int data) {this.data = data;}public Node(Node prev, int data, Node next) {this.prev = prev;this.data = data;this.next = next;}@Overridepublic String toString() {return "Node{" +"prev=" + prev +", data=" + data +", next=" + next +'}';}
}

1.2.3 常见方法

1) 测试类，创建双向链表并输出

public class NodeTest {public static void main(String[] args) {// 创建节点Node node1 = new Node(null, 1, null);Node node2 = new Node(node1, 2, null);Node node3 = new Node(node2, 3, null);Node node4 = new Node(node3, 4, null);// 连起来node1.next = node2;node2.next = node3;node3.next = node4;// 输出双向链表// 定义临时node指向表头Node tmp = node1;while(tmp != null){System.out.println(tmp.data);tmp = tmp.next;}}
}

1.3 循环链表

2 二叉树(Binary tree)

2.1 图例

2.2 Java实现

public class TreeNodeTest {public static void main(String[] args) {// 创建二叉树并输出// 创建节点TreeNode root = new TreeNode(null, 1, null);TreeNode left = new TreeNode(null,2, null);TreeNode right = new TreeNode(null, 3, null);// 连接成树root.left = left;root.right = right;// 输出二叉树// 先序遍历 中序遍历 后序遍历}
}

3 栈(Stack FILO：先进后出)

3.1 图例

3.2 Java实现

可以基于数组或链表来构建

public class Stack {// 数据Object[] data;// 当前栈大小int size;// 初始化栈public Stack(int length) {data = new Object[length];}// 入栈public void push(Object ele){if(size >= data.length){throw new RuntimeException("栈已满");}data[size] = ele;size++;}// 出栈public Object pop(){if(size <= 0){throw new RuntimeException("栈已空");}Object obj = data[size - 1];data[size - 1] = null;size--;return obj;}// 遍历输出栈public void output(){for(int i = size-1; i >= 0; i--){System.out.println(data[i]);}}}

3.3 测试类，创建栈并输出

public class StackTest {public static void main(String[] args) {// 初始化栈Stack s = new Stack(3);// 元素入栈s.push('A');s.push('B');s.push('C');// 超过容量
//        s.push('D');// 输出s.output(); // C B A// 元素出栈s.pop();s.pop();// 输出s.output(); // A}
}

4 队列(Queue FIFO：先进先出)

4.1 图例

4.2 Java实现

public class Queue {// 保存数据Object[] values;// 记录存储的元素个数int size;// 构造函数public Queue(int length) {values = new Object[length];}// 向队列中添加元素public void add(Object ele) {if(size >= values.length){throw new RuntimeException("队列已满 添加失败");}values[size] = ele;size++;}// 从队头删除元素public Object get() {if(size <= 0) {throw new RuntimeException("队列已空  获取失败");}// 取队头元素Object obj = values[0];// do somethingfor(int i = 0; i < size-1; i++){values[i] = values[i+1];}// 最后一个元素置空values[size - 1] = null;size--;return obj;}// 输出队列内容public void output() {for(int i = 0; i < size; i++){System.out.println(values[i]);}}
}

4.3 测试类，创建队列并输出

public class Queue {// 保存数据Object[] values;// 记录存储的元素个数int size;// 构造函数public Queue(int length) {values = new Object[length];}// 向队列中添加元素public void add(Object ele) {if(size >= values.length){throw new RuntimeException("队列已满 添加失败");}values[size] = ele;size++;}// 从队头删除元素public Object get() {if(size <= 0) {throw new RuntimeException("队列已空  获取失败");}// 取队头元素Object obj = values[0];// do somethingfor(int i = 0; i < size-1; i++){values[i] = values[i+1];}// 最后一个元素置空values[size - 1] = null;size--;return obj;}// 输出队列内容public void output() {for(int i = 0; i < size; i++){System.out.println(values[i]);}}
}