動態(tài)數(shù)組與鏈表有相同部分，共用一個父類AbstracList，該父類繼承接口List

創(chuàng)新互聯(lián)專注于企業(yè)成都全網(wǎng)營銷、網(wǎng)站重做改版、潛江網(wǎng)站定制設計、自適應品牌網(wǎng)站建設、HTML5建站、成都做商城網(wǎng)站、集團公司官網(wǎng)建設、成都外貿(mào)網(wǎng)站制作、高端網(wǎng)站制作、響應式網(wǎng)頁設計等建站業(yè)務，價格優(yōu)惠性價比高，為潛江等各大城市提供網(wǎng)站開發(fā)制作服務。

數(shù)組：查詢快，增刪慢

鏈表：查詢慢，增刪快

2、鏈表

鏈表是一種鏈式存儲的線性表，地址不一定是連續(xù)的

一個鏈表包括頭結(jié)點、普通結(jié)點、尾結(jié)點

頭結(jié)點內(nèi)含：size（鏈表長度）、first（頭指針）?

其他結(jié)點內(nèi)含：element（內(nèi)容）、next（指向下一結(jié)點的指針，其中尾結(jié)點指針值為null）

頭指針供外界使用，其他指針不需要，為靜態(tài)內(nèi)部類

private static class Node{
	E element;    //內(nèi)容
	Nodeprev;   //指向前一個結(jié)點的指針
	Nodenext;    //指向下一個結(jié)點的指針
	public Node(Nodeprev, E element, Nodenext) {
		this.prev = prev;
		this.element = element;
		this.next = next;
    }
}

clear()

首先要讓size等于0

只需要將頭結(jié)點的指針指向空即可

其他結(jié)點沒有頭指針連接，會被自動回收，因此不需要管其他的結(jié)點

public void clear() {
	size = 0;
	first = null;
	last = null;
}

查找對應位置的結(jié)點?

通過觀察可以發(fā)現(xiàn)，從頭結(jié)點到目標結(jié)點使用的指針數(shù)目與該結(jié)點位置-1相同，因此可以使用for循環(huán)，定義一個指針指向頭結(jié)點地址，不斷next直到到達目標結(jié)點的地址

private Nodenode(int index){
    rangeCheck(index);    //查看index是否正常
    Nodenode = first;
    for(int i = 0; i< index; i++){
        node = node.next;   //使指針指向下一個結(jié)點地址
    }
    return node;
}

add(int index, E element)

先令要插入的結(jié)點指向插入位置原結(jié)點

再令前一個結(jié)點指向新插入的這個結(jié)點

public void add(int index, E element){
    if(index == 0){   //由于插入位置為第一個時，node(index - 1)會報錯
        first = new Node<>(element,first);
    }else{
        Nodeprev = new node(index - 1);   //原位置前一個結(jié)點為新結(jié)點的前一個結(jié)點
        prev.next = new Node<>(element,prev.next);   //創(chuàng)建新結(jié)點并將其與前后結(jié)點相連
    }
    size++;
}

remove(int index)

令刪除位置前一個結(jié)點的指針指向index+1，刪除位置結(jié)點被斷開后自動垃圾回收

public E remove(int index){   //返回刪除位置原來的內(nèi)容
    Nodenode = first;
    if(index == 0){
        first = first.next;
    }else{
        Nodeprev = new node(index - 1);   //找到前一個結(jié)點
        node = prev.next;   //node就是要刪除的結(jié)點
        prev.next = node.next;   //前一個結(jié)點連接后一個結(jié)點，刪除node
    }
    return node.element;
}

indexOf(E element)

通過循環(huán)，找到對應元素的位置

public int indexOf(E element) {
	if (element == null) {  //空元素單獨設條件
		Nodenode = first;   
		for (int i = 0; i< size; i++) {
			if (node.element == null) return i;
			node = node.next;
		}
	} else {
		Nodenode = first;
		for (int i = 0; i< size; i++) {
			if (element.equals(node.element)) return i;
			node = node.next;
		}
	}
	return -1;
}

