package LinkList;
class Node{
public Node next;
public int data;
public Node(int data){
this.data=data;
}
}
public class LinkList{
public Node head;
public int length=0;
//打印鏈表
public void printLinkList()
{
Node p=head;
while(p!=null)
{
System.out.println(p.data);
p=p.next;
}
System.out.println("長度為 ："+length);
}
//判斷鏈表是否為空
public Boolean isEmpty()
{
if(head==null)
return true;
return false;
}
//尾插法添加結點
public void addLastNode(int data)
{
Node x=new Node(data);
if(head==null)
{
head=x;length++;
return;
}
Node q=head;
while(q.next!=null)
q=q.next;
q.next=x;
length++;
}
//頭插法添加結點
public void addHeadNode(int data)
{
Node x=new Node(data);
if(head==null){
head =x;length++;
return;
}
x.next=head;
head=x;
length++;
}
//刪除結點
public Boolean deleteNode(int index)
{
if(index<1||index>length)
return false;
int i=1;
Node p=head;
while(i!=(index-1))
{
p=p.next;
i++;
}
(p.next)=(p.next.next);
length--;
return true;
}
//修改結點
public Boolean updateNode(int index,int data)
{
if(index<1||index>length)
return false;
int i=1;
Node p=head;
while(i<index)
{p=p.next;i++;}
p.data=data;
return true;
}
//向前冒泡，因為冒泡是相鄰倆倆進行比較，所以容易知道，當一輪排序發現順序沒有發生改變則數列已經有序 這樣可以提高效率
public void SortLinkList()
{
Boolean flag=false;
Node p=head;
Node q=null;
for(int i=0;i<length-1;i++)
{
q=p.next;
for(int j=i;j<length-1;j++)
{
if(p.data>q.data)
{
int t=p.data;
p.data=q.data;
q.data=t;
flag=true;
}
q=q.next;
}
if(flag==false)
break;
flag=false;
p=p.next;
}
}
}
測試：
package LinkList;
public class MyLinkedList {
public LinkList linkList=new LinkList();
public void testaddLastNode(){
linkList.addLastNode(1);
linkList.addLastNode(2);
linkList.addLastNode(3);
linkList.addLastNode(4);
linkList.printLinkList();
}
public void testaddHeadNode()
{
linkList.addHeadNode(1);
linkList.addHeadNode(2);
linkList.addHeadNode(3);
linkList.addHeadNode(4);
linkList.printLinkList();
}
public void testdaleteNode()
{
if(linkList.deleteNode(3)==false)
System.out.println("刪除位置有誤");
linkList.printLinkList();
}
public void testUpateNode()
{
if(linkList.updateNode(2, 10)==false)
System.out.println("修改位置有誤");
linkList.printLinkList();
}
public void testSortLinkList()
{
linkList.SortLinkList();
linkList.printLinkList();
}
public static void main(String[] args) {
MyLinkedList main=new MyLinkedList();
main.testaddHeadNode();
System.out.println("================================");
main.testSortLinkList();
}
}
補充：對于冒泡排序，由于是相鄰倆倆進行比較的，所以當一次循環查找發現順序沒有改變，則可以判斷，序列已有序
對于刪除結點，java與c/c++的不同在于java不用手動進行刪除結點的釋放空間，這是由于Java有自動處理垃圾的機制gc
在這里補充一下Java的GC處理機制：
對對象而言，如果沒有任何變量去引用它，那么該對象將不可能被程序訪問，因此可以認為他是垃圾信息，可以被回收，只要有一個以上的變量引用該對象，該對象就不會被回收。所以也就很好解釋在這里為什么我不用手動釋放空間了。
垃圾回收都是依據一定的算法進行的，下面介紹其中幾種常用的垃圾回收算法
（1）引用計數法（Reference Counting Collerctor）
引用計數作為一種簡單但是效率較低的方法，其主要原理如下：在堆中對每個對象都有一個計數器；當對象被引用時，引用計數器+1；當引用被置為空或離開作用域的時候，引用計數-1，由于這種方法無法解決相互引用的問題，因此JVM沒有采用這個算法
（2）追蹤回收算法（Tracing Collector）
追蹤回收算法利用JVM維護的對象引用圖，從根節點開始遍歷對象的應用圖，同時標記遍歷到的對象，當遍歷結束后，未被標記的對象就是目前已不被使用的對象，可以回收。
（3）壓縮回收算法（Compacting Collector）
壓縮回收算法的思路如下：把堆中活動的對象移動到堆中一端，這樣就會在堆中另外一端留出很大的一塊空閑區間，相當于對堆中的碎片進行了處理。雖然這種方法可以大大消除堆碎片的工作，但是每次處理都會帶來性能的損失。
（4）復制回收算法（Coping Collector）
復制回收算法的思路：把堆分為倆個大小相同的區域，在任何時刻，只有其中一個區域被使用，直到這個區域被消耗完為止，此時垃圾回收期就會中斷程序的執行，通過遍歷的方式把所有活動的對象復制到另外一個區域中，在復制的過程中它們是緊挨著布置的，從而可以消除內存碎片。當復制過程結束后程序會接著運行，知道這塊區域被使用完，然后再采用上面的方法繼續進行垃圾回收。
（5）按代回收算法（Generational Collector）
復制回收算法主要的缺點如下：每次算法執行時，所有出于活動狀態的對象都要被復制，這樣效率很低。由于程序有生命周期長短之分而大部分都是生命周期比較短的，因此可以根據這個特點對算法進行優化。按代回收算法的主要思路如下：把堆分為倆個或多個子堆，每一個子堆被視為一代。算法在運行的過程中優先收集那些“年幼”的對象，如果一個對象經過多次收集仍然“存活”，那么就可以把這個對象轉移到高一級的堆里，減少對其的掃描次數。想要了解更多的java應用技術那就加入我們吧！