文章目錄
- 一、 單連結清單原理
- 二、添加、修改、删除操作
- 三、代碼示例
一、 單連結清單原理
連結清單是一系列的存儲資料元素的單元通過指針串聯起來形成，是以每個單元至少有兩個域，一個用于資料元素的存儲另一個用于指向其他單元。
連結清單的第一個節點和最後一個節點，分别稱為連結清單的首節點和尾節點。
借助next引用我們可以從首節點移動到尾節點。
由于每個結點的資料域都是一個 Object 類的對象，
是以，每個資料元素并非真正如圖中那樣，而是在結點中的資料域通過一個 Object類的對象引用來指向資料元素的。
與數組類似，單連結清單中的結點也具有一個線性次序，即如果結點 P 的 next 引用指向結點 S，則 P 就是 S 的直接前驅，S 是 P 的直接後續。
單連結清單的一個重要特性就是隻能通過前驅結點找到後續結點，而無法從後續結點找到前驅結點。
二、添加、修改、删除操作
添加
第一種方式
添加節點到單向連結清單
思路，當不考慮編号順序時
1.找到目前連結清單的最後節點
2.将最後這個節點的next 指向新的節點
第二種方式
根據序号插入到指定位置，通過一個輔助指針（變量）來幫助我們找到添加的位置。因為單連結清單，因為我們找的temp是位于添加位置的前一個節點，否則插入不了。
查找
修改節點的資訊，根據序号節點來修改，即序号 編号不能改
通過周遊找到節點，對其進行修改
删除
删除節點
思路
1. head不能動，是以我們需要一個temp輔助節點找到待删除節點的前一個節點
2.說明我們在比較時，是temp.next.no 和需要删除的節點no比較
三、代碼示例
package llinkedlist;
public class SingleLInkedListDemo {
public static void main(String[] args) {
//測試
//先創節點
HeroNode hero1=new HeroNode(1,"宋江","及時雨");
HeroNode hero2=new HeroNode(2,"盧俊義","玉麒麟");
HeroNode hero3=new HeroNode(3,"吳用","智多星");
HeroNode hero4=new HeroNode(4,"林沖","豹子頭");
//建立一個連結清單
SingleLInkedList singleLInkedList=new SingleLInkedList();
//加入
// singleLInkedList.add(hero1);
// singleLInkedList.add(hero2);
// singleLInkedList.add(hero3);
// singleLInkedList.add(hero4);
//加入按照編号的順序
singleLInkedList.addByOrder(hero1);
singleLInkedList.addByOrder(hero4);
singleLInkedList.addByOrder(hero3);
singleLInkedList.addByOrder(hero2);
//顯示
singleLInkedList.list();
//測試修改節點的代碼
HeroNode newHeroNode = new HeroNode(2,"小盧","玉麒麟~~");
singleLInkedList.update(newHeroNode);
//顯示
System.out.println("修改之後");
singleLInkedList.list();
//删除
singleLInkedList.del(1);
singleLInkedList.del(3);
System.out.println("删除後的連結清單情況~~");
singleLInkedList.list();
}
}
//定義SingleLinkedList 管理我們的英雄
class SingleLInkedList{
//先初始化一個頭節點，頭節點不要動，不存放具體的資料
private HeroNode head=new HeroNode(0,"","");
//添加節點到單向連結清單
//思路，當不考慮編号順序時
//1.找到目前連結清單的最後節點
//2.将最後這個節點的next 指向新的節點
public void add(HeroNode heroNode) {
//因為head節點不能動，是以我們需要一個輔助變量temp
HeroNode temp=head;
//周遊連結清單，找到最後
while(true) {
//找到連結清單的最後
if(temp.next==null) {
break;
}
//如果沒有找到最後，将temp後移
temp=temp.next;
}
//當退出while循環時，temp就指向了連結清單的最後
//将最後這個節點的next指向新的節點
temp.next=heroNode;
}
//第二種方式在添加英雄時，根據英雄排名插入到指定位置（如果有這個排名，則添加失敗，并給出提示）
public void addByOrder(HeroNode heroNode) {
//因為頭節點不能動，是以我們仍然通過一個輔助指針（變量）來幫助我們找到添加的位置
//因為單連結清單，因為我們找的temp是位于添加位置的前一個節點，否則插入不了
HeroNode temp=head;
boolean flag =false;//flag标志添加的編号是否存在，預設為false
while(true) {
if(temp.next==null) {
break;//說明temp已經在連結清單最後
}
if(temp.next.no>heroNode.no) {//位置在temp和temp.next之間
break;
}else if(temp.next.no==heroNode.no) {
flag=true;//編号存在
break;
}
temp=temp.next;
}
//判斷flag的值
if(flag) {//不能添加，編号存在
System.out.printf("準備添加的英雄編号%d已經存在，不能加入\n",heroNode.no);
}else {
//插入到連結清單中，temp的後面
heroNode.next=temp.next;
temp.next=heroNode;
}
}
//修改節點的資訊，根據no節點來修改，即no 編号不能改
public void update(HeroNode newHeroNode) {
//判斷是否空
if(head.next==null) {
System.out.println("連結清單為空");
return;
}
//找到需要修改的節點，根據no編号
//定義一個輔助變量
HeroNode temp =head.next;
boolean flag =false;//表示是否找到該節點
while(true) {
if(temp==null) {
break;//已經周遊完連結清單
}
if(temp.no ==newHeroNode.no) {
//找到
flag=true;
break;
}
temp=temp.next;
}
//根據flag判斷是否找到要修改的節點
if(flag) {
temp.name=newHeroNode.name;
temp.nickname=newHeroNode.nickname;
}else {//沒有找到
System.out.printf("沒有找到編号%d的節點，不能修改\n",newHeroNode.no);
}
}
//删除節點
//思路
//1. head不能動，是以我們需要一個temp輔助節點找到待删除節點的前一個節點
//2.說明我們在比較時，是temp.next.no 和需要删除的節點no比較
public void del(int no) {
HeroNode temp=head;
boolean flag=false;//标志是否找到待删除節點
while(true) {
if(temp.name==null) {
break;
}
if(temp.next.no==no) {
//找到待删除的節點的前一個temp
flag=true;
break;
}
temp=temp.next;
}
//判斷flag
if(flag) {//找到
//可以删除
temp.next=temp.next .next;
}else {
System.out.printf("要删除的%d節點不存在",no);
}
}
//顯示連結清單【周遊】
public void list() {
//判斷連結清單是否為空
if(head.next==null) {
System.out.println("連結清單為空");
return;
}
//因為頭節點，不能動是以我們需要一個輔助變量來周遊
HeroNode temp=head.next;
while(true) {
//判斷是否到連結清單最後
if(temp==null) {
break;
}
//輸出節點的資訊
System.out.println(temp);
//将temp後移，一定小心
temp=temp.next;
}
}
}
//定義HeroNode ，每個HeroNode 對象就是一個節點
class HeroNode{
public int no;//編号
public String name;//姓名
public String nickname;//昵稱
public HeroNode next;//指向下一個節點
//構造器
public HeroNode(int hNo,String hName, String hNickname) {
this.no=hNo;
this.name=hName;
this.nickname=hNickname;
}
//為了顯示方法我們重寫toString
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
}
}