鏈結串列是個好玩的東西
只是單純的利用 Node類別的互相鏈結
就創造出許多不同的用法
class Node
{
Node link;
int data;
}
用link指向 下一個 node 而下一個node中又有link 又能指向其他的node
就這樣 不同的串接 形成龐大的鏈結
不過由於每次鏈結都要創造出新的空間 並更動鏈結
是挺耗時的做法呢
優點在於不須指定起始大小，能一直串接下去
1.新增
新增的概念是
i.為最前面的節點
newNode.link = front;
front = newNode;
新的點的link連到front
(new)|_| ----------> (front) |_| --->|_| --->|_| --->|_| --->..........
表示newNode後面就鏈結了原本的所有的串列 能一直往後跑
所以讓front = newNode;
(front)|_| ----------> |_| --->|_| --->|_| --->|_| --->..........
這樣就變成了(front 即是剛剛的newNode) |_| --->|_| --->|_| --->|_| --->..........
ii.為後面的兩點間或最後的點
newNode.link = preNode.link;
preNode.link = newNode;
第一行程式碼為 新節點的鏈結 跟 尋訪到藥插入的位置前一個的鏈結一樣鏈結到後面的點
---->(pre)|_| ----> |_|
↑ (也連過去)
|_| -------
(newNode)
第二行程式碼為 再把前面的那個節點的連結改連到新的節點
---->(pre)|_| |_|
↓ ↑
------ > |_| (pre改連過來)
(newNode)
這樣就成功的連結了!!
雖然有點繞路的感覺?
反正就是廢棄原來的連結 連到新的點 新的點在連回去這樣往後
利用for去尋訪 每次都讓 temp = temp.link
一直往後面跑
|_|--> |_| --> |_| |_| -->null
↓ ↑
--> |_| ((可能歪七扭八的?
如果變成null後表示到底了 就要新增在最末端
如果 temp.data < 使用者輸入的值 表示尋訪到的兩點中間插入
才能正確的排序
2.刪除
刪除就比較簡單了
temp.link =temp.link.link;
直接給他跳過去!!((雖然這樣好像會讓被跳過的點有佔著空間卻沒有用?
圖像化的話就是這種感覺吧
原來的
|_| -----> |_| ----->|_|
變成
|_| (斷了) |_| ----->|_|
↓ ↑
------------------------ ((繞路了
所以中間那個點阿 FOR在尋訪時 就連不過去了
可是他又不等於null 不會被回收 就很可憐的被遺忘了?
課本是有寫成先創一個temp點，讓temp等於那個可憐的點
等改完鏈結後 在讓temp等於null
由於是傳址應該有用，可是不確定 就懶得key上去了= =+
3.再來是反轉
課本寫那樣太簡陋的是也，只是單純的轉過來，然後一樣是小排到大插入
會造成原本的排序就錯亂了，所以我就一樣改寫了他
利用
revOp = revOp == true ? false : true;
//true變false false變true
很簡單的就讓他在大到小或小到大之間轉換
每次反轉時true跟false就會互換，true是小到大 false反之
再來就是精華-->反轉的方法
while(front != null)//一個一個轉換鏈結
{
a = b;
b = front;
front = front.link;
b.link = a;
//當是最後個鏈結時設為front
if(front == null)
{
front = b;
break;
}
}
一開始a跟b都是null
|_| (a)---
↓
null
↑
|_| (b)---
讓b等於一開始的那個節點
(front)|_|-->|_|-->|_|-->|_|-->...
↑
(b)|_|--- (因為等於 所以有一樣的連結)
然後讓front節點跑到下一個節點
|_|-->(front)|_|-->|_|-->|_|-->..
↑
(b)|_|--------- (front雖然往後移了可是b不變)
讓b在指到a ((一開始會指到null 鏈結串列最後都會指到null (由於link的預設都是null 所以還沒指到下一節點的link就是null)
null(a)<----|_| (front)|_|-->|_|-->|_|-->..
↑
-------(b)|_|
下一圈時
a跑到第一個節點
null<----|_|(a)(front) |_|-->|_|-->|_|-->.
↑
-------(b)|_|
b 在等於新的front((就是原來的front的下一個節點
null<----|_|(a)(front) |_|-->|_|-->|_|-->.
↑
(b)|_|------------------
然後front = front.link((又往後跳
null<----|_|(a) |_|(front)-->|_|-->|_|-->.
↑
(b)|_|-------------
b又連回a ((新的front 連到原先的front的那個點
null<----|_|(a) <-----|_| (front)-->|_|-->|_|-->.
↑
---- (b)|_|
一直往後推
.
.
.
最後就會全部反過來了
程式碼如下
import java.util.Scanner;
class Main {
public static void main(String[] args)
{
Scanner input = new Scanner(System.in);
LinkList MyList = new LinkList();
System.out.print("請輸入指令 1.插入 2.刪除 3.反轉 4.查詢長度 : ");
while(input.hasNext())
{
switch(input.nextInt())
{
case 1 :
System.out.print("請輸入要插入的數字 : ");
MyList.add(input.nextInt());
break;
case 2 :
System.out.print("請輸入要刪除的數字 : ");
MyList.del(input.nextInt());
break;
case 3 :
System.out.print("反轉 : ");
MyList.rev();
break;
case 4 :
System.out.println("長度為 : "+MyList.count());
break;
}
System.out.print("請輸入指令 1.插入 2.刪除 3.反轉 4.查詢長度 : ");
}
}
}
class Node
{
public int data;
public Node link;
Node(int data){this.data = data;}
}
class LinkList
{
int count_ = 0;
Node front;
boolean revOp = true;
public void add(int data)
{
count_++;
Node newNode = new Node(data) , preNode = null , temp = front;
if(front == null)//第一次插入時
{
front = newNode;
print();
return ;
}
if(revOp)//true為 小-->大 False為 大-->小
for(;temp != null && newNode.data > temp.data ; preNode = temp, temp = temp.link );
else
for(;temp != null && newNode.data < temp.data ; preNode = temp, temp = temp.link );
if(preNode == null)//為最前面的節點
{
newNode.link = front;
front = newNode;
}
else//不為最前面的節點
{
newNode.link = preNode.link;
preNode.link = newNode;
}
print();
}
public void del(int data)
{
Node temp = front;
if(front ==null||temp.data == data )//無元素或要刪除的為第一個節點
{
if(front !=null )
{
front= front.link;
count_--;
}
else System.out.println("無元素");
print();
return;
}
for(;temp.link != null && temp.link.data != data ;temp = temp.link);//尋訪
if(temp.link != null)//有找到
{
temp.link =temp.link.link;
print();
count_--;
}
else
{
System.out.println("串列中無該元素");
}
}
public void rev()
{
revOp = revOp == true ? false : true; //true變false false變true
Node a =null,b =null;
while(front != null)//一個一個轉換鏈結
{
a = b;
b = front;
front = front.link;
b.link = a;
if(front == null)//當是最後個鏈結時設為front
{
front = b;
break;
}
}
print();
}
public void print()//印出串列的鏈結
{
Node printTemp =front;
while(printTemp != null)
{
System.out.print(printTemp.data);
printTemp = printTemp.link;
if(printTemp != null)System.out.print(" --> ");
else System.out.println();
}
}
public int count(){return count_;}//回傳串列的長度
}
留言列表
HTML (0)
