新建類別模擬單向鏈接串列：
可以自動按照heroNo大到小排序
可以將節點進行新刪修查：
新增相同heroNo給予訊息提示，無法新增
無法修改heroNo，但可以修改heroName & heroNickname
import static utitled.SingleLinkedList.reversePrint;
import java.util.Stack;
public class Test {
public static void main(String[] args) {
SingleLinkedList singleLinkedList = new SingleLinkedList();
HeroNode heroNode1 = new HeroNode(1, "道明寺 司", "道明寺");
HeroNode heroNode2 = new HeroNode(2, "花澤 類", "花澤類");
HeroNode heroNode3 = new HeroNode(3, "西門 總二郎", "西門");
HeroNode heroNode4 = new HeroNode(4, "美作 玲", "美作");
singleLinkedList.add(heroNode2);
singleLinkedList.add(heroNode3);
singleLinkedList.add(heroNode1);
singleLinkedList.add(heroNode4);
// singleLinkedList.addByOrder(heroNode4);
// singleLinkedList.addByOrder(heroNode1);
// singleLinkedList.addByOrder(heroNode2);
// singleLinkedList.addByOrder(heroNode3);
// singleLinkedList.showAllNodes();
heroNode2 = new HeroNode(5, "花澤 類~~", "花澤類~~");
singleLinkedList.update(heroNode2);
System.out.println("修改後的LinkedList：");
singleLinkedList.showAllNodes();
// singleLinkedList.delete(1);
// singleLinkedList.delete(4);
// singleLinkedList.delete(2);
// singleLinkedList.delete(3);
// singleLinkedList.delete(5);
// System.out.println("刪除後的LinkedList：");
// singleLinkedList.showAllNodes();
//
// int effectiveCount = singleLinkedList.getEffectiveCount(singleLinkedList.getHead());
// System.out.println("有效節點數 = " + effectiveCount);
//
// HeroNode lastedNode = singleLinkedList.getLastedNode(singleLinkedList.getHead(), 4);
// System.out.println("倒數第4個節點 = " + lastedNode);
//
// // 反轉單向鏈接串列
// System.out.println("顯示反轉單向鏈接串列：");
// singleLinkedList.reverseLinkedList(singleLinkedList.getHead());
// singleLinkedList.showAllNodes();
System.out.println("打印使用資料結構Stack儲存的逆序LinkedList！");
reversePrint(singleLinkedList.getHead());
}
}
/**
* 新建類別(SingleLinkedList)模擬單向鏈接串列
*/
class SingleLinkedList {
// step1:new a head node, without data
private HeroNode head = new HeroNode(0, "", "");
public HeroNode getHead() {
return head;
}
// step2:aim to add new node from the end of LinkedList
// so create a function add()
public void add(HeroNode heroNode) {
// connect a node from the end, but not to change head node
HeroNode temp = head;
while (true) {
if (temp.getNextNode() == null) {
// already found the end of node, can jump out loop to connect a node
break;
}
temp = temp.getNextNode();
}
// (temp.next == null) be true, so add a new node here
temp.setNextNode(heroNode);
}
public void addByOrder(HeroNode heroNode) {
HeroNode temp = head;
while (true) {
if (temp.getNextNode() == null
|| temp.getNextNode().getHeroNo() > heroNode.getHeroNo()) {// headNo:1 heroNode:2 headNextNode:4
// exchange position between three nodes
heroNode.setNextNode(temp.getNextNode());
temp.setNextNode(heroNode);
break;
} else if (temp.getNextNode().getHeroNo() == heroNode.getHeroNo()) {
System.out.printf("此英雄編號：%d已存在，無法新增此節點\n", heroNode.getHeroNo());
break;
}
temp = temp.getNextNode();
}
}
public void update(HeroNode heroNode) {
// step1:the node next to head is null, cannot update then return function
if (head.getNextNode() == null) {
System.out.println("鏈接串列為空，無法更新~");
return;
}
HeroNode temp = head.getNextNode();
while (true) {
if (temp.getNextNode() == null) {
// already moved at the end of LinkedList
System.out.printf("鏈接串列已走到最後，找不到該英雄編號: %d\n", heroNode.getHeroNo());
return;
} else if (temp.getHeroNo() == heroNode.getHeroNo()) {
// heroNo is like primary key to find particular HeroNode
temp.setHeroName(heroNode.getHeroName());
temp.setHeroNickname(heroNode.getHeroNickname());
break;
}
temp = temp.getNextNode();
}
}
public void delete(int heroNo) {
if (head.getNextNode() == null) {
System.out.println("鏈接串列為空，無法刪除");
return;
}
HeroNode temp = head;
while (true) {
if (temp.getNextNode() == null) {
// already moved at the end of LinkedList
System.out.printf("鏈接串列已走到最後，找不到該英雄編號：%d\n", heroNo);
return;
} else if (temp.getNextNode().getHeroNo() == heroNo) {
// node's heroNo of next to head node = input heroNo
// use next and next node to replace current temp
temp.setNextNode(temp.getNextNode().getNextNode());
break;
}
temp = temp.getNextNode();
}
}
// step3:show LinkedList all nodes
// so create a function showList()
public void showAllNodes() {
// to check this LinkedList has node or not? but not to change head node
HeroNode temp = head.getNextNode();
while (true) {
if (temp == null) {
// already moved to the end of LinkedList then return function
return;
}
System.out.println(temp);
temp = temp.getNextNode();
}
}
/**
* 取得鏈接串列的有效節點數
* @param head 頭節點
* @return count 有效節點數(排除頭節點)
*/
public int getEffectiveCount(HeroNode head) {
int count = 0;
// the node next to headNode is not null then loop, otherwise return!
if (head.getNextNode() == null) {
return 0;
}
// use current node to store copied node
HeroNode current = head.getNextNode();
while (true) {
if (current == null) {
return count;
}
count++;
current = current.getNextNode();
}
}
/**
*
* @param head 頭節點
* @param inLastOrder 倒數第?個
* @return 倒數第?個節點
*/
public HeroNode getLastedNode(HeroNode head, int inLastOrder) {
// head.next == null，代表鏈接串列為空
if (head.getNextNode() == null) {
return null;
}
// verify valid inLastOrder
// length = effectiveCount
// newLength
int newLength = getEffectiveCount(head) - inLastOrder;
if (newLength > getEffectiveCount(head) && newLength < 0) {
return null;
}
// create a temp node to store node
HeroNode temp = head.getNextNode();
for (int i = 0; i < newLength; i++) {
temp = temp.getNextNode();
}
return temp;
}
/**
* 取得反轉的單向鏈接串列(頭插法)
* @param head 原鏈接串列頭節點
*/
public void reverseLinkedList(HeroNode head) {
// linkedList size less than 2, just return
if (head.getNextNode() == null || head.getNextNode().getNextNode() == null) {
return;
}
// new a linkedList to insert node from first
HeroNode reverseHead = new HeroNode(0, "", "");
HeroNode cur = head.getNextNode();
HeroNode next = null;
while(cur != null) {
// store the next node of cur before cut cur node off from linkedList
next = cur.getNextNode();
// cur node point to the next node of reverseHead after cut off
cur.setNextNode(reverseHead.getNextNode());
// insert cur node to the next node of reverseHead
reverseHead.setNextNode(cur);
// move forward cur node
cur = next;
}
head.setNextNode(reverseHead.getNextNode());
}
/**
* 逆序打印單向鏈接串列
* 使用資料結構Stack後進先出 特性
* @param head 頭節點
*/
public static void reversePrint(HeroNode head) {
if (head.getNextNode() == null) {
return;
}
HeroNode cur = head.getNextNode();
Stack<HeroNode> heroStack = new Stack<>();
while (cur != null) {
// add current node to Stack
heroStack.push(cur);
cur = cur.getNextNode();
}
while (heroStack.size() > 0) {
// loop heroStack to print all heroNode
System.out.println(heroStack.pop());
}
}
}
/**
* 新建類別(HeroNode)模擬LinkedList的節點
*/
class HeroNode {
private int heroNo;
private String heroName;
private String heroNickname;
private HeroNode nextNode;
// constructor
public HeroNode(int no, String name, String nickname) {
this.heroNo = no;
this.heroName = name;
this.heroNickname = nickname;
}
public int getHeroNo() {
return heroNo;
}
public HeroNode getNextNode() {
return nextNode;
}
public void setNextNode(HeroNode nextNode) {
this.nextNode = nextNode;
}
public String getHeroName() {
return heroName;
}
public String getHeroNickname() {
return heroNickname;
}
public void setHeroName(String heroName) {
this.heroName = heroName;
}
public void setHeroNickname(String heroNickname) {
this.heroNickname = heroNickname;
}
@Override
public String toString() {
final StringBuilder sb = new StringBuilder("HeroNode{");
sb.append("heroNo=").append(heroNo);
sb.append(", heroName='").append(heroName).append('\'');
sb.append(", heroNickname='").append(heroNickname).append('\'');
sb.append('}');
return sb.toString();
}
}如有敘述錯誤，還請不吝嗇留言指教，thanks!
