python 標準庫并沒有實現(xiàn)鏈表,所以我們得自己實現(xiàn)鏈表。

什么是鏈表

鏈表是計算機科學中最常用的數(shù)據(jù)結構之一。它也是最簡單的結構之一，也是更高層結構（如堆棧、循環(huán)緩沖區(qū)和隊列）的基礎。

一般來說，列表是通過引用連接的單個數(shù)據(jù)元素的集合。C程序員知道這是指針。例如，數(shù)據(jù)元素可以由地址數(shù)據(jù)、地理數(shù)據(jù)、幾何數(shù)據(jù)、路由信息或事務細節(jié)組成。通常，鏈接列表的每個元素都具有特定于列表的相同數(shù)據(jù)類型

單個列表元素稱為節(jié)點。節(jié)點不同于順序存儲在內(nèi)存中的數(shù)組。相反，它可能會在不同的內(nèi)存段中找到它們，您可以通過跟蹤從一個節(jié)點到下一個節(jié)點的指針找到這些內(nèi)存段。通常使用nil元素標記列表的結尾，該元素由python等效的None表示。

鏈表類型

• 單鏈表
  有兩種列表-單鏈接列表和雙鏈接列表。單個鏈接列表中的節(jié)點只指向列表中的下一個元素，而雙鏈接列表中的節(jié)點也指向上一個節(jié)點。數(shù)據(jù)結構占用更多的空間，因為您需要一個額外的變量來存儲鏈表的引用。

@單鏈列表

• 雙鏈表
  一個鏈表可以從頭到尾遍歷，而反向遍歷則比較難。相反，雙鏈接列表允許以相同的成本在兩個方向上遍歷節(jié)點，無論從哪個節(jié)點開始。此外，添加和刪除節(jié)點以及拆分單個鏈接列表的步驟不超過兩個。在雙鏈接列表中，必須更改四個指針。（詳情可見添加刪除方法）

@雙鏈表

這篇博文，我們將一步步建立自己的鏈表。首先，我們?yōu)楣?jié)點創(chuàng)建一個對應的數(shù)據(jù)結構。其次，您將學習如何實現(xiàn)和使用一個單鏈接列表，最后是一個雙鏈接列表。

Step 1: Node as a Data Structure

我們建立一個Node 的節(jié)點類。該類有兩個屬性變量存儲數(shù)據(jù)的data和指向下一個節(jié)點的引用next。

• __init_(): 初始化節(jié)點的方法
• self.data: 儲存在節(jié)點中的數(shù)據(jù)
• self.next: 下個節(jié)點的引用
• has_value(): 是否包含這個值的節(jié)點

# 1。__init_(): initialize the node with the data
# 2。self.data: the value stored in the node
# 3。self.next: the reference pointer to the next node
# 4。 has_value(): compare a value with the node value
class Node:
    def __init__(self, data):
        "constructor to initiate this object"

        # store data
        self.data = data

        # store reference (next item)
        self.next = None
        return

    def has_value(self, value):
        "method to compare the value with the node data"
        if self.data == value:
            return True
        else:
            return False
            

Step 2: Creating a Class for a Single-Linked List

這一步我們建立一個叫 SingleLinkedList 的類。該類包含一下方法

• __init__(): 初始化方法
  list_length():返回節(jié)點數(shù)
• output_list(): 打印方法
• add_list_item(): 添加一個節(jié)點到list 中
• unordered_search(): 在列表中查找具有指定值的節(jié)點
• remove_list_item_by_id(): 通過節(jié)點id 移除節(jié)點

初始化方法

定 head 和tail屬性

class SingleLinkedList:  
    def __init__(self):
        "constructor to initiate this object"

        self.head = None
        self.tail = None
        return

添加

def add_list_item(self, item):
        "add an item at the end of the list"

        #如果不是 Node，構建為Node
        if not isinstance(item, Node):
            item = Node(item)

        #如果頭節(jié)點是空，則當前節(jié)點就是 item
        if self.head is None:
            self.head = item
        else:
            #如果已經(jīng)有頭節(jié)點，則加到尾部
            self.tail.next = item
        
        #尾部就是當前績點item了
        self.tail = item

        return

定義返回節(jié)點長度方法

  def list_length(self):
        "returns the number of list items"

        count = 0
        current_node = self.head

        while current_node is not None:
            # increase counter by one
            count = count + 1

            # jump to the linked node
            current_node = current_node.next

        return count

定義輸出方法

    def output_list(self):

        "outputs the list (the value of the node, actually)"

        current_node = self.head

        while current_node is not None:
            print(current_node.data)

            # jump to the linked node
            current_node = current_node.next

        return

查詢

查詢列表，返回指定值的node 位置list

def unordered_search(self, value):
        "search the linked list for the node that has this value"

        # define current_node
        current_node = self.head

        # define position
        node_id = 1

        # define list of results
        results = []

        while current_node is not None:
            if current_node.has_value(value):
                results.append(node_id)

            # jump to the linked node
            current_node = current_node.next
            node_id = node_id + 1

        return results
        

