溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點(diǎn)擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

java實(shí)現(xiàn)單鏈表linked list的方法

發(fā)布時間:2021-03-01 10:15:45 來源:億速云 閱讀:195 作者:清風(fēng) 欄目:編程語言

這篇“java實(shí)現(xiàn)單鏈表linked list的方法”除了程序員外大部分人都不太理解,今天小編為了讓大家更加理解“java實(shí)現(xiàn)單鏈表linked list的方法”,給大家總結(jié)了以下內(nèi)容,具有一定借鑒價值,內(nèi)容詳細(xì)步驟清晰,細(xì)節(jié)處理妥當(dāng),希望大家通過這篇文章有所收獲,下面讓我們一起來看看具體內(nèi)容吧。

Java的特點(diǎn)有哪些

Java的特點(diǎn)有哪些 1.Java語言作為靜態(tài)面向?qū)ο缶幊陶Z言的代表,實(shí)現(xiàn)了面向?qū)ο罄碚?,允許程序員以優(yōu)雅的思維方式進(jìn)行復(fù)雜的編程。 2.Java具有簡單性、面向?qū)ο蟆⒎植际?、安全性、平臺獨(dú)立與可移植性、動態(tài)性等特點(diǎn)。 3.使用Java可以編寫桌面應(yīng)用程序、Web應(yīng)用程序、分布式系統(tǒng)和嵌入式系統(tǒng)應(yīng)用程序等。

一、單鏈表介紹

單鏈表是一個有序列表,以節(jié)點(diǎn)的方式鏈?zhǔn)酱鎯π畔?/code>,但節(jié)點(diǎn)不一定連續(xù),每一個節(jié)點(diǎn)包括data域和next域。

  • data域:用來存放數(shù)據(jù)。

  • next域:指向下一個節(jié)點(diǎn)。

java實(shí)現(xiàn)單鏈表linked list的方法

鏈表分為帶頭節(jié)點(diǎn)的鏈表不帶頭節(jié)點(diǎn)的鏈表。

  • 單鏈表(帶頭節(jié)點(diǎn))
    java實(shí)現(xiàn)單鏈表linked list的方法

  • 單鏈表(不帶頭節(jié)點(diǎn))
    java實(shí)現(xiàn)單鏈表linked list的方法

二、單鏈表的實(shí)現(xiàn)

需求:使用帶head頭的單向鏈表實(shí)現(xiàn)–水滸英雄排行榜管理。
1)完成對英雄的增刪改查
2)第一種方法在添加英雄時,直接添加到鏈表的尾部。
3)第二種方式在添加英雄時,根據(jù)排名將英雄插入到指定位置(如果已有這個排名,則添加失敗,并給出提示)

1.單鏈表的創(chuàng)建(添加)

1.1尾添加

尾添加的思路

先創(chuàng)建一個head頭節(jié)點(diǎn),作用就是表示單鏈表的頭。
然后每添加一個節(jié)點(diǎn),就直接加入到鏈表的最后。

尾添加即:不考慮編號順序,找到當(dāng)前鏈表的最后節(jié)點(diǎn),將最后這個節(jié)點(diǎn)的next指向新的節(jié)點(diǎn)。
java實(shí)現(xiàn)單鏈表linked list的方法
代碼實(shí)現(xiàn)

	// 添加方式1:尾添加
	public void add(HeroNode heroNode) {
		// 因?yàn)閔ead頭不能動,因此需要一個輔助變量(指針)temp
		HeroNode temp = head;
		while (true) {
			// 如果遍歷到鏈表的最后
			if (temp.next == null) {
				break;
			}
			// temp指針后移
			temp = temp.next;
		}
		// 當(dāng)退出循環(huán)時,temp指向鏈表的最后
		temp.next = heroNode;
	}

1.2按排名添加

按排名添加的思路
先通過輔助變量(temp指針)找到新添加的節(jié)點(diǎn)的位置。
新節(jié)點(diǎn).next=temp.next;
temp.next=新的節(jié)點(diǎn);

java實(shí)現(xiàn)單鏈表linked list的方法

