Free learning recommendation: java basic tutorial

##Article directory

1. Introduction to singly linked list
• 2. Implementation of singly linked list
• 1. Creation (addition) of singly linked list
  • 1.1 Add at the end
    • 1.2 Add by ranking
  2. Modification of singly linked list nodes
  • 3. Deletion of singly linked list nodes
  • 4. Complete implementation of singly linked list
3. Single linked surface test questions

---

1. Introduction to singly linked list

Singly linked list is an

ordered list that stores information in the form of node, but the node does not Must be continuous , each node includes data field and next field.

data domain
• : used to store data.
next domain
• : Points to the next node.

The linked list is divided into

the linked list with the head node

and the linked list without the head node.

Singly linked list (leading node)

• 
  Singly linked list (without leading node)
• 
  

2. Implementation of single linked list

Requirements: Use

single linked list with header to implement – ??Water Margin hero ranking management. 1) Complete the addition, deletion, modification and check of the hero
2) When adding a hero in the first method, is directly added to the end of the linked list
. 3) In the second method, when adding a hero, insert the hero into the specified position according to the ranking
(if the ranking already exists, the addition will fail and a prompt will be given)

1. Creation (addition) of a singly linked list

1.1 Adding the tail

The idea of ??adding the tail

①

First create a head node, which is used to represent the head of a singly linked list.

② Then every time a node is added, it is added directly to the end of the linked list.
Tail addition means: regardless of the numbering sequence, find the last node of the current linked list, and point the next of the last node to the new node.

Code implementation

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

1.2 Add by ranking

Ideas of adding by ranking

①First find the location of the newly added node through the auxiliary variable (temp pointer).
②New node.next=temp.next;
③temp.next=New node;

Code implementation

	// 添加方式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;// 后移,遍歷當前鏈表
		}
		if (flag) {
			// 不能添加
			System.out.printf("準備插入的英雄的編號%d已經(jīng)存在，不能加入\n", heroNode.no);
		} else {
			// 插入到temp的后面
			heroNode.next = temp.next;
			temp.next = heroNode;
		}
	}

2. Modification of singly linked list nodes

Modification ideas

①Find the node first through traversal.
②temp.name =newHeroNode.name;
, temp.nickname=newHeroNode.nickname;

Code implementation

	// 修改節(jié)點信息,根據(jù)節(jié)點的no屬性修改其他信息
	public void update(HeroNode newHeroNode) {
		// 空鏈表無法修改節(jié)點信息
		if (head.next == null) {
			System.out.println("鏈表為空~");
			return;
		}
		// 根據(jù)no排名找到需要修改的節(jié)點
		HeroNode temp = head.next;
		boolean flag = false;// flag表示是否找到需要修改的節(jié)點
		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é)點，不能修改\n", newHeroNode.no);
		}
	}

3. Deletion of singly linked list nodes

Deletion ideas

①

Find the node that needs to be deleted the previous node.

②temp.next=temp.next.next
③The deleted node will not have other references pointing to it and will be recycled by the garbage collection mechanism.

Code implementation

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

4. Complete implementation of singly linked list

package com.gql.linkedlist;/**
 * 單鏈表
 * 
 * @guoqianliang
 *
 */public class SingleLinkedListDemo {
	public static void main(String[] args) {
		// 創(chuàng)建節(jié)點
		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é)點
		HeroNode newHeroNode = new HeroNode(2, "小盧", "玉麒麟~");
		singleLinkedList.update(newHeroNode);
		System.out.println("修改后的鏈表情況:");
		singleLinkedList.list();

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

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

	// 添加方式1:尾添加
	// 思路:
	// 1.找到當前鏈表的最后節(jié)點
	// 2.將這個最后的節(jié)點的next指向新的節(jié)點
	public void add(HeroNode heroNode) {
		// 因為head頭不能動,因此需要一個輔助變量(指針)temp
		HeroNode temp = head;
		while (true) {
			// 如果遍歷到鏈表的最后
			if (temp.next == null) {
				break;
			}
			// temp指針后移
			temp = temp.next;
		}
		// 當退出循環(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;// 后移,遍歷當前鏈表
		}
		if (flag) {
			// 不能添加
			System.out.printf("準備插入的英雄的編號%d已經(jīng)存在，不能加入\n", heroNode.no);
		} else {
			// 插入到temp的后面
			heroNode.next = temp.next;
			temp.next = heroNode;
		}
	}

	// 修改節(jié)點信息,根據(jù)節(jié)點的no屬性修改其他信息
	public void update(HeroNode newHeroNode) {
		// 空鏈表無法修改節(jié)點信息
		if (head.next == null) {
			System.out.println("鏈表為空~");
			return;
		}
		// 根據(jù)no排名找到需要修改的節(jié)點
		HeroNode temp = head.next;
		boolean flag = false;// flag表示是否找到需要修改的節(jié)點
		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é)點，不能修改\n", newHeroNode.no);
		}
	}

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

	}

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

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

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

