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

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

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

鏈表：查詢慢，增刪快

2、鏈表

鏈表是一種鏈?zhǔn)酱鎯?chǔ)的線性表，地址不一定是連續(xù)的

一個(gè)鏈表包括頭結(jié)點(diǎn)、普通結(jié)點(diǎn)、尾結(jié)點(diǎn)

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

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

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

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

clear()

首先要讓size等于0

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

其他結(jié)點(diǎn)沒(méi)有頭指針連接，會(huì)被自動(dòng)回收，因此不需要管其他的結(jié)點(diǎn)

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

查找對(duì)應(yīng)位置的結(jié)點(diǎn)?

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

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

add(int index, E element)

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

再令前一個(gè)結(jié)點(diǎn)指向新插入的這個(gè)結(jié)點(diǎn)

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

remove(int index)

令刪除位置前一個(gè)結(jié)點(diǎn)的指針指向index+1，刪除位置結(jié)點(diǎn)被斷開(kāi)后自動(dòng)垃圾回收

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

indexOf(E element)

通過(guò)循環(huán)，找到對(duì)應(yīng)元素的位置

public int indexOf(E element) {
	if (element == null) {  //空元素單獨(dú)設(shè)條件
		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é)點(diǎn)

上述功能基本都會(huì)將index=0的情況單獨(dú)列出來(lái)，為了精簡(jiǎn)這些代碼，我們?cè)谠^結(jié)點(diǎn)前設(shè)一個(gè)新的頭結(jié)點(diǎn)，叫虛擬頭結(jié)點(diǎn)

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

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

雙向鏈表

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

文章名稱：java鏈表-創(chuàng)新互聯(lián)
網(wǎng)頁(yè)路徑：http://weahome.cn/article/doshhe.html