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

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

數組：查詢快，增刪慢

鏈表：查詢慢，增刪快

2、鏈表

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

一個鏈表包括頭結點、普通結點、尾結點

頭結點內含：size（鏈表長度）、first（頭指針）?

其他結點內含：element（內容）、next（指向下一結點的指針，其中尾結點指針值為null）

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

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

clear()

首先要讓size等于0

只需要將頭結點的指針指向空即可

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

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

查找對應位置的結點?

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

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

add(int index, E element)

先令要插入的結點指向插入位置原結點

再令前一個結點指向新插入的這個結點

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

remove(int index)

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

public E remove(int index){   //返回刪除位置原來的內容
    Nodenode = first;
    if(index == 0){
        first = first.next;
    }else{
        Nodeprev = new node(index - 1);   //找到前一個結點
        node = prev.next;   //node就是要刪除的結點
        prev.next = node.next;   //前一個結點連接后一個結點，刪除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;
}

虛擬頭結點

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

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

//構造函數，內含虛擬頭結點的定義
public linklist(){
    first = new Node<>(null,null); 
}

雙向鏈表

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文標題：java鏈表-創(chuàng)新互聯
瀏覽地址：http://www.rwnh.cn/article44/doshhe.html

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

廣告

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