【原】352,，數(shù)據(jù)結(jié)構(gòu)-2,鏈表

數(shù)據(jù)結(jié)構(gòu)和算法 2023-06-10 發(fā)布于上海

展開全文

基礎(chǔ)知識

鏈表是一種物理存儲單元上非連續(xù)的一種數(shù)據(jù)結(jié)構(gòu),，看名字我們就知道他是一種鏈?zhǔn)降慕Y(jié)構(gòu)，就像一群人手牽著手一樣,。鏈表有單向的,，雙向的，還有環(huán)形的,。

1,，單向鏈表

我們先定義一個(gè)最簡單的單向鏈表結(jié)點(diǎn)類

1class Node<E> {
2    E data;
3    Node<E> next;
4
5    Node(E data, Node<E> next) {
6        this.data = data;
7        this.next = next;
8    }
9}

這個(gè)類非常簡單，他只有兩個(gè)變量,，一個(gè)是data值,，一個(gè)是指向下一個(gè)結(jié)點(diǎn)的指針。我們先來看一下單向的鏈表是什么樣的,，

鏈表頭是不存儲任何數(shù)據(jù)的,，他只有指向下一個(gè)結(jié)點(diǎn)的指針，當(dāng)然如果我們不需要頭結(jié)點(diǎn),，直接拿第一個(gè)結(jié)點(diǎn)當(dāng)做頭結(jié)點(diǎn)也是可以的,，像下面這樣

單向鏈表的增刪

鏈表不像數(shù)組那樣,，可以通過索引來獲取,，單向鏈表查找的時(shí)候必須從頭開始往后一個(gè)個(gè)找，而不能從中間找,，也不能從后往前找,。我們來看一下鏈表的添加

1，添加到尾結(jié)點(diǎn)

添加到尾結(jié)點(diǎn)比較簡單,，我們只需要找到之前鏈表的尾結(jié)點(diǎn),，然后讓他的next指針指向新的結(jié)點(diǎn)即可。

2,，添加到中間結(jié)點(diǎn)

添加到中間結(jié)點(diǎn),，分為兩步，比如我們要在ab結(jié)點(diǎn)之間添加新結(jié)點(diǎn)n,，第一步讓新結(jié)點(diǎn)n的指針指向b,，然后再讓a的指針指向新結(jié)點(diǎn)n即可,。

3，刪除鏈表的尾結(jié)點(diǎn)

只需要讓尾結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)的指針指向null即可,。

4,，刪除鏈表的中間結(jié)點(diǎn)

只需要把要?jiǎng)h除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的指針指向要?jiǎng)h除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)即可，最好還要把要?jiǎng)h除結(jié)點(diǎn)的數(shù)據(jù)清空,，并且讓他的指針指向null,。

2，單向環(huán)形鏈表

環(huán)形鏈表一般分為兩種,，一種是單向環(huán)形鏈表,，一種是雙向環(huán)形鏈表。我們首先來看一下單向的環(huán)形鏈表是什么樣的

他和單向非環(huán)形鏈表的區(qū)就是,，單向非環(huán)形鏈表的尾結(jié)點(diǎn)的指針是指向null的,，而環(huán)形的是指向頭結(jié)點(diǎn)。關(guān)于他的增刪和單向非環(huán)形的差不多,，只不過在尾結(jié)點(diǎn)的時(shí)候會(huì)有點(diǎn)區(qū)別,，我們主要來看下這兩種

1，添加到尾結(jié)點(diǎn)

2,，刪除尾結(jié)點(diǎn)

3,，雙向鏈表

我們來定義一個(gè)雙向鏈表結(jié)點(diǎn)的類

 1class Node<E> {
 2    E data;
 3    Node<E> next;
 4    Node<E> prev;
 5
 6    Node(Node<E> prev, E data, Node<E> next) {
 7        this.data = data;
 8        this.next = next;
 9        this.prev = prev;
10    }
11}

雙向鏈表不光有指向下一個(gè)結(jié)點(diǎn)的指針，而且還有指向上一個(gè)結(jié)點(diǎn)的指針,，他比單向鏈表多了一個(gè)指向前一個(gè)結(jié)點(diǎn)的指針,，單向鏈表我們只能從前往后找，而雙向鏈表我們不光可以從前往后找,，而且還可以從后往前找,。我們來看一下雙向鏈表是什么樣的。

雙向鏈表我們可以從頭到尾查找,，也可以從尾到頭查找,，雙向鏈表在代碼中最常見的就是LinkedList了（java語言），雙向鏈表的增刪和單向鏈表的增刪很類似,，只不過雙向鏈表不光要調(diào)整他指向的下一個(gè)結(jié)點(diǎn),，還要調(diào)整他指向的上一個(gè)結(jié)點(diǎn)。這里我們來結(jié)合圖形和代碼的方式來分析一下雙向鏈表的增刪,。

