python数据结构--链表

什么是链表?

熟悉python语法的同学肯定都知道list，但是这并不是真正意义上的链表（linked list）。链表是由一系列的节点(node)来实现的，通过每一个node存储下一个节点的指针来实现一种快速的插入。此外每个节点都有一个cargo包含一定的数据。根据链表结构的不同，其种类可以分为单向链表、单项循环链表、双向链表、双向循环链表等。

创建链表

class Linklist:
    def __init__(self):
        self.headval = None


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


# 创建一个空的链表
ob = Linklist()
# 为链表添加第一个节点元素
ob.headval = Node("first")

# 为链表添加第二个节点元素（在第一节点之后）
n2 = Node("second")
ob.headval.nextval = n2

# 为链表添加第三个节点元素（在第二节点之后）
n3 = Node("threed")
n2.nextval = n3

print(n2)
print(n2.nextval)
print(n3)
# 结果为n3内存地址<__main__.Node object at 0x0000011FF5FECC48>
print(n2.nextval.data)
# 结果为n3所代表的值threed

链表首尾添加新的节点

class Linklist:
    def __init__(self):
        self.headval = None

    # 在链表末尾添加一个新的node
    def append(self, newdata):
        NewNode = Node(newdata)
        if self.headval is None:
            self.headval = NewNode
            return
        laste = self.headval
        while (laste.nextval):
            laste = laste.nextval
        laste.nextval = NewNode

    # 在链表头部添加一个新的node
    def add_left(self, newdata):
        NewNode = Node(newdata)
        if self.headval is None:
            self.headval = NewNode
            return
        last = self.headval
        self.headval = NewNode
        self.headval.nextval = last

    # 打印链表
    def show(self):
        printval = self.headval
        while printval:
            print(printval.data)
            printval = printval.nextval

中间添加节点

class Linklist:
    def __init__(self):
        self.headval = None
        
    def insert(self,middle_node,newdata):
        if not middle_node:
            print("The mentioned node is absent")
            return

        NewNode = Node(newdata)
        NewNode.nextval = middle_node.nextval
        middle_node.nextval = NewNode