Running results

3. Single-chain surface test questions

The answers to the above four interview questions are In the following code

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é)點
		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é)點
		HeroNode newHeroNode = new HeroNode(2, "小盧", "玉麒麟~");
		singleLinkedList.update(newHeroNode);
		System.out.println("修改后的鏈表情況:");
		singleLinkedList.list();

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

	/**
	 * @Description: 獲取單鏈表節(jié)點個數(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é)點 index:表示倒數(shù)第index給節(jié)點 
	 * 思路:
	 * 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é)點]
	 * 思路:
	 * 1.先定義一個節(jié)點reversalHead = new HeroNode(0,"","");
	 * 2.遍歷原來的鏈表,每遍歷一個節(jié)點,就將其取出,并放在新的鏈表reversalHead的最前端
	 * 3.原來的鏈表的head.next = reversalHead;
	 */
	public static void reversalList(HeroNode head){
		//鏈表為空或只有一個節(jié)點,無需反轉(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é)點,就將其取出,并放在新的鏈表reversalHead的最前端
		while(p != null){
			next = p.next;
			p.next = reversalHead.next;
			reversalHead.next = p;
			p = next;
		}
		head.next = reversalHead.next;
	}
	/**
	 * @Description: 
	 * 反向打印單鏈表[帶頭節(jié)點]
	 * 思路1:單鏈表反轉(zhuǎn)后打印(不建議,因為破壞了單鏈表的結(jié)構(gòu))
	 * 思路2:使用棧結(jié)構(gòu),利用棧先進后出的特點
	 */
	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é)點進行打印
		while(stack.size() > 0){
			System.out.println(stack.pop());
		}
	}}// 定義SingleLinkedList,管理英雄,即鏈表的增刪改查class SingleLinkedList {
	// 初始化頭結(jié)點,不存放具體數(shù)據(jù)
	private HeroNode head = new HeroNode(0, "", "");

	// 添加方式1:尾添加
	// 思路:
	// 1.找到當前鏈表的最后節(jié)點
	// 2.將這個最后的節(jié)點的next指向新的節(jié)點
	public void add(HeroNode heroNode) {
		// 因為head頭不能動,因此需要一個輔助變量(指針)temp
		HeroNode temp = head;
		while (true) {
			// 如果遍歷到鏈表的最后
			if (temp.next == null) {
				break;
			}
			// temp指針后移
			temp = temp.next;
		}
		// 當退出循環(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;// 后移,遍歷當前鏈表
		}
		if (flag) {
			// 不能添加
			System.out.printf("準備插入的英雄的編號%d已經(jīng)存在，不能加入\n", heroNode.no);
		} else {
			// 插入到temp的后面
			heroNode.next = temp.next;
			temp.next = heroNode;
		}
	}

	// 修改節(jié)點信息,根據(jù)節(jié)點的no屬性修改其他信息
	public void update(HeroNode newHeroNode) {
		// 空鏈表無法修改節(jié)點信息
		if (head.next == null) {
			System.out.println("鏈表為空~");
			return;
		}
		// 根據(jù)no排名找到需要修改的節(jié)點
		HeroNode temp = head.next;
		boolean flag = false;// flag表示是否找到需要修改的節(jié)點
		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é)點，不能修改\n", newHeroNode.no);
		}
	}

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

	}

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

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

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

Related learning recommendations:

java basics

The above is the detailed content of Java implementation of singly linked list (Linked List) related. For more information, please follow other related articles on the PHP Chinese website!