代碼實(shí)現(xiàn)

	// 添加方式2:根據(jù)排名添加
	public void addByOrder(HeroNode heroNode) {
		HeroNode temp = head;// 借助輔助指針
		boolean flag = false;// 添加的編號是否存在
		while (true) {
			if (temp.next == null) {// 遍歷到結(jié)尾
				break;
			}
			if (temp.next.no > heroNode.no) {// 位置找到,就在temp的后面插入
				break;
			} else if (temp.next.no == heroNode.no) {// 該編號已存在
				flag = true;
				break;
			}
			temp = temp.next;// 后移,遍歷當(dāng)前鏈表
		}
		if (flag) {
			// 不能添加
			System.out.printf("準(zhǔn)備插入的英雄的編號%d已經(jīng)存在,不能加入\n", heroNode.no);
		} else {
			// 插入到temp的后面
			heroNode.next = temp.next;
			temp.next = heroNode;
		}
	}

2.單鏈表節(jié)點(diǎn)的修改

修改的思路
通過遍歷先找到該節(jié)點(diǎn)。
temp.name =newHeroNode.name;,temp.nickname=newHeroNode.nickname;

代碼實(shí)現(xiàn)

	// 修改節(jié)點(diǎn)信息,根據(jù)節(jié)點(diǎn)的no屬性修改其他信息
	public void update(HeroNode newHeroNode) {
		// 空鏈表無法修改節(jié)點(diǎn)信息
		if (head.next == null) {
			System.out.println("鏈表為空~");
			return;
		}
		// 根據(jù)no排名找到需要修改的節(jié)點(diǎn)
		HeroNode temp = head.next;
		boolean flag = false;// flag表示是否找到需要修改的節(jié)點(diǎn)
		while (true) {
			if (temp == null) {
				// 遍歷到結(jié)尾
				break;
			}
			if (temp.no == newHeroNode.no) {
				// 找到
				flag = true;
				break;
			}
			temp = temp.next;// 后移
		}
		if (flag) {
			temp.name = newHeroNode.name;
			temp.nickname = newHeroNode.nickname;
		} else {
			System.out.printf("沒有找到編號為%d的節(jié)點(diǎn),不能修改\n", newHeroNode.no);
		}
	}

3.單鏈表節(jié)點(diǎn)的刪除

刪除的思路

找到需要刪除的節(jié)點(diǎn)的前一個節(jié)點(diǎn)。
temp.next=temp.next.next
被刪除的節(jié)點(diǎn),將不會有其它引用指向,會被垃圾回收機(jī)制回收。
java實(shí)現(xiàn)單鏈表linked list的方法
代碼實(shí)現(xiàn)

	public void delete(int no) {
		HeroNode temp = head;
		boolean flag = false;// 是否找到待刪除節(jié)點(diǎn)
		while (true) {
			if (temp.next == null) {
				// 遍歷到結(jié)尾
				break;
			}
			if (temp.next.no == no) {
				// 找到了待刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn)
				flag = true;
				break;
			}
			temp = temp.next;// 后移
		}
		if (flag) {
			// 可以刪除
			temp.next = temp.next.next;
		} else {
			System.out.printf("要刪除的%d節(jié)點(diǎn)不存在\n", no);
		}
	}

4.單鏈表的完整實(shí)現(xiàn)

