關(guān)于數(shù)據(jù)結(jié)構(gòu)和算法昆稿， 確實有不少公司在面試的時候會考一些這樣的題， 甚至一些叼鉆的操作數(shù)據(jù)結(jié)構(gòu)的題息拜， 當(dāng)這樣的問題其實在工作中基本上是用不到的.
如果為了迎合這樣的題溉潭， 為了面試而去面試的話，有些得不償失. 畢竟還是有不少公司會務(wù)實一些少欺， 不會去考這類的題目喳瓣， 如果花了太多精力去準(zhǔn)備算法題結(jié)果沒考到，對實際工作也沒有大的實際意義赞别， 那就得不償失了.
我的準(zhǔn)備原則是:
- 基礎(chǔ)概念要清晰畏陕，“Node類的作用”， “Link類只對根節(jié)點進行操作”仿滔， 像這樣的核心概念要清晰.
- 深度和廣度達到下面這個代碼就可以了惠毁， 更偏門一些的題， 能有個大致的實現(xiàn)思路也就可以了.
- 對時間復(fù)雜度的表示法能有個清晰的認識.
在Link類中, 實現(xiàn)添加數(shù)據(jù) add(String data), 查找數(shù)據(jù)是否存在contains(String data), 刪除數(shù)據(jù)remove(String data), 打印所有節(jié)點中封裝的數(shù)據(jù)print().
//節(jié)點類的存在意義在于要封裝一個數(shù)據(jù).
//Node類的實現(xiàn)很多都是通過遞歸調(diào)用來完成的.
class Node {
private String data; //要包裝的數(shù)據(jù)
private Node next; //保存它的下一個節(jié)點的位置
public Node(String data) { //節(jié)點類的功能就是包裝數(shù)據(jù)
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) { //將節(jié)點保存在合適的位置上
if(this.next == null ) { //當(dāng)前節(jié)點之后沒有其他節(jié)點
this.next = newNode;
} else { //當(dāng)前節(jié)點之后還有節(jié)點
this.next.addNode(newNode); //通過遞歸調(diào)用保存新節(jié)點的位置
}
}
public void printNode() {
System.out.printLn(this.data); //輸出當(dāng)前節(jié)點的數(shù)據(jù)
if(this.next != null) { //當(dāng)前節(jié)點后面還有節(jié)點
this.next.printNode(); //也是通過遞歸調(diào)用完成
}
}
public boolean containsNode(String data) {
if(this.data.equals(data)) { //當(dāng)前節(jié)點的數(shù)據(jù)為要查找的數(shù)據(jù)
return true;
} else { // 當(dāng)前節(jié)點的數(shù)據(jù)不是要查找的數(shù)據(jù)崎页， 繼續(xù)向下查找
if (this.next != null) { //當(dāng)前節(jié)點后還有其他的節(jié)點
this.next.containsNode(data);
} else { //當(dāng)前節(jié)點后沒有節(jié)點了.
return false;
}
}
}
public void removeNode(Node previous, String data) {
if(this.data.equals(data)) { //要刪除的就是當(dāng)前節(jié)點
previous.next = this.next; //空出當(dāng)前節(jié)點
} else {
this.next.removeNode(this, data); //還是通過遞歸調(diào)用完成
}
}
}
//鏈表類對外提供的所有API的實現(xiàn)都是通過直接調(diào)用根節(jié)點來完成的.
class Link { // 表示鏈表的操作類鞠绰， 主要就是操作Node類.
private Node root; //將根節(jié)點定義為類中的屬性
public void add(String data) { //設(shè)置要增加的數(shù)據(jù)
if(data == null ) {
return; //如果數(shù)據(jù)為空， 直接返回
}
Node newNode = new Node(data); //將數(shù)據(jù)包裝在節(jié)點中
if(this.root == null) { //現(xiàn)在還沒有根節(jié)點
this.root = newNode; //第一個節(jié)點作為根節(jié)點
} else { //如果根節(jié)點已經(jīng)存在, 則通過Node類指定新創(chuàng)建的節(jié)點的保存位置
this.root.addNode(newNode);
}
}
public void print() {
if(this.root != null ) { //當(dāng)前有節(jié)點有數(shù)據(jù)飒焦，可以輸出鏈表里的所有數(shù)據(jù)
this.root.printNode(); //輸出工作還是交給Node類去做.
}
}
public boolean contains(String data) {
if(data == null || this.root = null) {
return false; //要查詢的數(shù)據(jù)為空洞豁， 或是鏈表中還沒有根節(jié)點的話，就直接返回false了.
}
return this.root.containsNode(data); //交給Node類完成
}
public void remove(String data) {
if(this.contains(data)) { 要刪除的節(jié)點存在
if(this.root.getData().equals(data) { //如果要刪除的是根節(jié)點
this.root = this.root.getNext(); //讓根節(jié)點的下一個節(jié)點為新的根節(jié)點
} else { 交給Node類完成
//從根節(jié)點的下一個節(jié)點開始荒给， 判斷要刪除的節(jié)點
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-數(shù)據(jù)結(jié)構(gòu) - 簡單鏈表
-------DONE.----------
