• data域：用來存放數(shù)據(jù)。
• next域：指向下一個節(jié)點(diǎn)。

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

• 單鏈表(帶頭節(jié)點(diǎn))
  
• 單鏈表(不帶頭節(jié)點(diǎn))
  

二、單鏈表的實(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)。

代碼實(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)；

代碼實(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ī)制回收。
??? ??: ???? ???? ? ?????.
?? ??: ?? ??? ?????.

??? ??? ??? ????. ?? ??? ?? ?? ??? ?? ??? ?? ?? ???? ????.

?? ?? ??(?? ??)
?? ?? ??(?? ?? ??)

2. ?? ?? ??? ??

1) ??? ??, ??, ?? ? ??? ????? 2) ? ?? ??? ?? ?? ? ??? ?? ?? ?? ???? ????. ??. 3) ? ?? ??? ??? ??? ? ??? ?? ??? ??? ??? ?????. (??? ?? ???? ?? ??? ???? ????? ?????.) 1. ?? ???? ?? ??(??)

	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);
		}
	}

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 + "]";
	}}

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 stack = new Stack();
		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 + "]";
	}}

? ??? ?? ?? ???(Linked List) ?? Java ??? ?? ?????. ??? ??? PHP ??? ????? ?? ?? ??? ?????!