單向雙向鏈表的實現

用面向對象實現LinkedList鏈表

單向鏈表實現append、iternodes方法

雙向鏈表實現append、pop、insert、remove、iternodes方法

鏈表的好處：

            查詢慢、插入追加刪除快

思路：

# 單向鏈表 1 2 2 3 3 4 4 5 5 6 None 最基本的鏈表結構

# 鏈表由 每一個數據塊組成 串聯在一起就是鏈表

#先定義數據塊 Node

class Node1:  ##(item -> next)

    def __init__(self,item, next=None):

        self.item = item

        self.next = next

    def __repr__(self):

        return '<{}--->{}>'.format(self.item,

                                      self.next.item if self.next else 'None') #？？？怎么理解這句話 

#構造單向鏈表

class Singelinked:

    def __init__(self): #設定開頭和結尾 這是一個鏈表最基本的屬性 初始鏈表的開頭和結尾為None

        self.head = None

        self.tail = None

    def append(self,item):

        Node = Node1(item)  ##構造一個要添加的節點 然后寫入到鏈表中

        if self.head is None:  #

            self.head = Node ##如果是空的直接追加

            self.tail = Node     

        else:

            self.tail.next = Node #不為空 就在最后一個尾部 追加 然后追加完成后 把前一個的next 變成 node

            self.tail = Node

        return self

    def iterlink(self):

        current = self.head   #當前的頭部

        while current:      #無限循環 知道 當前為None 等效False

            yield current

            current = current.next  

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

##先定義數據塊 Node

class Node2:  ##(item -> next)

    def __init__(self,item, next= None,prev=None): ##雙向鏈表除了頭和尾之外都是雙向的

        self.prev = prev

        self.item = item

        self.next = next

    def __repr__(self):

        return '<{}<--{}-->{}>'.format(self.prev.item if self.prev else 'None',self.item,self.next.item if self.next else 'None')

#構造雙向鏈表

class DubleLineked:

    def __init__(self):

        self.head = None

        self.tail = None

        self.size = None

    def append(self,item):

        Node = Node2(item)  ##構造一個要添加的節點 然后寫入到鏈表中

        if self.head is None:

            self.head = Node ##如果是空的直接追加

            #self.tail = Node

        else:

            Node.prev = self.tail

            self.tail.next = Node

        self.tail = Node

        return self

    def insert(self,index,value):

        if index < 0 : #只接受正索引

            raise IndexError('Negative index err{}'.format(index))

        current = None

        for i,node in enumerate(self.iterlink()):

            if i == index:

                current = node

                break

        else:

            self.append(value)

            return  ########################## if使用后記得用return 終止函數執行

        ##創建一個待加入節點對象； 如果是空 或者超界的情況 則直接執行append語句 append有包裝的語句

        node = Node2(value) #包裝成模塊

        prev = current.prev

        # next = current.next

        ## 放在頭 考慮修正關系  切記 修改后要修改頭部 為不加入不用考慮 因為append 就是尾部和空的加入

        if index == 0 : # 除了空和尾部追加 就是 頭部 和中部了 分開討論一下就ok了 i==0 or prev = None

            current.prev = node

            node.next = current

            self.head = node

        else:#中部追加

            node.prev = prev

            node.next = current

            current.prev = node

            prev.next = node

        return

    def pop(self): #尾部移除

        if self.tail is None: #考慮空鏈表

            raise Exception('{}'.format(None))

        else:

            node = self.tail #取模塊

            item = node.item # item 是模塊內的data

            prev = node.prev #模塊的前一項

            if prev is None and next is None: #只有一個node

                self.head = None

                self.tail = None

                return item  #返回一個數值

            else:##兩個元素移除尾部 最后剩下一個

                self.tail = prev ##node.prev

                prev.next = None

                return item   #返回一個數值

    def remove(self,index): #任意位置移除 比較index

        if index < 0 :

            raise IndexError("Do not support nagative index {}".format(index))

        if self.head is None or self.tail is None:

            raise Exception('Empty')

        for i,node in enumerate(self.iterlink()):

            if i == index:

                current = node

                break

        else: ##超出索引范圍 移除最后一個

            self.pop() #拋出最后一個

            return  ##記得終止函數執行@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

            #raise IndexError('超出索引邊界')     兩個都可以

        ###break 說明找到了要索引的值 這時候就要對這個值進行操作了

        prev = current.prev

        next = current.next

        item = current.item

        #分4情況

        #就一個模塊 既是頭 有事尾

        #在開頭

        #在結尾

        #在中間

        if prev is None and next is None: #JUEST 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

    def iterlink(self,reversed = False): #雙向迭代就是翻轉的問題 想sorted函數

        current = self.head if not reversed else self.tail

        while current:

            yield current

            current = current.next if not reversed else current.prev

#輸出結果測試

a = DubleLineked()

a.append(1)

a.append(2)

a.append(3)

a.insert(100,'abd')

a.insert(0,112)

a.insert(3,'liajibin')

a.pop()

print(a.pop())

a.remove(1)

for x in a.iterlink():

    print(x)