刪除

 def remove_list_item_by_id(self, item_id):
        "remove the list item with the item id"

        current_id = 1
        current_node = self.head
        previous_node = None

        while current_node is not None:

            #當前這個node 就是需要移除的node
            if current_id == item_id:
                # if this is the first node (head)
                #如果這個node 前面還有node ，那需要把前面node 的next，指向當前node 的下一個node（原來前一個node 的next 是當前node）。
                # 就已經(jīng)從這個鏈路里移除了，因為沒有node 指向它了。
                if previous_node is not None:
                    previous_node.next = current_node.next
                else:
                    #需要移除的是第一個node，只要把當前的head 指向下一個node 即可
                    self.head = current_node.next
                    # we don't have to look any further
                    return

            # needed for the next iteration
            # 如果還不是當前node，上一個node 變成當前node
            # 當前node 變成當前node 的下一個。當然id 要加1
            previous_node = current_node
            current_node = current_node.next
            current_id = current_id + 1

        return

測試以上方法

我們使用一下代碼，測試下以上方法。

# create three single nodes
node1 = ListNode(15)  
node2 = ListNode(8.2)  
node3 = ListNode("Berlin")  
node4 = ListNode(15)

track = DoubleLinkedList()  
print("track length: %i" % track.list_length())

for current_node in [node1, node2, node3, node4]:  
    track.add_list_item(current_node)
    print("track length: %i" % track.list_length())
    track.output_list()

results = track.unordered_search(15)  
print(results)

track.remove_list_item_by_id(4)  
track.output_list()  

Step 3: Creating a Double-Linked List

本來我們可以通過繼承的方式，復用 Node 方法。但為了更清晰。我們再建立一個Node2 作為基本節(jié)點。

class Node2:
    def __init__(self, data):
        "constructor class to initiate this object"

        # store data
        self.data = data

        # store reference (next item)
        self.next = None

        # store reference (previous item)
        self.previous = None
        return

    def has_value(self, value):
        "method to compare the value with the node data"
        if self.data == value:
            return True
        else:
            return False

建立 DoubleLinkedList

from Add_Two_Numbers.Node2 import Node2


class DoubleLinkedList:
    def __init__(self):
        "constructor to initiate this object"

        self.head = None
        self.tail = None
        return

    def list_length(self):
        "returns the number of list items"

        count = 0
        current_node = self.head

        while current_node is not None:
            # increase counter by one
            count = count + 1

            # jump to the linked node
            current_node = current_node.next

        return count

    def output_list(self):
        "outputs the list (the value of the node, actually)"
        current_node = self.head

        while current_node is not None:
            print(current_node.data)

            # jump to the linked node
            current_node = current_node.next

        return

    def unordered_search (self, value):
        "search the linked list for the node that has this value"

        # define current_node
        current_node = self.head

        # define position
        node_id = 1

        # define list of results
        results = []

        while current_node is not None:
            if current_node.has_value(value):
                results.append(node_id)

            # jump to the linked node
            current_node = current_node.next
            node_id = node_id + 1

        return results





#略有不同
    def add_list_item(self, item):
        "add an item at the end of the list"

        if isinstance(item, Node2):

            #如果還沒有Node，則首尾都是item，而且該node 的前一個沒有，后一個也沒有
            if self.head is None:
                self.head = item
                item.previous = None
                item.next = None
                self.tail = item
            else:
                #如果有Node 元素了，則當前尾部的node的下一個node 就是item，item的前一個元素就是當前的tail node。現(xiàn)在把item 放到尾部。
                self.tail.next = item
                item.previous = self.tail
                self.tail = item

        return




    #根據(jù)node id 移除node
    def remove_list_item_by_id(self, item_id):
        "remove the list item with the item id"

        current_id = 1
        current_node = self.head


        #當前node 不為空
        while current_node is not None:
            previous_node = current_node.previous
            next_node = current_node.next

            #當前node 就是需要移除的node
            if current_id == item_id:
                # if this is the first node (head)

                #當前node 不是第一個head node
                if previous_node is not None:

                    #前一個node的 next 指向 下個node
                    previous_node.next = next_node

                    # 如果當前node 不是tail node
                    if next_node is not None:

                        # next_node 前一個node 指向 當前node 的前一個node（原來next_node 的前一個node 是 當前node）
                        next_node.previous = previous_node
                else:

                    #如果需要移除的是head node，則把head 指向 next_node
                    self.head = next_node


                    # 如果 head node 不是最后一個node ，則還要把下一個node 的 previous 指向為None（原來為當前node）
                    if next_node is not None:
                        next_node.previous = None
                # we don't have to look any further
                return

            # needed for the next iteration
            current_node = next_node
            current_id = current_id + 1

        return

總結

鏈表作為數(shù)據(jù)結構易于實現(xiàn)，并且提供了很大的使用靈活性。這是用幾行代碼完成的。作為改進，您可以添加一個節(jié)點計數(shù)器（count），它只保存列表中節(jié)點的數(shù)量。這樣可以把查詢列表長度復雜度降低到 O(1)，您不必遍歷整個列表。