Python实现单链表（带头结点）

àì夳堔傛蜴生んèń 2022-10-29 06:29 365阅读 0赞

[Python实现线性表][Python]的方法前面已经讲过，但是不带头结点会有一些问题，主要就是第一个结点的处理需要和其他结点区别对待：  
为了操作上的方便，在单链表第一个结点之前增加一个结点，称为**头结点**。头结点的数据域可以不设任何信息，也可以记录表长等相关信息。头结点的指针域指向线性表的第一个元素结点。

![在这里插入图片描述][20210207104825646.png]  
**不管带不带头结点，头指针始终指向链表的第一个结点，头结点是带头结点链表的第一个结点，结点内通常不存储信息**  
引入头结点的好处：  
1）由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作和在表中其他位置上的操作一致，无须进行特殊处理。  
2)无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。  
直接上代码，其余的函数在[Python实现线性表][Python]已经展示，有兴趣的可以去看看：

class linknode():#每个结点有两个数据成员，结点元素和指向下一个结点的指针
        def __init__(self,item):            #创建节点
            self.item = item
            self.next = None
    class  linklist():#初始化单链表，头结点指针域为空
        def __init__(self):#初始化的头结点的内容为None，指针域也为None
            self.headnode=linknode(None)
            self.headnode.next=None
    
    
    
        def headcreatlist(self, item):
            nod = linknode(item)  # 新建一个结点并赋值
    
            nod.next = self.headnode.next  # 结点指针域指向第一个结点
            self.headnode.next= nod  # 头结点指针指向当前结点
    
        def tailcreatelist(self,item):
            """尾部添加元素"""
            node =linknode(item)
            cur = self.headnode
            while cur.next != None:
                cur = cur.next
            cur.next = node
    
        def listlength(self):
            nod = self.headnode.next  # 头结点指针域指向第一个结点
            nodnum =0
            while (nod != None):
                nodnum += 1
                nod = nod.next  # 下一个结点
            return nodnum
            # 遍历单链表
    
        def tralist(self):
            show = []
            nod = self.headnode.next
            while nod != None:
                show.append(nod.item)
                nod = nod.next
            return show
    
    
    
    if __name__ == "__main__":
        ll1=linklist()
        for i in range(10):
            ll1.headcreatlist(i*10)
    
        len=ll1.listlength()
        print("单链表的长度为：",len)
        sh=ll1.tralist()
        print("头插法建立的链表遍历为：",ll1.tralist())
    
        ll2 = linklist()
        for i in range(10):
            ll2.tailcreatelist(i * 10)
    
        len = ll2.listlength()
        print("单链表的长度为：", len)
        sh = ll2.tralist()
        print("头插法建立的链表遍历为：", ll2.tralist())

运行结果为：

单链表的长度为： 10
    头插法建立的链表遍历为： [90, 80, 70, 60, 50, 40, 30, 20, 10, 0]
    单链表的长度为： 10
    头插法建立的链表遍历为： [0, 10, 20, 30, 40, 50, 60, 70, 80, 90]

[Python]: https://blog.csdn.net/liulanba/article/details/113720473
[20210207104825646.png]: /images/20221024/8e1d02b1fd144ce9aac224a9f896d973.png