python鏈表

一 簡介

1 鏈表簡介

鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。 相比于線性表順序結構，操作復雜。由于不必須按順序存儲，鏈表在插入的時候可以達到O(1)的復雜度，比另一種線性表順序表快得多，但是查找一個節點或者訪問特定編號的節點則需要O(n)的時間，而線性表和順序表相應的時間復雜度分別是O(logn)和O(1)。

使用鏈表結構可以克服數組鏈表需要預先知道數據大小的缺點，鏈表結構可以充分利用計算機內存空間，實現靈活的內存動態管理。但是鏈表失去了數組隨機讀取的優點，同時鏈表由于增加了結點的指針域，空間開銷比較大。鏈表最明顯的好處就是，常規數組排列關聯項目的方式可能不同于這些數據項目在記憶體或磁盤上順序，數據的存取往往要在不同的排列順序中轉換。鏈表允許插入和移除表上任意位置上的節點，但是不允許隨機存取。鏈表有很多種不同的類型：單向鏈表，雙向鏈表以及循環鏈表。鏈表可以在多種編程語言中實現。像Lisp和Scheme這樣的語言的內建數據類型中就包含了鏈表的存取和操作。程序語言或面向對象語言，如C,C++和Java依靠易變工具來生成鏈表，python在其標準庫中沒有鏈接列表。

2 單項鏈表和雙向鏈表

1 單鏈表

1 示意圖

2 存儲結構

上圖就是單向鏈表的存儲結構原理圖，由圖中我們可以看出每個節點都由兩部分組成，一個是data數據域，另一個是指向下一節點的next指針域，指針域不存放任何數據，然后通過這樣的方式一直指下去，最后便形成了一條類似鐵鏈的結構，所以稱為鏈表，最后的next指針為null，說明到了最后一個節點，(python中為None),最后一個節點的指針不指向任何節點，所以next=null.

2 雙向鏈表

1 示意圖

2 存儲結構

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接后繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。一般我們都構造雙向循環鏈表。

二 python單向鏈表實現

1 單項鏈表實現append和 iternodes

#!/usr/bin/poython3.6
#conding:utf-8
class  SingleNode:
    ''' 定義一個節點'''
    def  __init__(self,value,next=None,prev=None):  #追加的下一跳就是None
        self.value=value  # 定義節點中的數據
        self.next=next   # 定義節點的指針
        self.prev=prev   # 定義節點的上一個元素
    def  __repr__(self):
        return str(self.value)  # 此處返回的是指針的值

class  LinkedList:
    '''容器類，用來存儲一個個節點，鏈表在內存中并非是連續的，而list在內存中是連續的'''
    def __init__(self):
        self.nodes=[]  #定義存儲的容器，對于一個不需要插入和刪除的鏈表來說，使用list更方便,但插入和remove是不方便的
        self.head=None  #默認的，鏈表的頭和尾都是空
        self.tail=None  # 追加知道tail不用從頭進行處理，尾巴加上
    def append(self,val):
        node=SingleNode(val)  #此處生成一個node的值
        prev=self.tail #查看當前有多少個元素，及就是未加的節點之前，前一個節點
        if  prev  is None:  # 如果當前尾巴是None,則表明無元素。tail指的是node,此處是針對第一個元素的執行
            self.head=node #前一個的下一個是None
        else:
            prev.next = node  # 前一個元素的下一個元素指向當前的元素,若只放一個，則next是None，用默認值就可以
        self.nodes.append(node) #追加，此處需要前一個元素
        self.tail=node  # 前一個元素的下一個指向的是node，
    def  iternodes(self,reverse=False):#遍歷當前元素
        current= self.head  # 遍歷
        while current:
            yield current
            current=current.next

l1=LinkedList()
l1.append(10)
l1.append(11)
l1.append(12)
l1.append(20)
for i in  l1.iternodes():
    print (i)

結果如下

2 雙向鏈表實現如下

