鏈表通過(guò)指針將零散的數(shù)據(jù)塊連接在一起，這些內(nèi)存塊被稱(chēng)為節(jié)點(diǎn)（Node）。通常每個(gè)節(jié)點(diǎn)除了儲(chǔ)存數(shù)據(jù)之外還記錄下一個(gè)節(jié)點(diǎn)的地址。
//Node類(lèi)是LinkedList類(lèi)的內(nèi)部類(lèi)裁着，泛型E定義在LinkedList上
class Node {
E e; //數(shù)據(jù)域
Node next; //下一個(gè)節(jié)點(diǎn)
Node() {
this(null, null);
}
Node(E e) {
this(e, null);
}
Node(E e, Node next) {
this.e = e;
this.next = next;
}
}
與數(shù)組相比，數(shù)組的存儲(chǔ)空間是連續(xù)的拱她。因此為了保證數(shù)組的存儲(chǔ)空間的連續(xù)性二驰，需要搬移節(jié)點(diǎn)。而鏈表的各個(gè)節(jié)點(diǎn)是由指針串聯(lián)起來(lái)的秉沼，插入和刪除時(shí)只需維護(hù)指針即可桶雀，這樣的時(shí)間復(fù)雜度為O(1)。
單鏈表LinkedList
設(shè)置虛擬頭結(jié)點(diǎn)（哨兵）方便實(shí)現(xiàn)統(tǒng)一的邏輯代碼唬复，哨兵節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)矗积。無(wú)論鏈表是否為空，head指針都會(huì)指向它敞咧，作為鏈表的頭結(jié)點(diǎn)始終存在棘捣。下面是LinkedList的兩個(gè)成員變量
private Node dummyHead; //哨兵
private int size;
//構(gòu)造器初始化
public LinkedList() {
dummyHead = new Node();
size = 0;
}
鏈表的重要操作
-
add(int index, E e):在index位置插入元素epublic viod add(int index, E e) { Node prev = dummyHead; //指針移動(dòng)到目標(biāo)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)上 for(int i = 0; i < index; i ++) { prev = prev.next; } //修改指針的指向 //Node newNode = new Node(e); //newNode.next = prev.next; //prev.next = newNode; //上面的三行合并成一行 prev.next = new Node(e, prev.next); size ++; } -
removeElement(E e)：移除指定的元素epublic void removeElement(E e) { Node prev = dummyHead; while(prev.next != null) { if(prev.next.e.equals(e)) { //在找到目標(biāo)元素的前一個(gè)節(jié)點(diǎn)處停止 break; } prev = prev.next; } if(prev.next != null) { prev.next = prev.next.next; } } -
remove(int index)：移除指定位置上的元素，并返回該元素public E remove(int index) { Node prev = dummyHead; //在找到目標(biāo)元素的前一個(gè)節(jié)點(diǎn)處停止 for(int i = 0; i < index; i ++) { prev = prev.next; } //記錄節(jié)點(diǎn)休建，用于返回 Node retNode = prev.next; //修改指針 prev.next = retNode.next; //銷(xiāo)毀被刪元素 retNode.next = null; size --; return retNode.e; }
