數據結構與算法 —— 鏈表linked list(01)

鏈表(維基百科)

鏈表（Linked list）是一種常見的基礎數據結構，是一種線性表，但是并不會按線性的順序存儲數據，而是在每一個節點里存到下一個節點的指針(Pointer)。由于不必須按順序存儲，鏈表在插入的時候可以達到O(1)的復雜度，比另一種線性表順序表快得多，但是查找一個節點或者訪問特定編號的節點則需要O(n)的時間，而順序表相應的時間復雜度分別是O(logn)和O(1)。使用鏈表結構可以克服數組鏈表需要預先知道數據大小的缺點，鏈表結構可以充分利用計算機內存空間，實現靈活的內存動態管理。但是鏈表失去了數組隨機讀取的優點，同時鏈表由于增加了結點的指針域，空間開銷比較大。在計算機科學中，鏈表作為一種基礎的數據結構可以用來生成其它類型的數據結構。鏈表通常由一連串節點組成，每個節點包含任意的實例數據（data fields）和一或兩個用來指向上一個/或下一個節點的位置的鏈接（"links"）。鏈表最明顯的好處就是，常規數組排列關聯項目的方式可能不同于這些數據項目在記憶體或磁盤上順序，數據的訪問往往要在不同的排列順序中轉換。而鏈表是一種自我指示數據類型，因為它包含指向另一個相同類型的數據的指針（鏈接）。鏈表允許插入和移除表上任意位置上的節點，但是不允許隨機存取。鏈表有很多種不同的類型：單向鏈表，雙向鏈表以及循環鏈表。單向鏈表（又名單鏈表、線性鏈表）是鏈表的一種，其特點是鏈表的鏈接方向是單向的，對鏈表的訪問要通過從頭部開始，依序往下讀取.

定義

我們來看一下單向鏈表的定義實現：

class ListNode(object):def __init__(self, value):self.value = valueself.next = None

　一個節點有value的屬性定義該節點的值，還有一個next的指針，指向下一個節點，類似于1>2>4>5>6>3這樣。

操作

單向鏈表的操作主要有：添加一個節點，刪除一個節點，遍歷一條鏈表，具體的實現如下：

def add(pre, new_node):"""pre節點后面插入一個新的節點:param pre: pre節點:param new_node: 新插入的節點:return:"""new_code.next = pre.nextpre.next = new_nodedef delete(pre):"""pre節點的后面刪除一個節點:return:"""if pre.next:pre.next = pre.next.nextdef traverse(head):while head:print(head.value)head = head.next

　　在pre節點后面插入一個節點：只需要把新節點的指針指向pre節點指針指向的節點，把pre節點的指針指向新節點。

　　在pre節點后面刪除一個節點：只需要把pre節點的指針指向pre節點的指針的指針節點(要注意pre節點的指針不為None)

?題目

我們來看一個關于鏈表的一個算法題，來自于leetcode:

刪除鏈表中的元素

刪除鏈表中等于給定值?val?的所有元素。

示例
給定:?1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6,?val?= 6
返回:?1 --> 2 --> 3 --> 4 --> 5

分析：一般來講，我們首先會考慮到遍歷一下這個鏈表，移除掉value值等于給定val的節點就好。但是這里要返回一個新的鏈表，我們知道，對于單向鏈表，我們只能知道當前元素的后置節點，而不知道當前元素的前置節點。所以我們要構建一個前置節點。

　　　看代碼：

def removeElements(head, val):""":param head: listNode:param val: int:return: listNode"""dump = ListNode(-1)dump.next = headcur = headpre = dumpwhile cur:if cur.value == val:pre.next = cur.nextelse:pre = pre.nextcur = cur.nextreturn dump.next

　　我們構建一個dump節點作為第一個節點，cur節點為當前循環的節點，pre節點為cur節點的前置節點。

　　當前節點的value為給定val的時候，把當前cur的前置節點pre指針指向cur的后置節點，也就是cur.next。然后接著遍歷這個鏈表。

　　由于第一個節點dump是我們自己構造的(我用的值是-1，你可以用其他不為val的值，一般使用-1)，它的next是給出的head，我們只是對head做了調整。所以最后新的列表就是dump.next,也就是調整后的head。

?

學習技術交流群：226704167，愿和各位一起進步！

?