? 單鏈表是鏈表中結(jié)構(gòu)最簡(jiǎn)單的。一個(gè)單鏈表的節(jié)點(diǎn) (Node) 分為兩個(gè)部分帮非，第一個(gè)部分 (data) 保存或者顯示關(guān)于節(jié)點(diǎn)的信息，另一個(gè)部分存儲(chǔ)下一個(gè)節(jié)點(diǎn)的地址。最后一個(gè)節(jié)點(diǎn)存儲(chǔ)地址的部分指向空值脯爪。
單向鏈表只可向一個(gè)方向遍歷，一般查找一個(gè)節(jié)點(diǎn)的時(shí)候需要從第一個(gè)節(jié)點(diǎn)開始每次訪問下一個(gè)節(jié)點(diǎn)矿微，一直訪問到需要的位置痕慢。而插入一個(gè)節(jié)點(diǎn)，對(duì)于單向鏈表涌矢，我們只提供在鏈表頭插入掖举，只需要將當(dāng)前插入的節(jié)點(diǎn)設(shè)置為頭節(jié)點(diǎn)，next 指向原頭節(jié)點(diǎn)即可娜庇。刪除一個(gè)節(jié)點(diǎn)塔次，我們將該節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)的 next 指向該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。
首先建立一個(gè)鏈表結(jié)點(diǎn)的類名秀，如下所示
package 數(shù)據(jù)結(jié)構(gòu);
public class Node {
? ? ? ? ? int data;//數(shù)據(jù)
? ? ? ? ? public Node next;//下一個(gè)結(jié)點(diǎn)
? ? ? ? ? public Node previous;//上一個(gè)結(jié)點(diǎn)
? ? ? ? ? public Node(int value){
? ? ? ? ? this.data=value;
? ? ? ? ? }
? ? ? ? ? public void display(){
? ? ? ? ? System.out.println(data+"");
? ? ? ? ? }
}
初始化鏈表：
package 數(shù)據(jù)結(jié)構(gòu);
public class LinkList {
Node first;//頭結(jié)點(diǎn)
? ? ? ? ? ? public LinkList(){
? ? ? ? ? ? first=null;//初始化頭結(jié)點(diǎn)為null
? ? ? ? ? ? }
? ? ? ? ? ? public void insertFirst(int value){//插入元素励负，在頭結(jié)點(diǎn)前面插入
? ? ? ? ? ? Node node=new Node(value);
? ? ? ? ? ? node.next=first;
? ? ? ? ? ? first=node;
? ? ? ? ? ? }
? ? ? ? ? ? public int deletFirst(){//刪除元素，從頭結(jié)點(diǎn)開始
? ? ? ? ? ? Node temp=first;
? ? ? ? ? ? first=first.next;//把頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)賦給它匕得，即刪除了頭結(jié)點(diǎn)
? ? ? ? ? ? return temp.data;//返回刪除的結(jié)點(diǎn)的數(shù)據(jù)
? ? ? ? ? ? }
? ? ? ? ? ? public void display(){//將鏈表的數(shù)據(jù)打印出來
? ? ? ? ? ? Node t=first;
? ? ? ? ? ? while(t.next!=null){//打印出除尾結(jié)點(diǎn)以外的數(shù)據(jù)
? ? ? ? ? ? t.display();
? ? ? ? ? ? t=t.next;
? ? ? ? ? ? }
? ? ? ? ? ? t.display();//打印尾結(jié)點(diǎn)的數(shù)據(jù)
? ? ? ? ? ? }
? ? ? ? ? ? public Node chazhao(int value){//按值查找
? ? ? ? ? ? Node tt=first;
? ? ? ? ? ? while(tt.data!=value){
? ? ? ? ? ? if(tt.next==null){
? ? ? ? ? ? return null;
? ? ? ? ? ? }
? ? ? ? ? ? tt=tt.next;
? ? ? ? ? ? }
? ? ? ? ? ? return tt;//返回查找的結(jié)點(diǎn)
? ? ? ? ? ? }
? ? ? ? ? ? public Node shangchu(int value){//按值刪除并輸出值
? ? ? ? ? ? Node tt=first;
? ? ? ? ? ? Node ty=first;
? ? ? ? ? ? while(tt.data!=value){
? ? ? ? ? ? if(tt.next==null){
? ? ? ? ? ? return null;
? ? ? ? ? ? }
? ? ? ? ? ? ty=tt;//ty是要?jiǎng)h除的結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)继榆，因?yàn)楹竺嬉痪浯a將tt的值變成了tt的下一個(gè)結(jié)點(diǎn)
? ? ? ? ? ? ? tt=tt.next;
? ? ? ? ? ? }
? ? ? ? ? ? if(tt==first){
? ? ? ? ? ? first=first.next;
? ? ? ? ? ? }
? ? ? ? ? ? else{
? ? ? ? ? ? ty.next=tt.next;//將tt的前面的結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)變成tt的下一結(jié)點(diǎn)，即刪除了tt結(jié)點(diǎn)
? ? ? ? ? ? }
? ? ? ? ? ? return tt;//返回刪除的結(jié)點(diǎn)
? ? ? ? ? ? }
}
測(cè)試：
package 數(shù)據(jù)結(jié)構(gòu);
public class TextLinkList {
public static void main(String args[]){
? ? ? LinkList a=new LinkList();
? ? ? a.insertFirst(1);//插入數(shù)據(jù)
? ? ? a.insertFirst(2);
? ? ? a.insertFirst(3);
? ? ? a.display();//打印數(shù)據(jù)
? ? ? System.out.println("************");
? ? ? a.deletFirst();//刪除頭結(jié)點(diǎn)
? ? ? a.display();//打印數(shù)據(jù)
? ? ? System.out.println("************");
? ? ? Node node=a.chazhao(1);//查找data值為1的結(jié)點(diǎn)
? ? System.out.println(node.data);//輸出數(shù)據(jù)
? ? System.out.println("************");
? ? Node node1=a.shangchu(1);//刪除結(jié)點(diǎn)data值為1的數(shù)據(jù)
? ? System.out.println(node1.data);//打印數(shù)據(jù)
? ? System.out.println("************");
? ? a.display();
}}
輸出結(jié)果如下：
好啦,這次就到這里啦汁掠，有問題可以和我留言哦略吨！
其他博客的鏈接：
Github個(gè)人網(wǎng)站知乎簡(jiǎn)書
歡迎各位訪問哦，這次就到這里啦考阱！
