什么是鏈表？
鏈表是一種在物理上非連續(xù)，非順序的數(shù)據(jù)結(jié)構(gòu)，由若干節(jié)點(diǎn)（node）所組成。
單向鏈表的每一個(gè)節(jié)點(diǎn)包含兩個(gè)部分，一部分存放數(shù)據(jù)的變量，另一部分是指向下一個(gè)節(jié)點(diǎn)的指針。鏈表的第一個(gè)節(jié)點(diǎn)稱(chēng)為頭節(jié)點(diǎn)，最后一個(gè)節(jié)點(diǎn)稱(chēng)為尾結(jié)點(diǎn)，尾結(jié)點(diǎn)的指針指向空。與數(shù)組按照索引來(lái)隨機(jī)查找數(shù)據(jù)不同，對(duì)于鏈表的其中一個(gè)節(jié)點(diǎn)A，我們只能根據(jù)節(jié)點(diǎn)A的next指針來(lái)找到該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)B，在根據(jù)節(jié)點(diǎn)B的next指針找到一下個(gè)節(jié)點(diǎn)C，以此類(lèi)推。
那么如何找到該節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)呢？可以使用雙向鏈表。
單向鏈表存儲(chǔ)結(jié)構(gòu)如圖：
節(jié)點(diǎn)代碼如下：
/**
* 定義存儲(chǔ)數(shù)據(jù)的節(jié)點(diǎn)
*/
private class Node {
public E e;
public Node next;
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
public Node(E e) {
this(e, null);
}
public Node() {
this(null, null);
}
@Override
public String toString() {
return e.toString();
}
}
什么是雙向鏈表？
雙向鏈表比單向鏈表稍微復(fù)雜一些，它的每一個(gè)節(jié)點(diǎn)除了擁有data和next指針還包含一個(gè)指向前置節(jié)點(diǎn)的prev指針。
雙向鏈表存儲(chǔ)結(jié)構(gòu)如圖：
鏈表的實(shí)現(xiàn)
1、查找節(jié)點(diǎn)
查找元素時(shí)，鏈表不像數(shù)組那樣可以通過(guò)索引來(lái)進(jìn)行快速定位，只能從頭節(jié)點(diǎn)向后一個(gè)一個(gè)的查找。
2、更新節(jié)點(diǎn)
如果不考慮查找節(jié)點(diǎn)的過(guò)程，鏈表的更新過(guò)程非常節(jié)點(diǎn)，直接把舊數(shù)據(jù)替換成新數(shù)據(jù)即可。
3、插入節(jié)點(diǎn)
與數(shù)組類(lèi)似，鏈表插入節(jié)點(diǎn)同樣可以分為三種情況：
-
頭部插入
頭部插入，分為兩個(gè)步驟：
1、把新節(jié)點(diǎn)的next指針指向當(dāng)前頭節(jié)點(diǎn)。
2、把新節(jié)點(diǎn)變?yōu)殒湵淼念^節(jié)點(diǎn)。
-
尾部插入
尾部插入是最簡(jiǎn)單的情況，直接把尾結(jié)點(diǎn)的next執(zhí)行指向新節(jié)點(diǎn)即可。
-
中間插入
中間插入，分為兩個(gè)步驟：
1、新節(jié)點(diǎn)的next指針指向插入位置的節(jié)點(diǎn)。
2、插入位置的前置節(jié)點(diǎn)的next指針指向新節(jié)點(diǎn)。
4、刪除節(jié)點(diǎn)
同樣分為三種情況：
-
頭部刪除
把當(dāng)前鏈表的頭結(jié)點(diǎn)更新為原頭節(jié)點(diǎn)的next指針即可。
-
尾部刪除
把尾結(jié)點(diǎn)的前置節(jié)點(diǎn)的next指針指向?yàn)榭占纯伞?/p>
-
中間刪除
把要?jiǎng)h除的前置節(jié)點(diǎn)的next指針指向要?jiǎng)h除節(jié)點(diǎn)的next指針即可。
整體代碼如下：
/**
* 描述：鏈表。
* <p>
* Create By ZhangBiao
* 2020/5/11
*/
public class LinkedList<E> {
/**
* 虛擬頭結(jié)點(diǎn)
*/
private Node dummyHead;
private int size;
public LinkedList() {
this.dummyHead = new Node(null, null);
this.size = 0;
}
/**
* 獲取鏈表中的元素個(gè)數(shù)。
*
* @return
*/
public int getSize() {
return size;
}
/**
* 返回鏈表是否為空。
*
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 在鏈表的index(0-based)位置添加新的元素e，在鏈表中不是一個(gè)常用的操作，當(dāng)做練習(xí)。
*
* @param index
* @param e
*/
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed. Illegal index.");
}
Node prev = dummyHead;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
prev.next = new Node(e, prev.next);
size++;
}
/**
* 在鏈表頭添加新的元素e。
*
* @param e
*/
public void addFirst(E e) {
add(0, e);
}
/**
* 在鏈表末尾添加新的元素e。
*
* @param e
*/
public void addLast(E e) {
add(size, e);
}
/**
* 獲得鏈表的第index(0-based)個(gè)位置的元素。
* 在鏈表中不是一個(gè)常用的操作，當(dāng)做練習(xí)用。
*
* @param index
* @return
*/
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Get failed. Illegal index.");
}
Node cur = dummyHead.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur.e;
}
/**
* 獲得鏈表的第一個(gè)元素。
*
* @return
*/
public E getFirst() {
return get(0);
}
/**
* 獲得鏈表的最后一個(gè)元素。
*
* @return
*/
public E getLast() {
return get(size - 1);
}
/**
* 修改鏈表的第index(0-based)個(gè)位置的元素為e。
* 在鏈表中不是一個(gè)常用的操作，當(dāng)做練習(xí)用。
*
* @param index
* @param e
*/
public void set(int index, E e) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Set failed. Illegal index.");
}
Node cur = dummyHead.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
cur.e = e;
}
/**
* 查找鏈表中是否有元素e。
*
* @param e
* @return
*/
public boolean contains(E e) {
Node cur = dummyHead.next;
while (cur != null) {
if (cur.e.equals(e)) {
return true;
}
cur = cur.next;
}
return false;
}
/**
* 從鏈表中刪除index(0-based)位置的元素并返回刪除的元素。
*
* @param index
* @return
*/
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Remove failed. Index is illegal.");
}
Node prev = dummyHead;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
Node retNode = prev.next;
prev.next = retNode.next;
retNode.next = null;
size--;
return retNode.e;
}
/**
* 從鏈表中刪除第一個(gè)元素并返回刪除的元素。
*
* @return
*/
public E removeFirst() {
return remove(0);
}
/**
* 從鏈表中刪除最后一個(gè)元素并返回刪除的元素。
*
* @return
*/
public E removeLast() {
return remove(size - 1);
}
/**
* 從鏈表中刪除元素e
*
* @param e
*/
public void removeElement(E e) {
Node prev = dummyHead;
while (prev.next != null) {
if (prev.next.e.equals(e)) {
break;
}
prev = prev.next;
}
if (prev.next != null) {
Node delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
size--;
}
}
@Override
public String toString() {
StringBuilder result = new StringBuilder();
/*Node cur = dummyHead.next;
while (cur != null) {
result.append(cur + " -> ");
cur = cur.next;
}*/
for (Node cur = dummyHead.next; cur != null; cur = cur.next) {
result.append(cur + " -> ");
}
result.append("NULL");
return result.toString();
}
/**
* 定義存儲(chǔ)數(shù)據(jù)的節(jié)點(diǎn)
*/
private class Node {
public E e;
public Node next;
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
public Node(E e) {
this(e, null);
}
public Node() {
this(null, null);
}
@Override
public String toString() {
return e.toString();
}
}
}
在這里我使用了虛擬頭結(jié)點(diǎn)，為什么使用虛擬頭結(jié)點(diǎn)？
在添加元素的過(guò)程中遇到一個(gè)問(wèn)題：現(xiàn)在要在任意位置上添加一個(gè)元素，在鏈表頭添加元素與在其他位置邏輯會(huì)有差別，那么為什么在鏈表頭添加元素比較特殊呢？這是因?yàn)槲覀優(yōu)殒湵硖砑釉氐倪^(guò)程要找到待添加元素位置的前置節(jié)點(diǎn)，但是由于對(duì)于鏈表頭來(lái)說(shuō)，它沒(méi)有前置節(jié)點(diǎn)，所以在邏輯上就比較特殊一些，解決方式也比較簡(jiǎn)單，我們的核心問(wèn)題不就是鏈表頭它沒(méi)有前置節(jié)點(diǎn)嘛，那么我們就可以造一個(gè)鏈表頭的前置節(jié)點(diǎn)，對(duì)于這個(gè)前置節(jié)點(diǎn)，他不存儲(chǔ)任何的元素，這樣一來(lái)，對(duì)于我們的鏈表來(lái)說(shuō)，它第一個(gè)元素就是虛擬頭結(jié)點(diǎn)的next所對(duì)應(yīng)的那個(gè)元素，而不是虛擬頭結(jié)點(diǎn)。注意：==虛擬頭節(jié)點(diǎn)的那個(gè)元素是根本不存在的，對(duì)于用戶(hù)來(lái)講也是沒(méi)有意義的，這只是為了我們編寫(xiě)邏輯方便而出現(xiàn)的虛擬頭節(jié)點(diǎn)==。
添加虛擬頭節(jié)點(diǎn)后的存儲(chǔ)結(jié)構(gòu)如圖：
鏈表的優(yōu)劣勢(shì)
1、優(yōu)點(diǎn)
真正動(dòng)態(tài)，不需要處理固定容量的問(wèn)題。
2、缺點(diǎn)
喪失隨機(jī)訪問(wèn)能力。