package com.gql.linkedlist;/**
 * 單鏈表
 * 
 * @guoqianliang
 *
 */public class SingleLinkedListDemo {
	public static void main(String[] args) {
		// 創(chuàng)建節(jié)點(diǎn)
		HeroNode hero1 = new HeroNode(1, "宋江", "及時雨");
		HeroNode hero2 = new HeroNode(2, "盧俊義", "玉麒麟");
		HeroNode hero3 = new HeroNode(3, "吳用", "智多星");
		HeroNode hero4 = new HeroNode(4, "林沖", "豹子頭");
		// 創(chuàng)建單向鏈表
		SingleLinkedList singleLinkedList = new SingleLinkedList();
		// 加入
		singleLinkedList.addByOrder(hero1);
		singleLinkedList.addByOrder(hero4);
		singleLinkedList.addByOrder(hero3);
		singleLinkedList.addByOrder(hero2);

		singleLinkedList.list();

		// 測試修改節(jié)點(diǎn)
		HeroNode newHeroNode = new HeroNode(2, "小盧", "玉麒麟~");
		singleLinkedList.update(newHeroNode);
		System.out.println("修改后的鏈表情況:");
		singleLinkedList.list();

		// 刪除一個節(jié)點(diǎn)
		singleLinkedList.delete(1);
		singleLinkedList.delete(2);
		singleLinkedList.delete(3);
		singleLinkedList.delete(4);
		System.out.println("刪除后的鏈表情況:");
		singleLinkedList.list();

	}}//定義SingleLinkedList,管理英雄class SingleLinkedList {
	// 初始化頭結(jié)點(diǎn),不存放具體數(shù)據(jù)
	private HeroNode head = new HeroNode(0, "", "");

	// 添加方式1:尾添加
	// 思路:
	// 1.找到當(dāng)前鏈表的最后節(jié)點(diǎn)
	// 2.將這個最后的節(jié)點(diǎn)的next指向新的節(jié)點(diǎn)
	public void add(HeroNode heroNode) {
		// 因?yàn)閔ead頭不能動,因此需要一個輔助變量(指針)temp
		HeroNode temp = head;
		while (true) {
			// 如果遍歷到鏈表的最后
			if (temp.next == null) {
				break;
			}
			// temp指針后移
			temp = temp.next;
		}
		// 當(dāng)退出循環(huán)時,temp指向鏈表的最后
		temp.next = heroNode;
	}

	// 添加方式2:根據(jù)排名添加
	public void addByOrder(HeroNode heroNode) {
		HeroNode temp = head;// 借助輔助指針
		boolean flag = false;// 添加的編號是否存在
		while (true) {
			if (temp.next == null) {// 遍歷到結(jié)尾
				break;
			}
			if (temp.next.no > heroNode.no) {// 位置找到,就在temp的后面插入
				break;
			} else if (temp.next.no == heroNode.no) {// 該編號已存在
				flag = true;
				break;
			}
			temp = temp.next;// 后移,遍歷當(dāng)前鏈表
		}
		if (flag) {
			// 不能添加
			System.out.printf("準(zhǔn)備插入的英雄的編號%d已經(jīng)存在,不能加入\n", heroNode.no);
		} else {
			// 插入到temp的后面
			heroNode.next = temp.next;
			temp.next = heroNode;
		}
	}

	// 修改節(jié)點(diǎn)信息,根據(jù)節(jié)點(diǎn)的no屬性修改其他信息
	public void update(HeroNode newHeroNode) {
		// 空鏈表無法修改節(jié)點(diǎn)信息
		if (head.next == null) {
			System.out.println("鏈表為空~");
			return;
		}
		// 根據(jù)no排名找到需要修改的節(jié)點(diǎn)
		HeroNode temp = head.next;
		boolean flag = false;// flag表示是否找到需要修改的節(jié)點(diǎn)
		while (true) {
			if (temp == null) {
				// 遍歷到結(jié)尾
				break;
			}
			if (temp.no == newHeroNode.no) {
				// 找到
				flag = true;
				break;
			}
			temp = temp.next;// 后移
		}
		if (flag) {
			temp.name = newHeroNode.name;
			temp.nickname = newHeroNode.nickname;
		} else {
			System.out.printf("沒有找到編號為%d的節(jié)點(diǎn),不能修改\n", newHeroNode.no);
		}
	}

	// 刪除節(jié)點(diǎn)
	// 思路:
	// 1.找到需要刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn)
	// 2.temp.next=temp.next.next
	// 3.被刪除的節(jié)點(diǎn)將會被垃圾回收機(jī)制回收
	public void delete(int no) {
		HeroNode temp = head;
		boolean flag = false;// 是否找到待刪除節(jié)點(diǎn)
		while (true) {
			if (temp.next == null) {
				// 遍歷到結(jié)尾
				break;
			}
			if (temp.next.no == no) {
				// 找到了待刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn)
				flag = true;
				break;
			}
			temp = temp.next;// 后移
		}
		if (flag) {
			// 可以刪除
			temp.next = temp.next.next;
		} else {
			System.out.printf("要刪除的%d節(jié)點(diǎn)不存在\n", no);
		}

	}

	// 顯示鏈表[遍歷]
	public void list() {
		// 空鏈表直接返回
		if (head.next == null) {
			System.out.println("鏈表為空");
			return;
		}
		// 仍然使用輔助變量(指針),進(jìn)行循環(huán)
		HeroNode temp = head.next;
		while (true) {
			if (temp == null) {
				break;
			}
			System.out.println(temp);
			// 將temp后移
			temp = temp.next;
		}

	}}//定義HeroNode,每一個HeroNode就是一個節(jié)點(diǎn)class HeroNode {
	public int no;// 排名
	public String name;
	public String nickname;// 昵稱
	public HeroNode next;// 指向下一個節(jié)點(diǎn)

	// 構(gòu)造器
	public HeroNode() {
		super();
	}

	public HeroNode(int no, String name, String nickname) {
		super();
		this.no = no;
		this.name = name;
		this.nickname = nickname;
	}

	// 重寫toString
	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
	}}