#!/usr/bin/poython3.6
#conding:utf-8
class  SignerNode:
    def __init__(self,value,next=None,prev=None):
        self.value=value
        self.next=next
        self.prev=prev
    def __repr__(self):
        return  str(self.value)

class  LinkedList:
    def __init__(self):
        self.tail = None
        self.head = None
    def append(self,val):
        node=SignerNode(val)
        if self.tail  is None:  # only one
            self.head=node
        else:
            self.tail.next=node
            node.prev=self.tail  #前一個應該指向當前的前一個
        self.tail=node  # 將自己變成尾部
    def  iternodes(self,reverse=False):
        current=self.tail  if reverse else  self.head
        while current:
            yield  current
            current=current.prev  if  reverse  else  current.next
    def  pop(self):  # 從尾部進行刪除
        if self.tail  is  None:  #如果沒尾部，則直接為空
            raise  Exception('Empty')
        # tail中只有一個元素，則其一定不是None,但一定需要拿到
        tail = self.tail  #當前的尾巴
        prev=tail.prev   # 獲取尾巴的前一個
        # next=tail.next    # 尾巴的后一個恒定位None
        if  prev  is  None: # 此處表示其如果只有一個元素,則頭部和尾部都為空
            self.head=None
            self.tail=None
        else:  # 此處不止一個元素
            self.tail=prev  #將tail指定到前面的一個
            prev.next=None # 前一個的下一個是None
        return  tail.value  # 送進來的是誰，返回的應該就是誰
    def getitem(self,index): # 此處不支持負向索引，此處時通過索引進行操作
        if index < 0 :
            return None
        current=None
        for  k,v in enumerate(self.iternodes()):
            if  index==k:
                current=v  # 如果存在，此處返回為Node
                break
        if current  is  not  None:  # 此處是判斷元素的值是否是None，如果時None,則返回，查看遍歷是否到頭
            return  current
    def insert(self,index,value):
        if  index <0:
            raise Exception('Error')
        current = None
        for k, v in enumerate(self.iternodes()):
            if index == k:
                current = v  # 如果存在，此處返回為Node
                break
        if current  is   None:  # 此處是判斷元素的值是否是None，如果時None,則返回，查看遍歷是否到頭,若沒找到，則追加
            self.append(value)  # 此處尾部的修改是不用管的
            return
        prev = current.prev
        next = current.next
        node = SignerNode(value)
        if prev  is None:  # 若你是開頭，則prev為None
            self.head=node
            node.next=current # 當前的下一個是之前的
            current.prev=node # 之前的前一個之前是None,現在由于加入了元素，因此前一個的前一個是當前的節點
        else: # 在后面的，本身最后的沒動，只是他前面的在動
            node.prev=prev  # 插入的前一個是之前的
            node.next=current # 插入的后一個是當前節點
            current.prev= node   # 當前節點的之前修改成node
            prev.next=node  # 前一個的需要指向當前的
    def  remove(self,index):
        if self.tail is None:  # 此處表示是最后一個
            raise Exception('Empty')
        if index <0:
            raise ValueError('Wrong Index {}'.format(index))
        current=None
        for k, v in enumerate(self.iternodes()):
            if index == k:
                current = v  # 如果存在，此處返回為Node
                break
        if current  is None: # 沒找到
            raise  ValueError('Wrong   Index {} .out of  boundary'.format(index))
        prev=current.prev
        next = current.next

        if prev  is None  and  next  is  None: # 此處表示只有一個元素 only  one的情況
            self.head=None
            self.tail=None
        elif  prev  is None:  # 則表示為開始元素
            self.head=next
            next.prev=None
        elif next is  None: # 此處表示是最后一個元素
            self.tail=prev
            prev.next=None
        else: # 不是頭部，也不是尾部
            prev.next=next
            next.prev=prev
        print (current)
        del  current
l1=LinkedList()
node=SignerNode('1234')
l1.append(node)
node=SignerNode(1)
l1.insert(0,node)
node=SignerNode(2)
l1.insert(1,node)
node=SignerNode(100)
l1.insert(100,node)
for  i  in   l1.iternodes():
    print (i)
