下面整理數(shù)據(jù)結構中的鏈表（主要是用java寫的代碼）

一、什么是鏈表

　　1、首先理解鏈表的節(jié)點概念

　　個人理解：鏈表節(jié)點，包含一個數(shù)據(jù)和一個內(nèi)存地址，內(nèi)存地址指向下一個同樣類型的鏈表節(jié)點，這樣說有種繞起來了像遞歸的感覺（不過鏈表和遞歸還是有點類似的：自己指向自己，不斷積累），具體可以看下圖：

ok,上圖也差不多表現(xiàn)了鏈表節(jié)點的一個抽象結構了，而具體的代碼表示也很簡單：數(shù)據(jù)+引用即可:下面以int為說明例子

public class LinkSingleIntNode {
    public int data = 0;
    public LinkSingleIntNode next = null;
    public LinkSingleIntNode(){
        
    }
    public LinkSingleIntNode(int data){
        this.data = data;
    }
}

2、鏈表

　　上面的圖也說明了鏈表的具體結構了，這里不累贅；其實鏈表就是各個節(jié)點連接起來的結果集，通常會存儲一個手節(jié)點的內(nèi)存地址作為鏈表的具體引用，所以，鏈表的構造可以參考一下代碼：

public class LinkSingleInt {

    public static void main(String[] args) throws SecurityException, IllegalArgumentException, InstantiationException, IllegalAccessException, NoSuchMethodException, InvocationTargetException {
        // TODO Auto-generated method stub
        //隨機生成十個數(shù)進行測試
        LinkSingleInt link = new LinkSingleInt();
        LinkSingleIntNode node = null;
        int length = 10;
        for(int i = 0;i<length;i++){
            link.addNode(new LinkSingleIntNode((int)(Math.random() * 10)));
        }
        //遍歷
        ArrayList<Integer> list = link.findAll();
        int test;
    }
    //鏈表長度
    public int size = 0;
    public LinkSingleIntNode linkHead = null;
    public LinkSingleIntNode linkTail = null;
    
    //構造函數(shù)
    public LinkSingleInt(){
        linkHead = new LinkSingleIntNode();
        linkTail = linkHead;
    }
    //增加節(jié)點
    public  boolean addNode(LinkSingleIntNode node){
        boolean rtn = false;
        linkTail.next = node;
        linkTail = node;
        size++;
        rtn = true;
        return rtn;
    }
}

這個是簡單版的鏈表實現(xiàn)，通常來說，為了提高每個方法操作鏈表的平均運行時間（即用內(nèi)存換區(qū)時間），會將一些必要數(shù)據(jù)存儲在鏈表類中：例如本例中的size變量存儲了鏈表的長度。具體的設計其實還需要參考業(yè)務需求。

3、鏈表的刪除操作示意圖

具體實現(xiàn)方式看代碼：

//刪除節(jié)點（這里是針對雙向鏈表的來實現(xiàn)）
	public  boolean deleteNode(LinkSingleIntNode node){
		//判斷是否為null
		if(node==null){
			//可以在檢測到null的時候拋出異常
			throw new RuntimeException("失敗，node參數(shù)為null");
		}
		if(node.equals(linkHead)){
			//首節(jié)點，直接刪除
			linkHead = node.next;
			node.next=null;
			size--;//改變鏈表長度
			return true;
		}
		//判斷是否是最后一個節(jié)點，如果是，相應的改變tail的值（這里我的實現(xiàn)類存儲了tail的值，所以要改變尾端的值）
		if(node.equals(linkTail)){
			linkTail = node.prev;
			node = null;
			size--;//改變鏈表長度
			return true;
		}
		//其他情形直接刪除
		LinkSingleIntNode nodePrev = node.prev;//同理，存儲刪除節(jié)點的上一個節(jié)點
		nodePrev.next = node.next;
		node=null;
		size--;
		return true;
	}

　4、鏈表的增加操作

　　鏈表的增加操作從直觀上來說也挺簡單的，和刪除操作類似，具體就不上圖啦，看代碼吧

//增加節(jié)點（直接鏈表末增加，默認）
	public  boolean addNode(LinkSingleIntNode node){
		boolean rtn = false;
		linkTail.next = node;
		linkTail = node;
		size++;
		rtn = true;
		return rtn;
	}
	//在中間某個元素之后增加
	public boolean addNodeAfterAnyNode(LinkSingleIntNode nodeAdd,LinkSingleIntNode nodeAny){
		//先存儲標記節(jié)點的后一個節(jié)點以及前一個節(jié)點
		if(nodeAny==null){
			throw new RuntimeException("錯誤，nodeAdd為null");
		}
		if(nodeAny.next==null){
			return addNode(nodeAdd);//如果是最后一個元素直接調(diào)用默認的add方法
		}
		LinkSingleIntNode nodeBetw = nodeAny.next;
		nodeAny.next = nodeAdd;
		nodeAdd.next = nodeBetw;
		return true;
	}

　　

下面貼上完整版的鏈表類（擴展其他方法，代碼太長不想看直接跳過啦，畢竟，這種沒什么技術含量的代碼貼上來只是為了博客文章的完整性 而已，其實對理解鏈表并沒有什么卵用處）

public class LinkSingleInt {

