如何區(qū)分python中的鏈表和數(shù)組？

鏈表是節(jié)點(diǎn)的集合。第一個(gè)節(jié)點(diǎn)(Node)一般被稱(chēng)為Head。最后一個(gè)節(jié)點(diǎn)的Next屬性必須指向 None ，表明是鏈表的結(jié)尾。

在大多數(shù)編程語(yǔ)言中，鏈表和數(shù)組在內(nèi)存中的存儲(chǔ)方式存在明顯差異。數(shù)組要求內(nèi)存空間是連續(xù)的，鏈表可以不連續(xù)。

然而，在 Python 中，list是動(dòng)態(tài)數(shù)組。所以在Python中列表和鏈表的內(nèi)存使用非常相似。

鏈表和數(shù)組在以下的操作中也有本質(zhì)區(qū)別：

1.插入元素：數(shù)組中插入元素時(shí)，插入位置之后的所有元素都需要往后移動(dòng)一位，所以數(shù)組中插入元素最壞時(shí)間復(fù)雜度是 O(n)鏈表可以達(dá)到 O(1) 的時(shí)間復(fù)雜度。

2. 刪除元素：數(shù)組需要將刪除位置之后的元素全部往前移動(dòng)一位，最壞時(shí)間復(fù)雜度是 O(n)，鏈表可以達(dá)到 O(1) 的時(shí)間復(fù)雜度。

3.隨機(jī)訪(fǎng)問(wèn)元素：數(shù)組可以通過(guò)下標(biāo)直接訪(fǎng)問(wèn)元素，時(shí)間復(fù)雜度為O(1)。鏈表需要從頭結(jié)點(diǎn)開(kāi)始遍歷，時(shí)間復(fù)雜度為O(n)。

4.獲取長(zhǎng)度： 數(shù)組獲取長(zhǎng)度的時(shí)間復(fù)雜度為O(1)，鏈表獲取長(zhǎng)度也只能從頭開(kāi)始遍歷，時(shí)間復(fù)雜度為O(n)。
實(shí)現(xiàn)鏈表

class LinkedList:
   def __init__(self):
       self.head = None

在LinkedList中，需要存儲(chǔ)的唯一信息是鏈表的開(kāi)始位置(鏈表的頭部)。接下來(lái)，創(chuàng)建另一個(gè)類(lèi)Node來(lái)表示鏈表的每個(gè)節(jié)點(diǎn)：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

我們可以給剛創(chuàng)建的兩個(gè)類(lèi)添加 __repr__ 方法, 在創(chuàng)建實(shí)例的時(shí)候輸出更多有用的信息：

class LinkedList:
    def __init__(self):
        self.head = None
def __repr__(self):
    node = self.head
    nodes = []
    while node is not None:
        nodes.append(node.data)
        node = node.next
    nodes.append("None")
    return " -> ".join(nodes)

我們可以給剛創(chuàng)建的兩個(gè)類(lèi)添加 __repr__ 方法, 在創(chuàng)建實(shí)例的時(shí)候輸出更多有用的信息

class Node:
    def __init__(self, data):
       self.data = data
       self.next = None
        
    def __repr__(self):
            return self.data

創(chuàng)建測(cè)試類(lèi), 測(cè)試上面的代碼

from LinkedList import LinkedList
from Node import Node
if __name__ == '__main__':
    llist = LinkedList()
    print(llist)
    first_node = Node('a')
    llist.head = first_node
    print(llist)
    second_node = Node('b')
    third_node = Node('c')
    first_node.next = second_node
    second_node.next = third_node
    print(llist)

修改__init__ 方法，可以傳入列表快速創(chuàng)建LinkedList

def __init__(self, nodes=None):
    self.head = None
    if nodes is not None:
        node = Node(data=nodes.pop(0))
    self.head = node
    for elem in nodes:
        node.next = Node(data=elem)
        node = node.next

創(chuàng)建__iter__ 方法，遍歷鏈表

def __iter__(self):
    node = self.head
    while node is not None:
        yield node
        node = node.next

from LinkedList import LinkedList
if __name__ == '__main__':
    llist = LinkedList(['a','b','c','d','e'])
    print(llist)
for node in llist:

    print(node)

