# linklist.py

# 初始化鏈表內(nèi)每個(gè)節(jié)點(diǎn)的類(lèi)，每個(gè)節(jié)點(diǎn)包含一個(gè)數(shù)據(jù)域和一個(gè)指針域
#__init__這種帶雙線的函數(shù)理解為創(chuàng)建類(lèi)的對(duì)象時(shí)會(huì)自動(dòng)調(diào)用的函數(shù)，類(lèi)似于java的構(gòu)造函數(shù)
class linkNode:
    def __init__(self, data, p = 0): # 鏈表節(jié)點(diǎn)初始化時(shí)猪落，就有一個(gè)數(shù)據(jù)域和指針域秧耗，數(shù)據(jù)域是初始化時(shí)入?yún)Q定椎例，指針域默認(rèn)為空
        self.data = data
        self.next = p

class linkList:
    def __init__(self):
        self.head = None # 初始化時(shí)虑润，只有一個(gè)頭結(jié)點(diǎn)

    # 通過(guò)待插入鏈表的數(shù)據(jù)芝此，依次生成各個(gè)鏈表的節(jié)點(diǎn)(尾插法睡雇，插入data),data是一個(gè)數(shù)組，存儲(chǔ)了n個(gè)待插入鏈表的數(shù)據(jù)
    def initListTail(self, data):
        self.head = linkNode(data[0]) # 創(chuàng)建頭結(jié)點(diǎn)掉瞳，即第一個(gè)有值節(jié)點(diǎn)
        p = self.head # p 代表了鏈表的頭結(jié)點(diǎn)毕源，因此可以使用p.data和p.next訪問(wèn)鏈表節(jié)點(diǎn)的兩個(gè)域
        for i in data[1:]:
            node = linkNode(i)
            p.next = node
            p = p.next

    # 判斷鏈表是否為空
    def isEmpty(self):
        p = self.head
        if p.next == 0:
            print("The linkList is empty!")
            return 1 # 方便后續(xù)根據(jù)if語(yǔ)句調(diào)用該判斷函數(shù)
        else:
            print("The linkList is not empty!")
            return 0

    # 遍歷鏈表并輸出，用','隔開(kāi)
    def readList(self):
        if self.isEmpty():
            exit(0)
        p = self.head
        while p:
            print(p.data, end = ',')
            p = p.next
        print('')

    # 取鏈表長(zhǎng)度
    def getLength(self):
        if self.isEmpty():
            exit(0)
        p = self.head
        length = 0
        while p:
            length += 1
            p = p.next
        print('length of the linkedList:', length)

    # 在索引值為 index 的節(jié)點(diǎn)后插入節(jié)點(diǎn)key
    def insertElem(self, key, index):
        p = self.head
        j = 1
        while p and j < index:
            p = p.next
            j += 1
        if(p == 0 or j > index):
            exit(0)
            print("insert error!")
        node = linkNode(key)
        node.next = p.next
        p.next = node
        print("inserted linkList!")
        self.readList()

    # 刪除第 index 個(gè)節(jié)點(diǎn)后的那一個(gè)節(jié)點(diǎn)
    def deleteElem(self, index):
        p = self.head
        j = 1
        while p and j < index:
            p = p.next
            j += 1
        if (p == 0 or j > index):
            exit(0)
            print("delete error!")
        q = p.next
        p.next = q.next
        print("delete elem successful!")
        self.readList()

    # 反轉(zhuǎn)鏈表并輸出反轉(zhuǎn)后鏈表的頭結(jié)點(diǎn)
    def reverseLinkedList(self):
        pReverseHead = None
        pNode = self.head
        pPrev = None

        # 循環(huán)并反轉(zhuǎn)
        while pNode:
            pNext = pNode.next # 首先保存pNode原本指向的下一個(gè)節(jié)點(diǎn)陕习，這樣在解除它們指向關(guān)系時(shí)霎褐，原下一個(gè)節(jié)點(diǎn)不會(huì)丟失

            # 若pNext == 0, 則說(shuō)明pNone到達(dá)原順序的最后一個(gè)節(jié)點(diǎn)，即反轉(zhuǎn)后鏈表的頭結(jié)點(diǎn)
            if (pNext == 0):
                pReverseHead = pNode

            pNode.next = pPrev # 將節(jié)點(diǎn)的next指針指向它的前一個(gè)節(jié)點(diǎn)
            pPrev = pNode
            pNode = pNext

        # 打印反轉(zhuǎn)后的鏈表
        print("reversed linkedList:", end = ' ')
        p = pReverseHead
        while p:
            print(p.data, end = ",")
            p = p.next
        print("")
        return pReverseHead


if __name__ == "__main__":
    data1 = [1, 2, 3, 4, 5]
    data2 = []
    linkedList = linkList()
    linkedList.initListTail(data1) 
    linkedList.readList() #輸出結(jié)果為1,2,3,4,5,
    linkedList.getLength() #輸出結(jié)果為lenth of the LinkList: 5
    linkedList.insertElem(6, 3) #輸出結(jié)果為1,2,3,6,4,5,
    linkedList.deleteElem(3) #1,2,3,4,5,
    pReverseHead = linkedList.reverseLinkedList() #reversed linkedList: 5,4,3,2,1,
    print("pReverseHead = ", pReverseHead.data) # pReverseHead =  5