    public static void main(String[] args) throws SecurityException, IllegalArgumentException, InstantiationException, IllegalAccessException, NoSuchMethodException, InvocationTargetException {
        // TODO Auto-generated method stub
        //隨機生成十個數(shù)進行測試
        LinkSingleInt link = new LinkSingleInt();
        LinkSingleIntNode node = null;
        int length = 10;
        for(int i = 0;i<length;i++){
            link.addNode(new LinkSingleIntNode((int)(Math.random() * 10)));
        }
        //遍歷
        ArrayList<Integer> list = link.findAll();
        int test;
    }
    //鏈表長度
    public int size = 0;
    public LinkSingleIntNode linkHead = null;
    public LinkSingleIntNode linkTail = null;
    
    //構造函數(shù)
    public LinkSingleInt(){
        linkHead = new LinkSingleIntNode();
        linkTail = linkHead;
    }
    //增加節(jié)點
    public  boolean addNode(LinkSingleIntNode node){
        boolean rtn = false;
        linkTail.next = node;
        linkTail = node;
        size++;
        rtn = true;
        return rtn;
    }
    //刪除節(jié)點（待定）
    public  boolean deleteNode(LinkSingleIntNode node){
        boolean rtn = false;
        LinkSingleIntNode nodeBetw = linkHead.next;
        LinkSingleIntNode nodePrev = linkHead;
        while(nodeBetw!=null){
            if(nodeBetw.equals(node)){
                //判斷是否是最后一個節(jié)點，如果是，相應的改變tail的值
                if(nodeBetw.equals(linkTail)){
                    linkTail = nodePrev;
                }else{
                    nodeBetw = nodeBetw.next;
                }
                size--;
                rtn =  true;
                break;
            }else{
                nodePrev = nodeBetw;
                nodeBetw = nodeBetw.next;
            }
        }
        
        return rtn;
    }
    //判斷某個節(jié)點是否在鏈表中
    public  boolean judgeNode(LinkSingleIntNode node){
        boolean rtn = false;
        LinkSingleIntNode nodeJudge = linkHead;
        while(nodeJudge!=null){
            if(nodeJudge.equals(linkHead.next)){
                rtn =  true;
                break;
            }else{
                linkHead = linkHead.next;
            }
        }
        return rtn;
    }
    //遍歷
    public  ArrayList<Integer> findAll(){
        ArrayList<Integer> rtn = new ArrayList<Integer>();
        LinkSingleIntNode nodeJudge = linkHead.next;
        while(nodeJudge!=null){
            rtn.add(nodeJudge.data);
            nodeJudge = nodeJudge.next;
        }
        return rtn;
        
    }
}

View Code

二、鏈表的種類

　　1、單向鏈表：字面就可以理解：鏈表的操作只能沿一個方向進行。不多解釋

　　2、雙向量表。可前可后遍歷，其實就是在鏈表節(jié)點中新增多一個指針變量，將該指針指向上一個元素，可以方便鏈表操作，但是空間存儲變大，典型的空間換時間類型擴展。還是上個丑圖

好吧，可能你會說圖有點丑（別在意這些細節(jié)好吧），雙向指針只是多了個回指引用，指向了上一個對象。

恩，還是廢話不多說，上坨代碼直接點吧

//好吧，我承認這個類名取得有點歧義，其實double不是double類型，他表示雙個的意思（英語不好怪我咯）
public class LinkDoubleIntNode {

	
	public int data = 0;
	public LinkDoubleIntNode next = null;
	public LinkDoubleIntNode prev = null;//雙向鏈表和單項鏈表并沒有什么卵本質區(qū)別，不過多了一個指向上一個節(jié)點的引用罷了
	public LinkDoubleIntNode(){
		
	}
	public LinkDoubleIntNode(int data){
		this.data = data;
	}
}

3、還有種鏈表，叫做環(huán)裝鏈表，其實就是最后節(jié)點的引用指針指向首位而已，不過這種鏈表，感覺好像挺少用的，畢竟環(huán)狀和非環(huán)裝也沒什么本質區(qū)別。具體代代碼什么的就不上了，上個小丑圖吧　

　

4、好像貌似還有什么三指向的鏈表，omg,太難了，其實在我看來過于復雜的鏈表結構一般不會常用（可能這個時候已經(jīng)不叫鏈表了，已經(jīng)是類似于樹或者圖了，好吧，話有點多了）

三、鏈表特點

　　1、鏈表VS數(shù)組：鏈表其實是一種非常基本的數(shù)據(jù)結構，它具有的特點是：插入刪除快，而且，他的長度是可變的，但是要找某個元素的時候就必須遍歷整個鏈表了。數(shù)組其實是反過來，長度定死，找數(shù)據(jù)塊， 額，好像插數(shù)據(jù)和刪數(shù)據(jù)也挺快的（看從哪個角度看待吧，如果說每次數(shù)據(jù)改變都要調(diào)整數(shù)組使得它緊湊的話其實是很低效的）

　　2、作用范圍。有上面的鏈表特點，我們估計也能猜到鏈表一般會用到哪了吧：插入修改刪除的操作遠遠大于查詢操作的時候考慮該使用數(shù)據(jù)結構。

總結

以上是生活随笔為你收集整理的数据结构--链表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。