JAVA連結清單實作與連結清單的逆序

1.連結清單

        連結清單有單連結清單還有雙向連結清單，在java中每個節點都是一個類，這裡聲明了内部類，為了友善插入和删除，有時會在，連結清單的表頭加上哨兵（形成有哨兵的循環或雙向循環連結清單），這樣的插入删除就不用考慮當插入删除的元素在邊界的情況，友善，至于哨兵你可能覺得沒什麼用，其實他可以存儲連結清單的許多資訊，比如你每次查找一個元素，在無哨兵時，使用P！=null，使用哨兵，可以存儲要查找的元素，退出時，就要判斷是不是哨兵。

2.連結清單的實作與逆序

  若想代碼寫得快，必須清楚每次交換插入，産生的狀态和性質。在寫代碼時，一個節點指錯了下一個節點，導緻調了好長時間，一定要想清楚每次變換的狀态結果。下面使用了兩種方法實作，連結清單的逆序，這兩個思路都是插入排序的思想，隻是疊代反向不同。

思路一：從第n-1個元素開始向前疊代，一次插入到連結清單結尾，在為雙向連結清單并且含有尾節點時，時間複雜度為：n，在當連結清單為 n的平方。因為還要查找節點。

思路二：從第2-n個節點一次向後疊代，插入到head節點位置，一次向後就能每次使用next儲存下一次要插入的元素，一路走來，不用查找節點。

同樣的思路不同的方向，向前面插向後面插，雙向思考。

代碼如下：

class List<T> {
	private static class Node<T>{
		private T key;
		Node<T> next;
		public Node(T key,Node<T> next)
		{
			this.key=key;
			this.next=next;
		}
	}
	private int size;
	private Node<T> head;
	public List(){
		size=0;
		head=null;
	}
	public int size()
	{
		return size;
	}
	public boolean isEmpty()
	{
		if(size==0)
			return true;
		else
			return false;
	}
	public void insert(T key)
	{
		head=new Node<T>(key,head);
		size++;
	}
	public T front()
	{
		return  head.key;
	}
	public T get(int index)
	{
		if(index>=size||index<0)
			return null;
		int i=0;
		Node<T>p=head;
		while(i++<index)
			p=p.next;
		return p.key;
	}
	public T delete(){
		T x=head.key;
		head = head.next;
		size--;
		return x;
	}
	public void delete(T key){
		Node<T>node=searchNode(key);
		if(node==null)
			return ;
		
		if(size==1)
			head=null;
		else
		{
		    Node<T>pre=head;
		    while(pre.next!=null&&pre.next!=node)
			pre=pre.next;
		    pre.next=node.next;
		}
		size--;
	}
	public Node<T> searchNode(T key)
	{
		Node<T> p= head;
		int i=0;
		while(p!=null&&p.key!=key)
			p=p.next;
		return p;
	}
	public int searchIndex(T x)
	{
		Node<T> p= head;
		int i=0;
		
		while(p!=null&&p.key!=x)
		{
			i++;
			p=p.next;
			
		}
		if(p!=null)
		return i;
		return -1;
	}
	public Node<T> getNode(int index)
	{
		if(index<0&&index>=size)
			return null;
		int i=0;
		Node<T>p=head;
		while(i++<index)
			p=p.next;
		return p;
	}
	/**
	 * 求連結清單的逆序  注意一定要連結節點時 連接配接對
	 * 思路一：這個比較麻煩：是把前面的元素從後向前一次放在連結清單結尾
	 * 還要查找元素節點，查找過程為n是以時間複雜度已經為 ：n的平方 了
	 */
	public void reverse(){
		if(size<=1)
			return ;
		int i=size-2;
		Node<T>tail=getNode(size-1);
		while(i>=0)
		{
             Node<T>e=getNode(i);
             if(e!=head)
             {
            	 Node<T>pre=getNode(i-1);
                 tail.next=e;
                 pre.next=e.next;
                 tail=e;
                 tail.next=null;
             }
             else 
             {
            	 tail.next=head;
            	 tail=head;
            	 head=head.next;
            	 tail.next=null;
             }
             i--;
		}
	}
	
	/**
	 * 思路二： 從後面像最前面插入，插入排序的思想
	 */
	public void reverse2()
	{
		if(size<=1)
			return ;
		int i=1;
		Node<T>pre,insertNode,next;
		pre=head;
		next=head.next;//每個要插入元素的頭結點都是最初的頭結點
		while(i++<size)
		{
			insertNode=next;
			if(next.next!=null)
			next=next.next;
            pre.next=insertNode.next;  			
			insertNode.next=head;
			head=insertNode;
		}
		
	}
/* 思路三 ：借助輔助空間，叢原連結清單拿出 重新建構  簡單
 Node* reverse(Node* head)
{
    Node* current = head;
    Node* reversList = null;
     
    while(current)
    {
           /*将目前節點取出原連結清單迅速改變current(即current取出!!!注
                意這是 一個指派操作，指派完後current改變了，p還是沒變!!!)*/
        Node *p = current;  
        current = current->next; 
 
        p->next = reversList;        
        reverseList = p;
    }
 
    return reverseList;
}*/
 /*使用java的值傳遞，是複制了一份引用的副本，不是原來的引用
	 * ，雖然指向相同，這樣是不能把連結清單轉換為逆序的
	 * public void swap(Node<T>head)
	
	{
		if(head.next!=null)
		{
			Node<T>p=head;
			swap(p.next);
			T key=head.key;
			while(p!=null)
				p=p.next;
			p.next=head;
			head=p.next;
		}
		
	}*/
}
public class SingleList {
    public static  void main(String args[])
    {
    	List<Integer> list=new List<Integer>();
    	list.insert(1);
    	list.insert(2);
    	list.insert(3);
    	list.insert(4);
    	list.insert(5);
    	list.reverse2();
    	System.out.println(list.get(0)+" "+list.get(1)+" "+list.get(2)+" "+list.get(3)+" "+list.get(4)+" ");
    }
}