模擬雙向鏈接串列(DoublyLinkedList)的新刪修查
import java.util.Stack;
public class Test {
public static void main(String[] args) {
DoublyLinkedList doublyLinkedList = new DoublyLinkedList();
HeroNode heroNode1 = new HeroNode(1, "道明寺 司", "道明寺");
HeroNode heroNode2 = new HeroNode(2, "花澤 類", "花澤類");
HeroNode heroNode3 = new HeroNode(3, "西門 總二郎", "西門");
HeroNode heroNode4 = new HeroNode(4, "美作 玲", "美作");
// doublyLinkedList.add(heroNode2);
// doublyLinkedList.add(heroNode3);
// doublyLinkedList.add(heroNode1);
// doublyLinkedList.add(heroNode4);
// doublyLinkedList.showAllNodes();
doublyLinkedList.addByOrder(heroNode2);
doublyLinkedList.addByOrder(heroNode3);
doublyLinkedList.addByOrder(heroNode1);
doublyLinkedList.addByOrder(heroNode4);
doublyLinkedList.showAllNodes();
heroNode2 = new HeroNode(5, "花澤 類~~", "花澤類~~");
doublyLinkedList.update(heroNode2);
System.out.println("修改後的LinkedList：");
doublyLinkedList.showAllNodes();
// doublyLinkedList.delete(1);
// doublyLinkedList.delete(4);
// doublyLinkedList.delete(2);
// doublyLinkedList.delete(3);
// doublyLinkedList.delete(5);
// System.out.println("刪除後的LinkedList：");
// doublyLinkedList.showAllNodes();
//
// int effectiveCount = doublyLinkedList.getEffectiveCount(doublyLinkedList.getHead());
// System.out.println("有效節點數 = " + effectiveCount);
//
// HeroNode lastedNode = doublyLinkedList.getLastedNode(doublyLinkedList.getHead(), 4);
// System.out.println("倒數第4個節點 = " + lastedNode);
//
// // 反轉雙向鏈接串列
// System.out.println("顯示反轉雙向鏈接串列：");
// doublyLinkedList.reverseLinkedList(doublyLinkedList.getHead());
// doublyLinkedList.showAllNodes();
// System.out.println("打印使用資料結構Stack儲存的逆序LinkedList！");
// reversePrint(doublyLinkedList.getHead());
}
}
/**
* 新建類別(DoublyLinkedList)模擬雙向鏈接串列
*/
class DoublyLinkedList {
// 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()
/**
* 從雙向鏈表最後新增節點
* @param heroNode
*/
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);
heroNode.setPreNode(temp);
}
/**
* 模擬雙向鏈接串列按照英雄編號順序新增
* @param 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(temp.getNextNode)
// exchange position between three nodes
HeroNode next = temp.getNextNode();
temp.setNextNode(heroNode);
temp.getNextNode().setNextNode(next);
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.getNextNode();
while (true) {
if (temp == null) {
System.out.printf("鏈接串列已走到最後，找不到該英雄編號：%d\n", heroNo);
return;
} else if (temp.getHeroNo() == heroNo) {
// just delete current node(temp) directly
temp.getPreNode().setNextNode(temp.getNextNode());
// if delete the end of node, can't run: temp.getNextNode(), otherwise throws NullPointerException
if (temp.getNextNode() != null) {
temp.getNextNode().setPreNode(temp.getPreNode());
}
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) {
//origin linkedList's node less then two, just return
if (head.getNextNode() == null || head.getNextNode().getNextNode() == null) {
return;
}
HeroNode cur = head.getNextNode();
HeroNode next = null;
// create a new LinkedList
HeroNode reverseHead = new HeroNode(0, "", "");
while (cur != null) {
// store it for cur node next time to move on
next = cur.getNextNode();
// the node next to cur point to reverseHead.next
cur.setNextNode(reverseHead.getNextNode());
// let cur node to replace reverseHead.next
reverseHead.setNextNode(cur);
// cur node just move on
cur = next;
}
// head node point to reverseHead.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;
private HeroNode preNode;
// 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 HeroNode getPreNode() {
return preNode;
}
public void setPreNode(HeroNode preNode) {
this.preNode = preNode;
}
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!