关于数据结构和算法， 确实有不少公司在面试的时候会考一些这样的题， 甚至一些叼钻的操作数据结构的题， 当这样的问题其实在工作中基本上是用不到的.
如果为了迎合这样的题， 为了面试而去面试的话，有些得不偿失. 毕竟还是有不少公司会务实一些， 不会去考这类的题目， 如果花了太多精力去准备算法题结果没考到，对实际工作也没有大的实际意义， 那就得不偿失了.
我的准备原则是:
- 基础概念要清晰，“Node类的作用”， “Link类只对根节点进行操作”， 像这样的核心概念要清晰.
- 深度和广度达到下面这个代码就可以了， 更偏门一些的题， 能有个大致的实现思路也就可以了.
- 对时间复杂度的表示法能有个清晰的认识.
在Link类中, 实现添加数据 add(String data), 查找数据是否存在contains(String data), 删除数据remove(String data), 打印所有节点中封装的数据print().
//节点类的存在意义在于要封装一个数据.
//Node类的实现很多都是通过递归调用来完成的.
class Node {
private String data; //要包装的数据
private Node next; //保存它的下一个节点的位置
public Node(String data) { //节点类的功能就是包装数据
this.data = data;
}
public void setNext(Node next) {
this.next = next;
}
public Node getNext() {
return this.next;
}
public String getData() {
return this.data;
}
public void addNode(Node newNode) { //将节点保存在合适的位置上
if(this.next == null ) { //当前节点之后没有其他节点
this.next = newNode;
} else { //当前节点之后还有节点
this.next.addNode(newNode); //通过递归调用保存新节点的位置
}
}
public void printNode() {
System.out.printLn(this.data); //输出当前节点的数据
if(this.next != null) { //当前节点后面还有节点
this.next.printNode(); //也是通过递归调用完成
}
}
public boolean containsNode(String data) {
if(this.data.equals(data)) { //当前节点的数据为要查找的数据
return true;
} else { // 当前节点的数据不是要查找的数据， 继续向下查找
if (this.next != null) { //当前节点后还有其他的节点
this.next.containsNode(data);
} else { //当前节点后没有节点了.
return false;
}
}
}
public void removeNode(Node previous, String data) {
if(this.data.equals(data)) { //要删除的就是当前节点
previous.next = this.next; //空出当前节点
} else {
this.next.removeNode(this, data); //还是通过递归调用完成
}
}
}
//链表类对外提供的所有API的实现都是通过直接调用根节点来完成的.
class Link { // 表示链表的操作类， 主要就是操作Node类.
private Node root; //将根节点定义为类中的属性
public void add(String data) { //设置要增加的数据
if(data == null ) {
return; //如果数据为空， 直接返回
}
Node newNode = new Node(data); //将数据包装在节点中
if(this.root == null) { //现在还没有根节点
this.root = newNode; //第一个节点作为根节点
} else { //如果根节点已经存在, 则通过Node类指定新创建的节点的保存位置
this.root.addNode(newNode);
}
}
public void print() {
if(this.root != null ) { //当前有节点有数据，可以输出链表里的所有数据
this.root.printNode(); //输出工作还是交给Node类去做.
}
}
public boolean contains(String data) {
if(data == null || this.root = null) {
return false; //要查询的数据为空， 或是链表中还没有根节点的话，就直接返回false了.
}
return this.root.containsNode(data); //交给Node类完成
}
public void remove(String data) {
if(this.contains(data)) { 要删除的节点存在
if(this.root.getData().equals(data) { //如果要删除的是根节点
this.root = this.root.getNext(); //让根节点的下一个节点为新的根节点
} else { 交给Node类完成
//从根节点的下一个节点开始， 判断要删除的节点
this.root.getNext().removeNode(this.root, data);
}
}
}
}
//测试代码
public class Demo {
public static void main(String args[]) {
Link all = new Link();
all.add("A");
all.add("B");
all.add("C");
all.remove("B");
all.contains("C");
all.print();
System.out.printLn(all.contains("A"));
System.out.printLn(all.contains("X"));
}
}
refer to:
视频讲座
魔乐 java核心 25-数据结构 - 简单链表
-------DONE.----------