print ('#'*20)
print  (l1.pop())
print (l1.pop())
for  i  in   l1.iternodes():
    print (i)
print ('~'*20)
l1.remove(1)
print ('*'*20)
for  i  in   l1.iternodes():
    print (i)

結果如下

3 使用_setitem_，_getitem_,__iter__實現對鏈表的訪問

#!/usr/bin/poython3.6
#conding:utf-8
class  Node:
    def __init__(self,value,next=None,prev=None):
        self.value=value
        self.next=next
        self.prev=prev
    def __repr__(self):
        return  str(self.value)

class  NodeList:
    def __init__(self):
        # self.lst=[]
        self.tail=None
        self.head=None
    def append(self,value):
        node = Node(value)
        current=self.tail
        if current  is None:  # 此處表示無數據
            self.head=node
        else:  #此處表示有數據
            current.next=node
            node.prev=current
        self.tail=node
        # self.lst.append(node)
    def  pop(self):
        current=self.tail
        prev=current.prev
        next=current.next
        if  current  is None:
            raise  Exception('Empty')
        if  prev  is None:  # 此處是判斷只有一個元素
            self.head=None
            self.tail=None
        else:
            self.tail=prev
            prev.next=None
    def  iterable(self,reverse=True):
        current=  self.head    if  reverse else  self.tail
        while current:
            yield  current
            current= current.next  if reverse  else current.prev
    def insert(self,index,value):
        if index < 0 :
            raise Exception('Index  illegal')
        node1=Node(value)
        current=None
        for  k,node  in   enumerate(self.iterable()):
            if  index==k:
                current=node
                break
        if  current  is  None:
            self.append(node1)
            return
        prev=current.prev
        mext=current.next
        if prev is None:  # 此處表示是第一個
            self.head=node1
            node1.next=current
            current.prev=node1
        else:
            node1.next=current
            node1.prev=current.prev
            prev.next=node1
            current.prev=node1
    def remove(self,index):
        if index < 0:
            raise Exception('Index  illegal')
        current = None
        for k, node in enumerate(self.iterable()):
            if index == k:
                current = node
                break
        if current  is None:
            raise Exception('Index  not exist')
        prev=current.prev
        next=current.next
        if  prev  is None  and  next  is None:
            self.tail=None
            self.head=None
        elif prev  is None:
            self.head=current.next
            next.prev=None
        elif  next is None:
            self.tail=current.prev
            prev.next=None
        else:
            prev.next=next
            next.prev=prev
    def __getitem__(self, index):
        for  i,node  in enumerate(self.iterable(True  if index >=0  else  False), 0  if  index >= 0 else 1 ): # 此處表示枚舉法的起點為0
            if  ( i   if  index>=0  else  -i) == abs(index):
                return node

    def __iter__(self):
        return  iter(self.iterable())
    def __setitem__(self,index, value):
        self[index].value=value
node=Node(1)
l1=NodeList()
l1.append(node)
node=Node(2)
l1.append(node)
node=Node(3)
l1.append(node)
node=Node(4)
l1.append(node)
node=Node(5)
l1.append(node)
for i in l1.iterable():
    print (i)
print ('*'*30)
l1.pop()
l1.pop()
l1.pop()
for i in l1.iterable():
    print (i)
print ('#'*30)
l1.insert(0,100)
l1.insert(100,10)
l1.insert(2,'abc')
for i in l1.iterable():
    print (i)
print ('~'*30)
l1.remove(2)
l1.remove(1)
l1.remove(0)
l1.remove(1)
for i in l1.iterable():
    print (i)
l1.append(node)
l1.append(node)
print ('}'*20)
print (l1[0])
print (l1[1])
print ('}'*20)
for i  in l1:
    print (i)
print ('['*30)
l1[1]=4
for i  in l1:
    print (i)
l1[0]=10
print (']'*30)
for i  in l1:
    print (i)
l1[2]=20
print ('$'*30)
for i  in l1:
    print (i)
l1[2]=40
print ('('*30)
for i  in l1:
    print (i)