Java 實現自定義鏈表

Java 實現自定義鏈表
節點類 Node.java
操作功能類 Link.java
App.java
節點類 Node.java
public class Node {
/ 當前節點的數據*/
private String data;
/* 如果當前節點是首/尾節點 NULL 或者是 下一個節點的實例/
private Node next;
public Node(final String data) {
this.data = data;
}
public void setNext(final Node next) {
this.next = next;
}
public Node getNext() {
return this.next;
}
public String getData() {
return this.data;
}
public void addNode(final 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 containNode(final String data) {
/ 比對當前節點數據是否相同*/
if (this.data.equals(data)) {
return true;
} else {
if (this.next != null) {
return this.next.containNode(data);
} else {
return false;
}
}
}
public void removeNode(final Node previous, final String data) {
/ 比對當前節點數據是否和將要刪除的數據相同*/
if (this.data.equals(data)) {
/* 數據相同的前提下 把下一個節點覆蓋到上一個節點的 next/
previous.next = this.next;
} else {
this.next.removeNode(this, data);
}
}
}
操作功能類 Link.java
public class Link {
private Node root;
public void add(final String data) {
if (data == null || this.contains(data)) {
return;
}
Node newNode = new Node(data);
if (this.root == null) {
this.root = newNode;
} else {
this.root.addNode(newNode);
}
}
public void print() {
if (this.root != null) {
this.root.printNode();
}
}
public boolean contains(final String data) {
if (data == null || this.root == null) {
return false;
}
return this.root.containNode(data);
}
public void remove(final String data) {
/ 1. 首先判斷是否有相同數據節點*/
if (this.contains(data)) {
/ 2. 將要刪除的數據和當前根節點數據節點相同的話 把下一個節點覆蓋到根節點*/
if (this.root.getData().equals(data)) {
this.root = this.root.getNext();
} else {
/* 通過當前根節點和將要刪除的數據, 刪除節點/
this.root.getNext().removeNode(this.root , data);
}
}
}
}
App.java
public class App {
public static void main(String[] args) {
final Link list = new Link();
list.add("饅頭");
list.add("豆漿");
list.add("茶葉蛋");
list.add("包子");
list.add("麻花");
list.add("豆漿");
/ 刪除*/
list.remove("包子");
list.remove("豆漿");
/* 打印/
list.print();
/* 查詢/
System.out.println(list.contains("饅頭"));
System.out.println(list.contains("豆漿"));
}
}
結果：

饅頭
茶葉蛋
麻花
true
false
1.入門級
首先實現一個節點類：
package jimo.love;
public 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 data;
}
public void setData(String data) {
this.data = data;
}
}
然后在主方法中生成節點，完成連接關系，并打印出來，看代碼有解釋：
package jimo.love;
public class Test {
public static void main(String[] args) {
//1.準備所有數據
Node head = new Node("頭節點");
Node n1 = new Node("n1");
Node n2 = new Node("n2");
head.setNext(n1);
n1.setNext(n2);
//2.取出所有數據
//方法一：
Node curNode = head;
while(curNode!=null){
System.out.println(curNode.getData());
curNode = curNode.getNext();
}
//方法二,遞歸方式：
print(head);
}
//采用遞歸方式
public static void print(Node curNode){
if(curNode==null){
return ;
}
System.out.println(curNode.getData());
print(curNode.getNext());
}
}
代碼中用了兩種方式取數據，看執行結果：
1
可以看到Main方法里寫的東西太多了，還要設置數據，輸出數據。
但面向對象的思想讓我們不需要關注太多的東西和具體的實現。
所以我們需要ThinkMarkets返傭www.kaifx.cn/broker/thinkmarkets.html一個工具類，我們只關注存數據和取數據，并不關心怎么存，怎么取。
2.中級
我們增加一個Link類用于業務操作：
public class Link {
private Node head;
public void add(String data){
Node newNode = new Node(data);
if(this.head==null){
this.head = newNode;//頭節點
}else{
//頭插法
// newNode.setNext(this.head.getNext());
// this.head.setNext(newNode);
//尾插法
this.head.addNode(newNode);
}
}
public void print(){
if(this.head!=null){
this.head.printNode();
}
}
}
其中的addNode和printNode方法來自Node類：
//遞歸添加節點
public void addNode(Node node){
if(this.next==null){
this.next = node;
}else{
this.next.addNode(node);
}
}
//遞歸打印節點
public void printNode(){
System.out.println(this.data);
if(this.next!=null){
this.next.printNode();
}
}
在主函數里：
Link link = new Link();
link.add("1");
link.add("2");
link.add("3");
link.print();
3.高級
在可用鏈表中，你不可能直接操作節點類吧,像這樣：
Node n = new Node("n");
所以，我們要讓Node類只能被Link類使用，具體方法是將Node類聲明為Link類的私有內部類：
4.終極
一個鏈表不可能只有一個add方法吧，接下來就完善方法：
1.size():取得元素個數
在Link類中聲明屬性count：
private int count = 0;
在add函數里自加：
this.count++;//增加完就++
返回size：
//取得數量
public int size(){
return this.count;
}
測試：
Link link = new Link();
link.add("1");
link.add("2");
link.add("3");
link.add(null);
System.out.println(link.size());
可以看到我添加了一個null元素，但也添加進去了，添不添加取決于自己4，我這里不讓添加，所以在add函數里修改：
if(null==data){
return ;
}
2.isEmpty():判斷鏈表是否為空：
public boolean isEmpty(){
return 0==this.count;
}
3.contains(data):判斷數據是否存在：
在Link類中：
//根據內容查詢數據
public boolean contains(String data){
if(null==data||null==this.head){
return false;
}else{
return this.head.containNode(data);
}
}
在Node類中：
public boolean containNode(String data){
if(data.equals(this.data)){
return true;
}else{
if(null!=this.next){
return this.next.containNode(data);
}else{
return false;//遞歸結束條件
}
}
}
4.get(int index):根據索引查找數據：
在Link類添加屬性：
private int index = 0;
1
在Node類添加方法：
public String getNode(int index){
//注意Link.this.index
if(Link.this.index++==index){
return this.data;
}else{
return this.next.getNode(index);
}
}
注意：Link.this.index是內部類獲得外部類屬性的方法。
在Link類添加方法：
//通過索引查找內容
public String get(int index){
if(index >= this.count){
return null;
}
this.index = 0;//每次從頭向后查詢
return this.head.getNode(index);
}
注意：查找時索引從0開始，當然可以改成從1開始。
5.set(int index,data):根據索引修改內容：
其實和查找一樣，只是操作不同方而已：
在Node類：
public void setNode(int index,String data){
if(Link.this.index++==index){
this.data = data;
}else{
this.next.setNode(index, data);
}
}
在Link類：
//根據索引修改內容
public void set(int index,String data){
if(index >= this.count){
return ;
}else{
this.head.setNode(index,data);
}
}
6.remove(data)：刪除一個元素：
這也是相對來說最復雜的部分，不過也很簡單。
在Node類：
//對非根節點的刪除
public void removeNode(Node preNode,String data){
if(data.equals(this.data)){
preNode.next = this.next;
}else{
this.next.removeNode(this, data);
}
}
在Link類，要判斷是否是根節點：
//刪除
public void remove(String data){
if(this.contains(data)){
//刪除根節點
if(data.equals(this.head.data)){
this.head = this.head.next;
}else{ //非根節點
this.head.next.removeNode(this.head, data);
}
this.count--;//別忘了
}
}
7.toArray():轉化成數組：
在Link類添加一個屬性：private String[] retArray;
在Node類：
public void toArrayNode(){
Link.this.retArray[Link.this.index++] = this.data;
if(null!=this.next){
this.next.toArrayNode();
}
}
在Link類：
public String[] toArray(){
if(null == this.head){
return null;
}
this.index = 0;
this.retArray = new String[this.count];
this.head.toArrayNode();
return this.retArray;
}
5.總結
以上代碼不能夠用于實戰開發，只是為了理解引用關系的傳遞，后續的改進可以添加更多的方法，不用遞歸，加入泛型，做出和List一樣的效果。