Java如何實(shí)現帶頭結點(diǎn)的單鏈表

這篇文章主要介紹Java如何實(shí)現帶頭結點(diǎn)的單鏈表，文中介紹的非常詳細，具有一定的參考價(jià)值，感興趣的小伙伴們一定要看完！

鏈表的特點(diǎn)

1，以節點(diǎn)方式存儲，是鏈式結構。

2，每個(gè)節點(diǎn)包含data域，next域：指向下一個(gè)節點(diǎn)。

3，鏈表的各個(gè)節點(diǎn)不一定是連續存儲。

4，鏈表分為帶頭節點(diǎn)和不帶頭節點(diǎn)兩種類(lèi)型的鏈表。

實(shí)現原理

添加節點(diǎn)：首先遍歷原有鏈表，找到最后一個(gè)節點(diǎn)，將要增加的節點(diǎn)添加到該節點(diǎn)的后面。下面介紹如何找到最后一個(gè)節點(diǎn)。

思路是這樣的，先遍歷整個(gè)鏈表，定義一個(gè)輔助變量temp，用于暫時(shí)存儲遍歷出來(lái)的各個(gè)節點(diǎn)。首先將head頭節點(diǎn)賦給temp（從頭節點(diǎn)開(kāi)始遍歷），通過(guò)一個(gè)死循環(huán)不斷的遍歷節點(diǎn)的next，直到temp.next==null時(shí)，該節點(diǎn)temp就是鏈表的最后一個(gè)節點(diǎn)，只需要將該節點(diǎn)的next指向新增節點(diǎn)就行了。

修改節點(diǎn)：首先遍歷整個(gè)鏈表，通過(guò)傳入的編號去匹配原有的鏈表的編號，找到對應的編號將節點(diǎn)里面的數據替換即可。

刪除節點(diǎn)：如圖所示，要刪除某一節點(diǎn)，需要遍歷整個(gè)鏈表，找到該節點(diǎn)對應的編號，再將該前一個(gè)節點(diǎn)的next指向要刪除的節點(diǎn)的后面的一個(gè)節點(diǎn)，即（temp.next = temp.next.next）。由于被刪除的節點(diǎn)沒(méi)有被引用，將會(huì )被垃圾回收機制回收掉。

主要代碼

package cn.mrlij.linkedlist;/*** * 單鏈表的實(shí)現 * @author dreamer * */public class SingleLinkedList { public static void main(String[] args) { SingleLinkedListDemo s = new SingleLinkedListDemo(); HeroNode h2 = new HeroNode(1, "宋江", "及時(shí)雨"); HeroNode h3 = new HeroNode(3, "盧俊義", "玉麒麟"); HeroNode h4 = new HeroNode(4, "吳用", "智多星"); HeroNode h5 = new HeroNode(2, "林沖", "豹子頭"); s.addByOrder(h2); s.addByOrder(h3); s.addByOrder(h4); s.addByOrder(h5); System.out.println("修改前————"); s.list();// HeroNode h6 = new HeroNode(4, "有用", "超星星");// s.update(h6); s.del(1); s.del(4); s.del(2); s.del(3); System.out.println("刪除后————"); s.list(); } }class SingleLinkedListDemo{ //創(chuàng  )建一個(gè)頭結點(diǎn)，初始化數據，頭結點(diǎn)不要動(dòng)，不放具體的數據 private HeroNode head = new HeroNode(0,"",""); //添加英雄 public void add(HeroNode node) { //先找出最后的一個(gè)節點(diǎn)，把新加的節點(diǎn)放在最后一個(gè)節點(diǎn)的后面 HeroNode temp = head; while(true) {  if(temp.next == null) {  break;  }  temp = temp.next; } temp.next = node; } public void addByOrder(HeroNode node) { HeroNode temp = head; boolean flag = false; while(true) {  if(temp.next == null) {  break;  }  if(temp.next.no>node.no) {  break;  }else if(temp.next.no == node.no) {  flag = true;  break;  }  temp = temp.next; } if(flag) {  System.out.println("編號"+node.no+"已經(jīng)存在了！"); }else {  node.next = temp.next;  temp.next = node; } } public void update(HeroNode node ) { if(head.next == null) {  System.out.println("鏈表為空！");  return; } HeroNode temp = head.next; boolean flag = false; while(true) {  if(temp == null) {  break;  }  if(temp.no == node.no) {  flag = true;  break;  }  temp = temp.next; } if(flag) {  temp.name = node.name;  temp.nickname = node.name; }else {  System.out.println("不存在該節點(diǎn)！"); } } //刪除節點(diǎn) public void del(int no) { if(head.next == null) {  System.out.println("鏈表為空！");  return; } HeroNode temp = head; boolean flag = false; while(true) {  if(temp.next == null) {  break;  }  if(temp.next.no == no) {  flag = true;  break;  }  temp = temp.next; } if(flag) {  temp.next = temp.next.next; }else {  System.out.println("該節點(diǎn)不存在！"); } } public void list() { HeroNode temp = head; if(temp.next == null) {  System.out.println("鏈表為空！");  return; } while(true) {  if(temp.next == null) {  break;  }  System.out.println(temp.next);  temp = temp.next;  } }}class HeroNode{ public int no;//英雄編號 public String name;//人名 public String nickname;//綽號 public HeroNode next;//下一個(gè)節點(diǎn) public HeroNode(int no, String name, String nickname) { this.no = no; this.name = name; this.nickname = nickname; } @Override public String toString() { return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]"; }   }