1,，添加到尾結(jié)點(diǎn)

我們結(jié)合著代碼來看下

 1void linkLast(Object e) {
 2    final Node<Object> last = tail;
 3    final Node<Object> newNode = new Node<>(last, e, null);
 4    tail = newNode;
 5    if (last == null)
 6        head = newNode;
 7    else
 8        last.next = newNode;
 9    size++;
10}

總共分為4步

2，添加到頭結(jié)點(diǎn)

 1private void linkFirst(Object e) {
 2    //用臨時(shí)變量firt保存head結(jié)點(diǎn)
 3    final Node<Object> first = head;
 4    //創(chuàng)建一個(gè)新的結(jié)點(diǎn),，讓他的pre指針指向null,，next指針指向head結(jié)點(diǎn)
 5    final Node<Object> newNode = new Node<>(null, e, first);
 6    //讓head指向新的結(jié)點(diǎn)
 7    head = newNode;
 8    //如果之前的first為空，說明之前鏈表是空的，讓head和tial同時(shí)指向新結(jié)點(diǎn)即可
 9    if (first == null)
10        tail = newNode;
11    else//如果之前鏈表不為空,，讓之前first結(jié)點(diǎn)的pre指向新的結(jié)點(diǎn)
12        first.prev = newNode;
13    size++;
14}

添加到頭結(jié)點(diǎn)和添加到尾結(jié)點(diǎn)很類似,，圖就不在畫了，大家可以看下上面的代碼,。

3,，添加到指定結(jié)點(diǎn)之前

比如我們在a結(jié)點(diǎn)之前添加一個(gè)指定的結(jié)點(diǎn)，先來看下代碼

 1void linkBefore(Object e, Node<Object> a) {
 2    final Node<Object> pred = a.prev;
 3    final Node<Object> newNode = new Node<>(pred, e, a);
 4    a.prev = newNode;
 5    if (pred == null)
 6        head = newNode;
 7    else
 8        pred.next = newNode;
 9    size++;
10}

假如我們在a結(jié)點(diǎn)之前添加一個(gè)結(jié)點(diǎn),，圖就不在細(xì)畫,，簡單看一下即可

4，刪除鏈表的尾結(jié)點(diǎn)

 1private Object unlinkLast(Node<Object> last) {
 2    final Object element = last.data;
 3    final Node<Object> prev = last.prev;
 4    last.data = null;
 5    last.prev = null;
 6    tail = prev;
 7    if (prev == null)//如果只有一個(gè)結(jié)點(diǎn),，把尾結(jié)點(diǎn)刪除,，相當(dāng)于把鏈表清空了
 8        head = null;
 9    else
10        prev.next = null;
11    size--;
12    return element;
13}

如果鏈表只有一個(gè)結(jié)點(diǎn)的話，我們把它刪除,，相當(dāng)于直接把鏈表清空了,，這種很好理解，就不再畫,。下面畫一個(gè)長度大于1的鏈表,，然后刪除最后一個(gè)結(jié)點(diǎn)

5，刪除鏈表的頭結(jié)點(diǎn)

 1private Object unlinkFirst(Node<Object> first) {
 2    final Object element = first.data;
 3    final Node<Object> next = first.next;
 4    first.data = null;
 5    first.next = null;
 6    head = next;
 7    if (next == null)
 8        tail = null;
 9    else
10        next.prev = null;
11    size--;
12    return element;
13}

6,，刪除鏈表的中間結(jié)點(diǎn)

 1Object unlink(Node<Object> x) {
 2    final Object element = x.data;
 3    final Node<Object> next = x.next;//x的前一個(gè)結(jié)點(diǎn)
 4    final Node<Object> prev = x.prev;//x的后一個(gè)結(jié)點(diǎn)
 5
 6    if (prev == null) {//前一個(gè)結(jié)點(diǎn)是空
 7        head = next;
 8    } else {
 9        prev.next = next;
10        x.prev = null;
11    }
12
13    if (next == null) {//后一個(gè)結(jié)點(diǎn)是空
14        tail = prev;
15    } else {
16        next.prev = prev;
17        x.next = null;
18    }
19
20    x.data = null;
21    size--;
22    return element;
23}

4,，雙向環(huán)形鏈表

雙向環(huán)形鏈表在代碼中最常見的就是LinkedHashMap了，這個(gè)一般用于圖片緩存的比較多一些,，LRUCache這個(gè)類里面主要使用的就是LinkedHashMap（java語言中）,，通過上面的分析，如果對linkedList能理解的話,，那么雙向環(huán)形鏈表也就不難理解了,，其實(shí)原理都差不多，這里就不在過多介紹,，下面是雙向環(huán)形鏈表的圖,。