虛擬頭結(jié)點

上述功能基本都會將index=0的情況單獨列出來，為了精簡這些代碼，我們在原頭結(jié)點前設一個新的頭結(jié)點，叫虛擬頭結(jié)點

在頭結(jié)點前另設一個頭結(jié)點，它的值為null，它被頭指針連接，且next指針指向真正的頭結(jié)點

//構(gòu)造函數(shù)，內(nèi)含虛擬頭結(jié)點的定義
public linklist(){
    first = new Node<>(null,null); 
}

雙向鏈表

擁有兩個指針：頭指針first和尾指針last，分別連接鏈表的頭部和尾部，從而讓鏈表連成一個環(huán)

每個結(jié)點又各自擁有兩個指針，一個是與單向鏈表相同的next指針，從頭指向尾的方向；另一個是prev指針，與next方向相反，從尾指向頭

因此要找某個結(jié)點，比較它的index與1/2size的大小，小于說明離頭結(jié)點比較近，用next指針，大于說明離尾結(jié)點比較近，用prev指針

雙向鏈表添加元素，不需要尋找元素前一個結(jié)點（已經(jīng)有prev指針了）

index不是0也不等于size時，順序：添加結(jié)點的next連接原為index處的結(jié)點，prev連接這個結(jié)點的前一個結(jié)點，即index-1位置的結(jié)點；后一個結(jié)點的prev連接添加結(jié)點，前一個結(jié)點的next連接添加結(jié)點

Nodenext = node(index);   //新結(jié)點的next為相應index位置的結(jié)點
Nodeprev = next.prev;   //新結(jié)點的prev連接index位置結(jié)點的前一個結(jié)點
Nodenode = new Node<>(prev,element,next);  //創(chuàng)建新結(jié)點
next.prev = node;    //新結(jié)點變成獲取結(jié)點的前一個結(jié)點，即變成了index位置的結(jié)點
prev.next = node;    //新結(jié)點再與前一個結(jié)點的next相連

index為0時：頭指針first改變，需要與添加結(jié)點相連，添加結(jié)點的prev變?yōu)閚ull，也是上述代碼中的prev = next.prev，唯一需要改動的就是prev是null時它沒有next，所以最后一句代碼進行修改：

if(next == first){
    first = node;   //新結(jié)點就是頭結(jié)點，與頭指針相連
}else{
    prev.next = node;
}

index為size時，尾指針last改變，需要與添加結(jié)點相連，添加結(jié)點的next變成null，原先的尾結(jié)點的next指向它

如果鏈表是空的，添加元素是鏈表第一個結(jié)點，last.prev不存在

if(index == size){
    Nodeoldlast = last;  //舊的尾結(jié)點
    last = new Node<>(oldlast,element,null);  //新的尾結(jié)點，它的prev指向oldlast,next指向null
    if(oldlast == null){   //如果這是第一個結(jié)點
        first = last;  //頭指針尾指針都指向新結(jié)點
        
    }else{
        oldlast.next = last;
    }
}

刪除某個結(jié)點時，由于雙向鏈表能夠輕松找到結(jié)點的前一個結(jié)點與后一個結(jié)點，所以只需要讓他們斷開（前一結(jié)點的next指向后一結(jié)點，后一結(jié)點的prev指向前一結(jié)點），再把index為0和size單獨處理即可

單向循環(huán)鏈表：與單向鏈表不同的是，它的尾結(jié)點的next指向頭結(jié)點

雙向循環(huán)鏈表：比單向循環(huán)鏈表多一個，頭結(jié)點的prev指向尾結(jié)點

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

本文標題：java鏈表-創(chuàng)新互聯(lián)
瀏覽地址：http://chinadenli.net/article44/doshhe.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供外貿(mào)建站、手機網(wǎng)站建設、網(wǎng)站策劃、靜態(tài)網(wǎng)站、搜索引擎優(yōu)化、品牌網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)