鏈表
鏈表還分為單向鏈表和雙向鏈表, 但是這篇文章只說單向鏈表 , 下次再講雙向鏈表 .
鏈表和數(shù)組的區(qū)別 ?
鏈表和數(shù)組在內(nèi)存中的區(qū)別在于 , 數(shù)組的每一個元素的地址是連續(xù)的 , 而鏈表的元素地址是可以不連續(xù)的 .關(guān)于數(shù)組 , 后面的文章也會講到的 .
鏈表的元素,怎么構(gòu)成一個整體 ?
上面說了 , 數(shù)組因為元素地址連續(xù) , 有了起始地址和數(shù)組長度 , 很方便就構(gòu)成了一個數(shù)組結(jié)構(gòu) .
那鏈表的元素地址不連續(xù) , 怎么搞 ?
鏈表內(nèi)部 , 每一個元素 , 我們稱為一個節(jié)點 (Node) , 沒一個節(jié)點內(nèi)部有兩個屬性 , 一個屬性用來存儲當(dāng)前節(jié)點的信息 (item) , 另一個屬性則用來存儲下一個節(jié)點的對象的引用 (next) , 這就相當(dāng)于存儲了下一個節(jié)點的地址 . 所以說,鏈表的最后一個元素的 next 屬性為 null .
方法列表
-
add(Item item): 添加元素 . -
get(int index): 獲取相應(yīng)索引位置的元素 . -
isEmpty(): 判斷鏈表是否為空 . -
size(): 返回鏈表長度 . -
remove(Item item): 刪除指定的元素 .
Item 是 java 的泛型類型 .
代碼實現(xiàn)
Node 節(jié)點對象
private class Node {
public Item item = null;
public Node next = null;
public Node(Item item) {
this.item = item;
}
}
add(Item item)
public void add(Item item) {
Node node = new Node(item);
if (this.length == 0) {
this.head = node;
} else {
Node current = this.head;
while (current.next != null) {
current = current.next;
}
current.next = node;
}
this.length++;
}
首先判斷鏈表長度是否為零 , 為 0 就直接把新節(jié)點設(shè)為 head , 如果不為零 , 就遍歷到最后一個節(jié)點 , 并把最后一個節(jié)點的next屬性指向新節(jié)點 .
get(int index)
public Item get(int index) {
Node current = this.head;
int i = 0;
while (i <= index) {
current = current.next;
i++;
}
return current.item;
}
遍歷鏈表 , 如果給定的索引值超出了鏈表最大索引 , 會直接報錯 .
isEmpty()
public boolean isEmpty() {
return this.length == 0;
}
判斷鏈表是否為空 , 直接判斷鏈表長度是否為 0 就可以了 .
size()
public int size(){
return this.length;
}
獲取鏈表長度 , 返回length屬性 .
remove(Item item)
public boolean remove(Item item) {
if (this.head.item != item) {
Node current = this.head;
while (current.next != null) {
if (current.next.item == item) {
current.next = current.next.next;
this.length--;
return true;
}
current = current.next;
}
return false;
}
this.head = this.head.next;
this.length--;
return true;
}
遍歷鏈表 , 每一個鏈表元素的item屬性和給定的item值相比較 , 如果相等 , 將current的上一個元素的next屬性指向current的下一個元素的引用 .
OK! 鏈表 , 到這里就結(jié)束了!!!
