關(guān)于鏈表的知識(shí)點(diǎn)有哪些

本篇內(nèi)容介紹了“關(guān)于鏈表的知識(shí)點(diǎn)有哪些”的有關(guān)知識(shí)，在實(shí)際案例的操作過(guò)程中，不少人都會(huì)遇到這樣的困境，接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

一 單向鏈表

1.1  單向鏈表原理圖

單向鏈表的一個(gè)鏈結(jié)點(diǎn)包含數(shù)據(jù)域和下一個(gè)鏈結(jié)點(diǎn)的指針。頭結(jié)點(diǎn)也包含數(shù)據(jù)域和指針域，但是一般為了方便查找，頭節(jié)點(diǎn)不寫(xiě)數(shù)據(jù)，最后一個(gè)結(jié)點(diǎn)的指針指向空。

1.2 實(shí)現(xiàn)單向鏈表的存儲(chǔ)等操作

創(chuàng)建一個(gè)鏈結(jié)點(diǎn)的實(shí)體類(lèi)

public class Node {      // 數(shù)據(jù)域     public long data;     // 指針域     public Node next;      public Node(long value){         this.data = value;     } }

1.2.1 插入一個(gè)節(jié)點(diǎn)

在頭節(jié)點(diǎn)后插入一個(gè)結(jié)點(diǎn)，第一步需要將新插入的結(jié)點(diǎn)指向頭結(jié)點(diǎn)指向的結(jié)點(diǎn)，第二步將頭結(jié)點(diǎn)指向新插入的結(jié)點(diǎn)。插入結(jié)點(diǎn)只需要改變一個(gè)引用，所以復(fù)雜度為O(1)。

public class LinkList {      private Node head;     /**      * 在頭節(jié)點(diǎn)之后插入一個(gè)節(jié)點(diǎn)      */     public void insertFirst(long value){         Node node = new Node(value);         node.next = head;         head = node;     } }

1.2.2 頭結(jié)點(diǎn)后刪除一個(gè)結(jié)點(diǎn)

在頭結(jié)點(diǎn)后刪除一個(gè)結(jié)點(diǎn)，就是讓頭結(jié)點(diǎn)指向這個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)。復(fù)雜度也是O(1)。

public Node deleteFirst(){     Node tmp = head;     head = tmp.next;     return tmp; }

1.2.3 根據(jù)數(shù)據(jù)域查找結(jié)點(diǎn)

查找需要比對(duì)每個(gè)結(jié)點(diǎn)的數(shù)據(jù)，理論上查找一個(gè)結(jié)點(diǎn)平均需要N/2次，所以復(fù)雜度為O(N)。

public Node find(long value){      Node current = head;     while (current.data != value){         if(current.next == null){             return null;         }         current = current.next;     }     return current; }

1.2.4 根據(jù)數(shù)據(jù)與刪除結(jié)點(diǎn)

查找需要比對(duì)每個(gè)結(jié)點(diǎn)的數(shù)據(jù)，理論上刪除一個(gè)結(jié)點(diǎn)平均需要N/2次，所以復(fù)雜度為O(N)。