實(shí)現(xiàn)鏈表，添加節(jié)點(diǎn)

在頭部添加Node：在鏈表的開(kāi)頭添加一個(gè)Node，不必遍歷鏈表，只需將新的Node的next屬性指向 self.head ，并將新的node設(shè)置為新的 self.head

def add_first(self, node):
    node.next = self.head
    self.head = node

from LinkedList import LinkedList
from Node import Node
if __name__ == '__main__':
    llist = LinkedList()
    print(llist)
    llist.add_first(Node('b'))
    print(llist)
    llist.add_first(Node('a'))
    print(llist)

在尾部添加Node：必須遍歷鏈表，與list不同，list可以直接獲取長(zhǎng)度， 鏈表只有從第一個(gè)Node，不斷的去獲取下一個(gè)Node 才能知道鏈表的尾部。

def add_last(self, node):
    if self.head is None:
        self.head = node
        return
    for current_node in self:
        pass
    current_node.next = node

from LinkedList import LinkedList
from Node import Node
if __name__ == '__main__':
    llist = LinkedList(['a','b','c','d'])
    print(llist)

    llist.add_last(Node('e'))
    print(llist)

    
    llist.add_last(Node('f'))
    print(llist)

在指定元素后添加Node：遍歷鏈表找到目標(biāo)Node， 把目標(biāo)Node的下一個(gè)元素， 賦值給要添加Node的next屬性, 然后修改目標(biāo)Node的next屬性, 指向新添加的Node, 當(dāng)鏈表為空以及目標(biāo)元素不存在時(shí)拋出異常。

def add_after(self, target_node_data, new_node):
   if self.head is None:
        raise Exception("List is empty")
for node in self:
   if node.data == target_node_data:
     new_node.next = node.next
     node.next = new_node
     return
     
     raise Exception("Node with data '%s' not found" % target_node_data)

在指定元素后添加Node：遍歷鏈表找到目標(biāo)Node， 把目標(biāo)Node的下一個(gè)元素， 賦值給要添加Node的next屬性, 然后修改目標(biāo)Node的next屬性, 指向新添加的Node, 當(dāng)鏈表為空以及目標(biāo)元素不存在時(shí)拋出異常。

from LinkedList import LinkedList
from Node import Node
if __name__ == '__main__':

    llist = LinkedList()
    llist.add_after("a", Node("b"))
    llist = LinkedList(['a','b','c','d'])
    print(llist)
    llist.add_after("c", Node("cc"))
    print(llist)
    llist.add_after("f", Node("g"))

在指定元素前添加Node：遍歷鏈表找到目標(biāo)Node，還需要記錄當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。

def add_before(self, target_node_data, new_node):
    if self.head is None:
        raise Exception("List is empty")

    if self.head.data == target_node_data:
        return self.add_first(new_node)
    prev_node = self.head
    for node in self:
        if node.data == target_node_data:
        prev_node.next = new_node
        new_node.next = node
        return
    prev_node = node

    raise Exception("Node with data '%s' not found" % target_node_data)

from LinkedList import LinkedList
from Node import Node
if __name__ == '__main__’:
    llist = LinkedList()
    llist.add_before("a", Node("b"))
    llist = LinkedList(["b", "c"])
    print(llist)
    llist.add_before('b',Node('a'))
    print(llist)
    llist.add_before("b", Node("aa"))
    llist.add_before("c", Node("bb"))
    print(llist)
    llist.add_before("n", Node("m"))

刪除Node：遍歷鏈表找到目標(biāo)Node，將目標(biāo)Node的前一個(gè)Node的next屬性,指向目標(biāo)Node的next節(jié)點(diǎn)。

def remove_node(self, target_node_data):
    if self.head is None:
        raise Exception("List is empty")
    if self.head.data == target_node_data:
        self.head = self.head.next
        return

    previous_node = self.head
    for node in self:
        if node.data == target_node_data:
        previous_node.next = node.next
        return
    previous_node = node
raise Exception("Node with data '%s' not found" % target_node_data)

from LinkedList import LinkedList
from Node import Node
if __name__ == '__main__’:
    llist = LinkedList(["a", "b", "c", "d", "e"])
    print(llist)
    llist.remove_node("a")
    print(llist)
    llist.remove_node('e')
    print(llist)