運(yùn)行結(jié)果
java實(shí)現(xiàn)單鏈表linked list的方法

三、單鏈表面試題

java實(shí)現(xiàn)單鏈表linked list的方法
上面四個面試題,答案都放在下面的代碼中

package com.gql.LinkedList;import java.util.Stack;/**
 * 模擬單鏈表
 * 
 * @author Hudie
 * @Email:guoqianliang@foxmail.com
 * @date 2020年7月16日下午6:47:42
 */public class SingleLinkedListDemo {
	public static void main(String[] args) {
		// 創(chuàng)建節(jié)點(diǎn)
		HeroNode hero1 = new HeroNode(1, "宋江", "及時雨");
		HeroNode hero2 = new HeroNode(2, "盧俊義", "玉麒麟");
		HeroNode hero3 = new HeroNode(3, "吳用", "智多星");
		HeroNode hero4 = new HeroNode(4, "林沖", "豹子頭");
		// 創(chuàng)建單向鏈表
		SingleLinkedList singleLinkedList = new SingleLinkedList();
		// 加入
		singleLinkedList.addByOrder(hero1);
		singleLinkedList.addByOrder(hero4);
		singleLinkedList.addByOrder(hero3);
		singleLinkedList.addByOrder(hero2);

		singleLinkedList.list();

		// 測試修改節(jié)點(diǎn)
		HeroNode newHeroNode = new HeroNode(2, "小盧", "玉麒麟~");
		singleLinkedList.update(newHeroNode);
		System.out.println("修改后的鏈表情況:");
		singleLinkedList.list();

		// 刪除一個節(jié)點(diǎn)
		singleLinkedList.delete(4);
		System.out.println("刪除后的鏈表情況:");
		singleLinkedList.list();
		
		//練習(xí)4:反向打印單鏈表
		System.out.println("反向打印單鏈表:");
		reversePrint(singleLinkedList.getHead());
		//練習(xí)3:反轉(zhuǎn)單鏈表
		reversalList(singleLinkedList.getHead());
		System.out.println("反轉(zhuǎn)過后的單鏈表為:");
		singleLinkedList.list();
		
		// 練習(xí)1:獲取單鏈表節(jié)點(diǎn)個數(shù)
		System.out.println("單鏈表的有效個數(shù)為:");
		System.out.println(getLength(singleLinkedList.getHead()));
		
		int index = 2;
		//練習(xí)2:獲取單鏈表倒數(shù)第index給節(jié)點(diǎn)
		System.out.println("倒數(shù)第"+ index +"個節(jié)點(diǎn)為:");
		System.out.println(getLastKNode(singleLinkedList.getHead(),index));
	}

	/**
	 * @Description: 獲取單鏈表節(jié)點(diǎn)個數(shù) 思路: while循環(huán) + 遍歷指針
	 */
	public static int getLength(HeroNode head) {
		if (head.next == null) {
			return 0;
		}
		int length = 0;
		// 輔助指針
		HeroNode p = head.next;
		while (p != null) {
			length++;
			p = p.next;
		}
		return length;
	}

	/**
	 * @Description: 
	 * 查找單鏈表中倒數(shù)第index個節(jié)點(diǎn) index:表示倒數(shù)第index給節(jié)點(diǎn) 
	 * 思路:
	 * 1.首先獲取鏈表的長度length,可直接調(diào)用getLength
	 * 2.然后從鏈表第一個開始遍歷,遍歷(length-index)個 
	 * 3.找不到返回null
	 */
	public static HeroNode getLastKNode(HeroNode head, int index) {
		if (head.next == null) {
			return null;
		}
		int length = getLength(head);
		if (index <= 0 || index > length) {
			return null;
		}
		HeroNode p = head.next;
		for(int i = 0;i < length-index;i++){
			p = p.next;
		}
		return p;
	}
	
	/**
	 * @Description: 
	 * 反轉(zhuǎn)單鏈表[帶頭節(jié)點(diǎn)]
	 * 思路:
	 * 1.先定義一個節(jié)點(diǎn)reversalHead = new HeroNode(0,"","");
	 * 2.遍歷原來的鏈表,每遍歷一個節(jié)點(diǎn),就將其取出,并放在新的鏈表reversalHead的最前端
	 * 3.原來的鏈表的head.next = reversalHead;
	 */
	public static void reversalList(HeroNode head){
		//鏈表為空或只有一個節(jié)點(diǎn),無需反轉(zhuǎn),直接返回
		if(head.next == null || head.next.next == null){
			return;
		}
		//輔助指針p
		HeroNode p = head.next;
		HeroNode next = null;//指向輔助指針p的下一個位置
		HeroNode reversalHead = new HeroNode(0,"","");
		//遍歷原來的鏈表,每遍歷一個節(jié)點(diǎn),就將其取出,并放在新的鏈表reversalHead的最前端
		while(p != null){
			next = p.next;
			p.next = reversalHead.next;
			reversalHead.next = p;
			p = next;
		}
		head.next = reversalHead.next;
	}
	/**
	 * @Description: 
	 * 反向打印單鏈表[帶頭節(jié)點(diǎn)]
	 * 思路1:單鏈表反轉(zhuǎn)后打印(不建議,因?yàn)槠茐牧藛捂湵淼慕Y(jié)構(gòu))
	 * 思路2:使用棧結(jié)構(gòu),利用棧先進(jìn)后出的特點(diǎn)
	 */
	public static void reversePrint(HeroNode head){
		if(head.next == null){
			return;
		}
		Stack<HeroNode> stack = new Stack<HeroNode>();
		HeroNode p = head.next;
		while(p != null){
			stack.push(p);
			p = p.next;
		}
		//將棧中的節(jié)點(diǎn)進(jìn)行打印
		while(stack.size() > 0){
			System.out.println(stack.pop());
		}
	}}// 定義SingleLinkedList,管理英雄,即鏈表的增刪改查class SingleLinkedList {
	// 初始化頭結(jié)點(diǎn),不存放具體數(shù)據(jù)
	private HeroNode head = new HeroNode(0, "", "");

	// 添加方式1:尾添加
	// 思路:
	// 1.找到當(dāng)前鏈表的最后節(jié)點(diǎn)
	// 2.將這個最后的節(jié)點(diǎn)的next指向新的節(jié)點(diǎn)
	public void add(HeroNode heroNode) {
		// 因?yàn)閔ead頭不能動,因此需要一個輔助變量(指針)temp
		HeroNode temp = head;
		while (true) {
			// 如果遍歷到鏈表的最后
			if (temp.next == null) {
				break;
			}
			// temp指針后移
			temp = temp.next;
		}
		// 當(dāng)退出循環(huán)時,temp指向鏈表的最后
		temp.next = heroNode;
	}

	public HeroNode getHead() {
		return head;
	}

	// 添加方式2:根據(jù)排名添加
	public void addByOrder(HeroNode heroNode) {
		HeroNode temp = head;// 借助輔助指針
		boolean flag = false;// 添加的編號是否存在
		while (true) {
			if (temp.next == null) {// 遍歷到結(jié)尾
				break;
			}
			if (temp.next.no > heroNode.no) {// 位置找到,就在temp的后面插入
				break;
			} else if (temp.next.no == heroNode.no) {// 該編號已存在
				flag = true;
				break;
			}
			temp = temp.next;// 后移,遍歷當(dāng)前鏈表
		}
		if (flag) {
			// 不能添加
			System.out.printf("準(zhǔn)備插入的英雄的編號%d已經(jīng)存在,不能加入\n", heroNode.no);
		} else {
			// 插入到temp的后面
			heroNode.next = temp.next;
			temp.next = heroNode;
		}
	}

	// 修改節(jié)點(diǎn)信息,根據(jù)節(jié)點(diǎn)的no屬性修改其他信息
	public void update(HeroNode newHeroNode) {
		// 空鏈表無法修改節(jié)點(diǎn)信息
		if (head.next == null) {
			System.out.println("鏈表為空~");
			return;
		}
		// 根據(jù)no排名找到需要修改的節(jié)點(diǎn)
		HeroNode temp = head.next;
		boolean flag = false;// flag表示是否找到需要修改的節(jié)點(diǎn)
		while (true) {
			if (temp == null) {
				// 遍歷到結(jié)尾
				break;
			}
			if (temp.no == newHeroNode.no) {
				// 找到
				flag = true;
				break;
			}
			temp = temp.next;// 后移
		}
		if (flag) {
			temp.name = newHeroNode.name;
			temp.nickname = newHeroNode.nickname;
		} else {
			System.out.printf("沒有找到編號為%d的節(jié)點(diǎn),不能修改\n", newHeroNode.no);
		}
	}

	// 刪除節(jié)點(diǎn)
	// 思路:
	// 1.找到需要刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn)
	// 2.temp.next=temp.next.next
	// 3.被刪除的節(jié)點(diǎn)將會被垃圾回收機(jī)制回收
	public void delete(int no) {
		HeroNode temp = head;
		boolean flag = false;// 是否找到待刪除節(jié)點(diǎn)
		while (true) {
			if (temp.next == null) {
				// 遍歷到結(jié)尾
				break;
			}
			if (temp.next.no == no) {
				// 找到了待刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn)
				flag = true;
				break;
			}
			temp = temp.next;// 后移
		}
		if (flag) {
			// 可以刪除
			temp.next = temp.next.next;
		} else {
			System.out.printf("要刪除的%d節(jié)點(diǎn)不存在\n", no);
		}

	}

	// 顯示鏈表[遍歷]
	public void list() {
		// 空鏈表直接返回
		if (head.next == null) {
			System.out.println("鏈表為空");
			return;
		}
		// 仍然使用輔助變量(指針),進(jìn)行循環(huán)
		HeroNode temp = head.next;
		while (true) {
			if (temp == null) {
				break;
			}
			System.out.println(temp);
			// 將temp后移
			temp = temp.next;
		}

	}}// 定義HeroNode,每一個HeroNode就是一個節(jié)點(diǎn)class HeroNode {
	public int no;// 排名
	public String name;
	public String nickname;// 昵稱
	public HeroNode next;// 指向下一個節(jié)點(diǎn)

	// 構(gòu)造器
	public HeroNode() {
		super();
	}

	public HeroNode(int no, String name, String nickname) {
		super();
		this.no = no;
		this.name = name;
		this.nickname = nickname;
	}

	// 重寫toString
	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
	}}

感謝你的閱讀,希望你對“java實(shí)現(xiàn)單鏈表linked list的方法”這一關(guān)鍵問題有了一定的理解,具體使用情況還需要大家自己動手實(shí)驗(yàn)使用過才能領(lǐng)會,快去試試吧,如果想閱讀更多相關(guān)知識點(diǎn)的文章,歡迎關(guān)注億速云行業(yè)資訊頻道!

向AI問一下細(xì)節(jié)

免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI