1. 鏈表的基本形式
鏈表主要知識(shí)點(diǎn)
- 此次的內(nèi)容屬于引用部分的實(shí)際應(yīng)用，所以需要依賴兩點(diǎn)：
- 依賴于引用傳遞
- this表示當(dāng)前對(duì)象宪卿。
- 鏈表的實(shí)現(xiàn)基本模式戳玫；
- 開(kāi)發(fā)并且使用可用鏈。
鏈表基本形式
鏈表是一種最為簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)谤碳，它的主要目的是依靠引用關(guān)系來(lái)實(shí)現(xiàn)多個(gè)數(shù)據(jù)的保存溃卡。
范例：定義一個(gè)Node類
- 假設(shè)本次保存的數(shù)據(jù)是String型，同時(shí)擁有下一個(gè)引用蜒简；
//每一個(gè)鏈表實(shí)際上就是有多個(gè)節(jié)點(diǎn)所組成的
class Node {
//定義一個(gè)節(jié)點(diǎn)
private String data; //要保存的數(shù)據(jù)
private Node next; //要保存下一個(gè)節(jié)點(diǎn)
//每一個(gè)Node類對(duì)象都必須保存有相應(yīng)的數(shù)據(jù)
public Node(String data) { //必須有數(shù)據(jù)才有Node
this.data = data;
}
public void setNext(Node next) {
this.next = next;
}
public Node getNext() {
return this.next;
}
public String getData() {
return this.data;
}
}
以上只是一個(gè)專門負(fù)責(zé)保存節(jié)點(diǎn)的類瘸羡，具體怎么保存并不是Node類負(fù)責(zé)，需要由其它的類來(lái)負(fù)責(zé)Node的關(guān)系匹配
范例：使用第一種形式設(shè)置和取出數(shù)據(jù)
public class LinkDemo {
public static void main(String[] args) {
//第一步：準(zhǔn)備出所有數(shù)據(jù)
Node root = new Node("火車頭");
Node n1 = new Node("No1");
Node n2 = new Node("No2");
root.setNext(n1);
n1.setNext(n2);
//第二步：取出所有數(shù)據(jù)
Node currentNode = root; //從根節(jié)點(diǎn)開(kāi)始讀取
while (currentNode != null) {
System.out.println(currentNode.getData());
//將下一個(gè)節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)
currentNode = currentNode.getNext();
}
}
}
實(shí)際以上的操作使用的循環(huán)并不方便搓茬，最好的做法還是應(yīng)該使用遞歸操作完成犹赖。
范例：使用第二種方式設(shè)置和取得數(shù)據(jù)
public class LinkDemo2 {
public static void main(String[] args) {
//第一步：準(zhǔn)備出所有數(shù)據(jù)
Node root = new Node("火車頭");
Node n1 = new Node("No1");
Node n2 = new Node("No2");
root.setNext(n1);
n1.setNext(n2);
print(root);
}
public static void print(Node current) {
if (current == null) {
return ;
}
System.out.println(current.getData());
print(current.getNext());
}
}
由于所有的節(jié)點(diǎn)并不知道具體的操作次數(shù)队他，所以只能用while使用，但是在節(jié)點(diǎn)的操作中峻村，遞歸比while更加的直觀麸折。
疑問(wèn)?整個(gè)代碼實(shí)際上就是完成設(shè)置數(shù)據(jù)和取去數(shù)據(jù)的過(guò)程，為什么需要Node呢?
因?yàn)檎匙颍瑪?shù)據(jù)本身不具備先后的關(guān)系垢啼，所以使用Node類的封裝數(shù)據(jù)，同時(shí)利用Node類來(lái)指向下一個(gè)節(jié)點(diǎn)张肾。
2. 鏈表的基本雛形
通過(guò)分析發(fā)現(xiàn)：
- 用戶在操作的過(guò)程之中完全沒(méi)有必要去Node類是否存在芭析；
- 所有的節(jié)點(diǎn)的引用關(guān)系不應(yīng)該由用戶去處理，應(yīng)該有一個(gè)專門的工具類來(lái)進(jìn)行處理吞瞪。
定義一個(gè)類馁启，使客戶端隱藏所有的鏈表中給出的細(xì)節(jié)操作。
范例：鏈表的基本形式
//每一個(gè)鏈表實(shí)際上就是有多個(gè)節(jié)點(diǎn)所組成的
class Node {
//定義一個(gè)節(jié)點(diǎn)
private String data; //要保存的數(shù)據(jù)
private Node next; //要保存下一個(gè)節(jié)點(diǎn)
//每一個(gè)Node類對(duì)象都必須保存有相應(yīng)的數(shù)據(jù)
public Node(String data) { //必須有數(shù)據(jù)才有Node
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() {
//輸出當(dāng)前節(jié)點(diǎn)數(shù)據(jù)
System.out.println(this.data);
if (this.next != null) {
//輸出下一個(gè)節(jié)點(diǎn)
this.next.printNode();
}
}
}
//對(duì)Node類對(duì)象的關(guān)系處理
class Link {
//根節(jié)點(diǎn)
private Node root;
public void add(String data) {
//為了可以設(shè)置數(shù)據(jù)的先后關(guān)系尸饺，所以將data包裝在一個(gè)Node類對(duì)象
Node newNode = new Node(data);
//保存當(dāng)前數(shù)據(jù)进统，現(xiàn)在還沒(méi)有根節(jié)點(diǎn)
if (this.root == null) {
//將新的節(jié)點(diǎn)設(shè)置為根節(jié)點(diǎn)
this.root = newNode;
}else {
//當(dāng)前的下一個(gè)節(jié)點(diǎn)繼續(xù)保存
this.root.addNode(newNode);
}
}
public void print() {
if (this.root != null) {
//現(xiàn)在存在根節(jié)點(diǎn)
this.root.printNode();
}
}
}
public class LinkDemo3 {
public static void main(String[] args) {
//由這個(gè)類負(fù)責(zé)所有的數(shù)據(jù)操作
Link link = new Link();
link.add("hello"); //存放數(shù)據(jù)
link.add("world"); //存放數(shù)據(jù)
link.add("WWWW"); //存放數(shù)據(jù)
link.print(); //展示數(shù)據(jù)
}
}
鏈表的基本特點(diǎn)：
- 客戶端代碼不實(shí)現(xiàn)Node以及引用關(guān)系的細(xì)節(jié)，只使用Link類中提供的方法浪听；
- Link類的主要功能時(shí)控制Node類對(duì)象的產(chǎn)生和根節(jié)點(diǎn)螟碎；
- Node類主要負(fù)責(zé)數(shù)據(jù)的保存以及引用關(guān)系的分配。
3. 開(kāi)發(fā)可用鏈表
可以使用鏈表實(shí)現(xiàn)數(shù)據(jù)的增加迹栓、修改掉分、刪除、查詢操作
1. 程序基本結(jié)構(gòu)
Node類負(fù)責(zé)所有的節(jié)點(diǎn)數(shù)據(jù)的保存以及節(jié)點(diǎn)關(guān)系的匹配克伊，所以Node類酥郭，不可能單獨(dú)去使用，而以上的代碼里面Node時(shí)可以單獨(dú)使用的愿吹，外部可以榮國(guó)Link類直接操作Node類不从，這樣是沒(méi)有意義的；所以修改代碼犁跪，是Node為內(nèi)部類椿息，只能被Link類使用。
內(nèi)部類可以使用private定義坷衍，這樣內(nèi)部類只能被外部類使用寝优，而且，內(nèi)部類可以方便的與外部類之間進(jìn)行私有屬性的直接訪問(wèn)枫耳。
范例：鏈表的開(kāi)發(fā)結(jié)構(gòu)
class Link { //鏈表類乏矾，外部能夠看見(jiàn)的只有這一個(gè)類
//之所以定義在內(nèi)部，主要是之讓Link類能調(diào)用
private class Node {
private String data;
private Node next;
public Node(String data) {
this.data = data;
}
public void addNode(Node newNode) {
if (this.next == null) {
this.next = newNode;
}else {
this.next.addNode(newNode);
}
}
}
}
//=================以上為內(nèi)部類=====================
2. 數(shù)據(jù)增加 public void add(數(shù)據(jù)類型 變量)
如果要進(jìn)行新數(shù)據(jù)的增加，則應(yīng)該由Link類負(fù)責(zé)節(jié)點(diǎn)對(duì)象的產(chǎn)生钻心，并且由Link類維護(hù)根節(jié)點(diǎn)凄硼，所有的節(jié)點(diǎn)的關(guān)系匹配交給Node類處理。
class Link { //鏈表類扔役，外部能夠看見(jiàn)的只有這一個(gè)類
//之所以定義在內(nèi)部帆喇，主要是之讓Link類能調(diào)用
private class Node {
private String data;
private Node next;
public Node(String data) {
this.data = data;
}
public void addNode(Node newNode) {
if (this.next == null) {
this.next = newNode;
}else {
this.next.addNode(newNode);
}
}
}
//=================以上為內(nèi)部類=====================
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 {
this.root.addNode(newNode);
}
}
}
public class LinkDemo4 {
public static void main(String[] args) {
Link all = new Link();
all.add("hello");
all.add("world");
all.add("null");
}
}
3. 取鏈表元素個(gè)數(shù) public int size()
每個(gè)鏈表都有長(zhǎng)度亿胸，可以直接在Link類里面設(shè)置一個(gè)count屬性，隨后每一次數(shù)據(jù)添加之后预皇，可以進(jìn)行個(gè)數(shù)自增侈玄。
范例：修改Link.java類
class Link { //鏈表類，外部能夠看見(jiàn)的只有這一個(gè)類
private Node root;
//增加一個(gè)count屬性
private int count = 0; //保存元素的個(gè)數(shù)
public void add(String data) {
//判斷鏈表不能為空吟温，但不是所有的鏈表都不許為空
if (data == null) {
return;
}
Node newNode = new Node(data);
if (this.root == null) {
this.root = newNode;
}else {
this.root.addNode(newNode);
}
this.count ++ ; //每一次保存完成后元素個(gè)數(shù)+1
}
public int size() {
return this.count;
}
}
再在Link類里面添加一個(gè)新的方法：size（）
public int size() {
return this.count;
}
此程序中null不會(huì)保存
4. 判斷鏈表是否為空 public boolean isEmpty()
空鏈表的兩種判斷方式：
- 判斷root是否有對(duì)象(是否為null)序仙；
- 判斷保存的數(shù)據(jù)量的值(count)。
范例：判斷是否為空鏈表
public boolean isEmpty() {
return this.count == 0;
}
5. 數(shù)據(jù)查詢 public boolean contains(數(shù)據(jù)類型 變量)
在鏈表中一定會(huì)保存多個(gè)數(shù)據(jù)鲁豪，判斷數(shù)據(jù)存在的方式潘悼，以：String類型為例，循環(huán)查詢鏈表中的內(nèi)容爬橡，并且要與查詢的數(shù)據(jù)進(jìn)行匹配(equals())治唤，如果查找到了返回true，否則返回false糙申。
范例：修改Link.java 類
public boolean contains(String data) {
//現(xiàn)在沒(méi)有要查詢的數(shù)據(jù)宾添，根節(jié)點(diǎn)也不保存數(shù)據(jù)
if (data == null || this.root == null) {
return false;
}
return this.root.containsNode(data);
}
范例：在Node類中增加方法
public boolean containsNode(String data) {
//當(dāng)前節(jié)點(diǎn)數(shù)據(jù)為要查詢的數(shù)據(jù)
if (data.equals(this.data)) {
return true;
} else {
//當(dāng)前節(jié)點(diǎn)不是要查詢的數(shù)據(jù)
//判斷時(shí)候后下一個(gè)節(jié)點(diǎn)
if (this.next != null) {
return this.next.containsNode(data);
} else {
return false;
}
}
}
6. 根據(jù)索引取得數(shù)據(jù) public 數(shù)據(jù)類型 get(int index)
范例：在Link類里面添加一個(gè)foot屬性，表示Node元素編號(hào)
private int foot = 0;
范例：foot每一次查詢都應(yīng)該從頭開(kāi)始
public String get(int index) {
if (index > this.count) {
return null;
} else {
this.foot = 0;
return this.root.getNode(index);
}
}
范例：在Node類實(shí)現(xiàn)getNode()方法柜裸，
public String getNode(int index) {
//使用當(dāng)前的foot內(nèi)容與要查詢的內(nèi)容比較
//foot自增缕陕，目的是為了下次查詢
if (Link.this.foot ++ ==index) { //要查詢的索引
return this.data; //返回當(dāng)前節(jié)點(diǎn)數(shù)據(jù)
} else { //向后查詢
return this.next.getNode(index);
}
}
內(nèi)部類和外部類之間可以方便的進(jìn)行私有屬性的互相訪問(wèn)。
7. 修改指定索引內(nèi)容public void set(int index , 數(shù)據(jù)類型 變量)
修改數(shù)據(jù)和查詢的區(qū)別不大疙挺，查詢的時(shí)候當(dāng)滿足索引值的時(shí)候扛邑，只是進(jìn)行了一個(gè)數(shù)據(jù)的返回，那么此處只需要將數(shù)據(jù)返回改成數(shù)據(jù)的重新賦值即可铐然。
范例：在Link類里面增加set()方法
public void set(int index , String data) {
if (index > this.count) {
return ;
} else {
this.foot = 0;
this.root.setNode(index , data);
}
}
范例：在Node類里面增加setNode方法
public void setNode(int index , String data) {
if (Link.this.foot ++ ==index) {
this.data = data;
} else {
this.next.setNode(index , data);
}
}
8. 數(shù)據(jù)刪除public void remove(數(shù)據(jù)類型 變量)
數(shù)據(jù)刪除分兩種情況：
- 刪除根節(jié)點(diǎn)蔬崩，則root應(yīng)該指向"root.next" ， Like類中處理這種情況
- 要?jiǎng)h除的不是 根節(jié)點(diǎn)锦爵，而是其它的普通節(jié)點(diǎn)舱殿，應(yīng)該在Node類里面處理，所以此處從第二個(gè)節(jié)點(diǎn)開(kāi)始判斷的险掀。
范例：在Node類里增加一個(gè)removeNode()方法沪袭，此方法處理非根節(jié)點(diǎn)的刪除
public void removeNode(Node previous , String data) {
if (data.equals(this.data)) {
previous.next = this.next;
} else {
this.next.removeNode(this , data);
}
}
范例：在Link類里面增加remove()方法和根節(jié)點(diǎn)的判斷
public void remove(String data) {
if (this.contains(data)) { //判斷數(shù)據(jù)是否存在
if (data.equals(this.root.data)) {
this.root = this.root.next;
} else {
this.root.next.removeNode(this.root , data);
}
this.count -- ;
}
}
9. 將鏈表轉(zhuǎn)換為數(shù)組public 數(shù)組類型[] toArray
在任何情況下，不管是什么樣的類，都不可能總理類中使用輸出語(yǔ)句冈绊，只要是想輸出數(shù)據(jù)一定將數(shù)據(jù)返回到調(diào)用處進(jìn)行輸出侠鳄，而由于鏈表屬于動(dòng)態(tài)對(duì)象數(shù)組，所以此處最好的做法是將鏈表以對(duì)象數(shù)組的形式返回死宣。
范例：修改Link類的定義
- 增加一個(gè)返回?cái)?shù)組類型的屬性伟恶，內(nèi)部類和外部類都可以訪問(wèn)
private String[] retArray
- 增加toArray()方法
public String[] toArray() {
if (this.root == null) {
return null;
}
this.foot = 0;
//根據(jù)保存內(nèi)容開(kāi)辟數(shù)據(jù)
this.retArray = new String[this.count];
this.root.toArrayNode();
return this.retArray;
}
}
范例：在Node類里面處理數(shù)組數(shù)據(jù)的保存
public void toArrayNode() {
Link.this.retArray[Link.this.foot++] = this.data;
if (this.next != null) {
this.next.toArrayNode();
}
}
實(shí)現(xiàn)的前提：內(nèi)部類與外部類之間可以直接進(jìn)行私有屬性的訪問(wèn)。