public Node delete(int value){     Node current = head;     // 當(dāng)前結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)     Node pre = head;     while (current.data != value){         if(current.next == null){             return null;         }         pre = current;         current = current.next;     }     if(current == head){         head = head.next;     }else{         pre.next = current.next;     }     return current; }

二 雙端鏈表

2.1 雙端鏈表原理圖

雙端鏈表是在單向鏈表的基礎(chǔ)上，頭結(jié)點(diǎn)增加了一個(gè)尾結(jié)點(diǎn)的引用。

2.2 實(shí)現(xiàn)雙端鏈表的存儲(chǔ)等操作

2.2.1 從頭部插入結(jié)點(diǎn)

如果鏈表為空，則設(shè)置尾結(jié)點(diǎn)就是新添加的結(jié)點(diǎn)。復(fù)雜度為O(1)。

public class FirstLastLinkList {      private Node first;     private Node last;     /**      * 在頭結(jié)點(diǎn)之后插入一個(gè)節(jié)點(diǎn)      */     public void insertFirst(long value){         Node node = new Node(value);         if(first == null){             last = node;         }         node.next = first;         first = node;     } }

2.2.2 從尾部插入結(jié)點(diǎn)

如果鏈表為空，則設(shè)置頭結(jié)點(diǎn)為新添加的結(jié)點(diǎn)，否則設(shè)置尾結(jié)點(diǎn)的后一個(gè)結(jié)點(diǎn)為新添加的結(jié)點(diǎn)。復(fù)雜度為O(1)。

public void insertLast(long value){     Node node = new Node(value);     if(first == null){         first = node;     }else{         last.next = node;     }     last = node; }

2.2.3 從頭部進(jìn)行刪除

判斷頭結(jié)點(diǎn)是否有下一個(gè)結(jié)點(diǎn)，如果沒(méi)有則設(shè)置尾結(jié)點(diǎn)為null，復(fù)雜度為O(1)。

public Node deleteFirst(){      Node tmp = first;     if(first.next == null){         last = null;     }     first = tmp.next;     return tmp; }

三 雙向鏈表

3.1 雙向鏈表原理圖

每個(gè)結(jié)點(diǎn)除了保存對(duì)后一個(gè)結(jié)點(diǎn)的引用外，還保存著對(duì)前一個(gè)結(jié)點(diǎn)的引用。

3.2 實(shí)現(xiàn)雙向鏈表的存儲(chǔ)等操作鏈結(jié)點(diǎn)實(shí)體類(lèi)

public class Node {      // 數(shù)據(jù)域     public long data;     // 后一個(gè)結(jié)點(diǎn)指針域     public Node next;     // 前一個(gè)結(jié)點(diǎn)指針域     public Node prev;      public Node(long value){         this.data = value;     } }

3.2.1 從頭部插入結(jié)點(diǎn)

如果鏈表為空，則設(shè)置尾結(jié)點(diǎn)為新添加的結(jié)點(diǎn)，如果不為空，還需要設(shè)置頭結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)為新添加的結(jié)點(diǎn)。插入結(jié)點(diǎn)只需要改變兩個(gè)結(jié)點(diǎn)的引用，所以復(fù)雜度為O(1)。

public class DoubleLinkList {      private Node first;     private Node last;      /**      * 在頭結(jié)點(diǎn)之后插入一個(gè)節(jié)點(diǎn)      */     public void insertFirst(long value){         Node node = new Node(value);         if(first == null){             last = node;         } else{             first.prev = node;         }         node.next = first;         first = node;     } }

3.2.2 從尾部插入結(jié)點(diǎn)

如果鏈表為空，則設(shè)置頭結(jié)點(diǎn)為新添加的結(jié)點(diǎn)，否則設(shè)置尾結(jié)點(diǎn)的后一個(gè)結(jié)點(diǎn)為新添加的結(jié)點(diǎn)。同時(shí)設(shè)置新添加的結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)為尾結(jié)點(diǎn)。插入結(jié)點(diǎn)只需要改變1個(gè)結(jié)點(diǎn)的引用，所以復(fù)雜度為O(1)。

public void insertLast(long value){     Node node = new Node(value);     if(first == null){         first = node;     }else{         last.next = node;         node.prev = last;     }     last = node; }

3.2.3 從頭部刪除結(jié)點(diǎn)

判斷頭結(jié)點(diǎn)是否有下一個(gè)結(jié)點(diǎn)，如果沒(méi)有則設(shè)置尾結(jié)點(diǎn)為null，否則設(shè)置頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的prev為null。復(fù)雜度也為O(1)。

public Node deleteFirst(){      Node tmp = first;     if(first.next == null){         last = null;     }else{         first.next.prev = null;     }     first = tmp.next;     return tmp; }

3.2.4 從尾部刪除結(jié)點(diǎn)

如果頭結(jié)點(diǎn)后沒(méi)有其他結(jié)點(diǎn)，則設(shè)置頭結(jié)點(diǎn)為null，否則設(shè)置尾結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的next為null，設(shè)置尾結(jié)點(diǎn)為前一個(gè)結(jié)點(diǎn)。復(fù)雜度為O(1)。

public Node deleteLast(){      Node tmp = last;      if(first.next == null){         first = null;     }else{         last.prev.next = null;       }     last = last.prev;     return last; }

“關(guān)于鏈表的知識(shí)點(diǎn)有哪些”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！