連結清單
單連結清單
package com.linkedlist;
import com.sun.xml.internal.bind.util.Which;
import java.util.WeakHashMap;
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(hero3);
singleLinkedList.addByOrder(hero4);
singleLinkedList.addByOrder(hero2);
//輸出
singleLinkedList.list();
//測試修改節點的代碼
HeroNode newHeroNode = new HeroNode(3,"吳用upup","智多星upup");
singleLinkedList.update(newHeroNode);
System.out.println("---修改後情況---");
singleLinkedList.list();
//測試删除節點
singleLinkedList.delete(3);
System.out.println("---删除後情況---");
singleLinkedList.list();
}
}
//定義HeroNode,連結清單的節點
class HeroNode{
public int no;
public String name;
public String nickname;
public HeroNode next;//指向下一個節點
//構造器
public HeroNode(int no,String name,String nickname){
this.no = no;
this.name = name;
this.nickname = nickname;
}
//重寫toString,不列印next
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickname='" + nickname + '\'' +
'}';
}
}
/**
* 定義一個SingleLinkedList連結清單 管理節點
*/
class SingleLinkedList{
//初始化一個頭結點,不存放具體資料
private HeroNode head = new HeroNode(0,"","");
//添加節點方法
//添加到最後
public void add(HeroNode heroNode){
//輔助指針temp
HeroNode temp = head;
//周遊連結清單,找到最後
while (true) {
if (temp.next == null) {
break;
}
//如果沒有找到最後,就将temp後移
temp = temp.next;
}
//退出while循環時,temp就指向了最後一個節點
//添加新的節點
temp.next=heroNode;
}
//添加節點方法
//添加到連結清單最後,尾插法
public void addByOrder(HeroNode heroNode){
//輔助指針temp,位于添加位置的前一個節點
HeroNode temp = head;
boolean flag = false; //标志添加的編号是否存在,預設為false
while (true){
if (temp.next == null) {//說明temp已經在連結清單最後
break;
}else if(temp.next.no > heroNode.no){//位置找到,在temp後面插入
break;
}else if(temp.next.no == heroNode.no){//說明添加的編号已存在
flag = true;
break;
}
temp = temp.next; // 後移
}
//判斷flag的值
if(flag){//編号存在,不能添加
System.out.println("準備插入的英雄編号已經存在,不能添加");
}else {
//插入到連結清單中,temp後面
heroNode.next = temp.next;
temp.next = heroNode;
}
}
//修改節點資訊,根據newHeroNode的no編号修改
public void update(HeroNode newHeroNode){
//判斷是否為空
if(head.next == null){
System.out.println("連結清單為空");
return;
}
//找到需要修改的節點,根據no編号
//定義輔助變量temp
HeroNode temp = head.next;
boolean flag =false; //表示是否找到該節點
while (true){
if(temp == null){
break; //周遊到最後
}else 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.println("未找到需要修改的節點");
}
}
//删除節點
public void delete(int no){
//判斷是否為空
if (head.next == null){
System.out.println("連結清單為空");
return;
}
//
HeroNode temp = head;
boolean flag = false;
//找到待删除節點的前一個節點
while (true){
if(temp.next==null){//周遊到最後
break;
}else if(temp.next.no == no){//找到待删除節點的前一個節點
flag = true;
break;
}
temp = temp.next;
}
//判斷flag
if (flag){
//可以删除
temp.next =temp.next.next;
}else {
System.out.println("未找到待删除節點");
}
}
//顯示連結清單(周遊)
public void list(){
//先判斷連結清單是否為空
if (head.next == null){
System.out.println("連結清單為空");
return;
}
//輔助指針temp
HeroNode temp = head.next;
while(true){
//判斷是否到最後
if(temp == null){
break;
}
//輸出節點資訊
System.out.println(temp.toString());
//next後移
temp=temp.next;
}
}
}
雙向連結清單
package com.linkedlist;
public class DoubleLinkedListDemo {
public static void main(String[] args) {
//測試
System.out.println("雙向連結清單的測試:");
//先建立雙向清單節點
HeroNode2 hero1 = new HeroNode2(1, "松江", "及時雨");
HeroNode2 hero2 = new HeroNode2(2,"盧俊義","玉麒麟");
HeroNode2 hero3 = new HeroNode2(3,"吳用","智多星");
HeroNode2 hero4 = new HeroNode2(4,"林沖","豹子頭");
//建立一個雙向連結清單
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
//加入
// doubleLinkedList.add(hero1);
// doubleLinkedList.add(hero2);
// doubleLinkedList.add(hero3);
// doubleLinkedList.add(hero4);
//按編号順序加入
doubleLinkedList.addByOrder(hero1);
doubleLinkedList.addByOrder(hero3);
doubleLinkedList.addByOrder(hero4);
doubleLinkedList.addByOrder(hero2);
//輸出
doubleLinkedList.list();
//測試修改節點的代碼
HeroNode2 newHeroNode = new HeroNode2(3,"吳用upup","智多星upup");
doubleLinkedList.update(newHeroNode);
System.out.println("---修改後情況---");
doubleLinkedList.list();
//測試删除節點
doubleLinkedList.delete(3);
System.out.println("---删除後情況---");
doubleLinkedList.list();
}
}
//定義HeroNode2,節點
class HeroNode2{
public int no;
public String name;
public String nickname;
public HeroNode2 next;//指向下一個節點
public HeroNode2 pre;//指向前節點
//構造器
public HeroNode2(int no,String name,String nickname){
this.no = no;
this.name = name;
this.nickname = nickname;
}
//重寫toString,不列印next
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickname='" + nickname + '\'' +
'}';
}
}
//建立一個雙向連結清單的類
class DoubleLinkedList{
//初始化一個頭結點,不存放具體資料
private HeroNode2 head = new HeroNode2(0,"","");
//周遊雙向連結清單,與單連結清單一樣
public void list(){
//先判斷連結清單是否為空
if (head.next == null){
System.out.println("連結清單為空");
return;
}
//輔助指針temp
HeroNode2 temp = head.next;
while(true){
//判斷是否到最後
if(temp == null){
break;
}
//輸出節點資訊
System.out.println(temp.toString());
//next後移
temp=temp.next;
}
}
//添加到雙向連結清單最後
public void add(HeroNode2 heroNode) {
//輔助指針temp
HeroNode2 temp = head;
//周遊連結清單,找到最後
while (true) {
if (temp.next == null) {
break;
}
//如果沒有找到最後,就将temp後移
temp = temp.next;
}
//退出while循環時,temp就指向了最後一個節點
//添加新的節點,形成雙向連結清單
temp.next = heroNode;
heroNode.pre = temp;
}
//添加節點方法
//按no編号順序插入
public void addByOrder(HeroNode2 heroNode){
//輔助指針temp,位于添加位置的前一個節點
HeroNode2 temp = head;
boolean flag = false; //标志添加的編号是否存在,預設為false
while (true){
if (temp.next == null) {//說明temp已經在連結清單最後
break;
}else if(temp.next.no > heroNode.no){//位置找到,在temp後面插入
break;
}else if(temp.next.no == heroNode.no){//說明添加的編号已存在
flag = true;
break;
}
temp = temp.next; // 後移
}
//判斷flag的值
if(flag){//編号存在,不能添加
System.out.println("準備插入的英雄編号已經存在,不能添加");
}else {
//插入到連結清單中,temp後面
heroNode.next = temp.next;
temp.next = heroNode;
if(heroNode.next!=null){
//如果是最後一個節點則不需要
heroNode.next.pre = heroNode;
heroNode.pre = temp;
}
}
}
//修改,同單向連結清單
public void update(HeroNode2 newHeroNode){
//判斷是否為空
if(head.next == null){
System.out.println("連結清單為空");
return;
}
//找到需要修改的節點,根據no編号
//定義輔助變量temp
HeroNode2 temp = head.next;
boolean flag =false; //表示是否找到該節點
while (true){
if(temp == null){
break; //周遊到最後
}else 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.println("未找到需要修改的節點");
}
}
//删除節點,可以直接找到要删除節點,然後自我删除
public void delete(int no){
//判斷是否為空
if (head.next == null){
System.out.println("連結清單為空,無法删除");
return;
}
//
HeroNode2 temp = head.next;
boolean flag = false;
while (true){
if(temp == null){//周遊到最後
break;
}else if(temp.no == no){//找到待删除節點
flag = true;
break;
}
temp = temp.next;
}
//判斷flag
if (flag){
//雙向清單的删除
temp.pre.next =temp.next;
if (temp.next!=null){
//如果是最後一個節點則不需要
temp.next.pre = temp.pre;
}
}else {
System.out.println("未找到待删除節點");
}
}
}
個人學習筆記,最後求看到的大佬給個贊吧(#^ .^#)!!