python3 实现链表的相关操作

# linklist.py

# 初始化链表内每个节点的类，每个节点包含一个数据域和一个指针域
#__init__这种带双线的函数理解为创建类的对象时会自动调用的函数，类似于java的构造函数
class linkNode:
    def __init__(self, data, p = 0): # 链表节点初始化时，就有一个数据域和指针域，数据域是初始化时入参决定，指针域默认为空
        self.data = data
        self.next = p

class linkList:
    def __init__(self):
        self.head = None # 初始化时，只有一个头结点

    # 通过待插入链表的数据，依次生成各个链表的节点(尾插法，插入data),data是一个数组，存储了n个待插入链表的数据
    def initListTail(self, data):
        self.head = linkNode(data[0]) # 创建头结点，即第一个有值节点
        p = self.head # p 代表了链表的头结点，因此可以使用p.data和p.next访问链表节点的两个域
        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 # 方便后续根据if语句调用该判断函数
        else:
            print("The linkList is not empty!")
            return 0

    # 遍历链表并输出，用','隔开
    def readList(self):
        if self.isEmpty():
            exit(0)
        p = self.head
        while p:
            print(p.data, end = ',')
            p = p.next
        print('')

    # 取链表长度
    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 的节点后插入节点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 个节点后的那一个节点
    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()

    # 反转链表并输出反转后链表的头结点
    def reverseLinkedList(self):
        pReverseHead = None
        pNode = self.head
        pPrev = None

        # 循环并反转
        while pNode:
            pNext = pNode.next # 首先保存pNode原本指向的下一个节点，这样在解除它们指向关系时，原下一个节点不会丢失

            # 若pNext == 0, 则说明pNone到达原顺序的最后一个节点，即反转后链表的头结点
            if (pNext == 0):
                pReverseHead = pNode

            pNode.next = pPrev # 将节点的next指针指向它的前一个节点
            pPrev = pNode
            pNode = pNext

        # 打印反转后的链表
        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() #输出结果为1,2,3,4,5,
    linkedList.getLength() #输出结果为lenth of the LinkList: 5
    linkedList.insertElem(6, 3) #输出结果为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