怎么在Python中实现一个单链表

　　介绍

怎么在Python中实现一个单链表?针对这个问题,这篇文章详细介绍了相对应的分析和解答,希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。

关于链表

<李>

链表(链表)是由许多相同数据类型的数据项按照特定顺序排列而成的线性表。

<李>

链表中个数据项在计算机内存中的位置是不连续且随机的,数组在内存中是连续的。

<李>

链表数据的插入和删除很方便,但查找数据效率低,下不能像数组一样随机读取数据。

单链表的实现

<李>

一个单向链表的节点由数据字段和指针组成,指针指向下一个元素所在内存地址

<李>

定义一个链表节点类,self.value实例属性表示节点数据字段;自我。下表示指针;初始化值为没有

<李> class 节点(对象): 　　def 才能;__init__(自我,,value=https://www.yisu.com/zixun/None,接下来=None): 　　自我。值=值 　　自我。明年=

,

<李>

在单链表中第一个节点为头(头)指针节点(<强>即头指针指向的节点为单链表第一个节点,后续简称头指针节点),从头指针节点出发可以遍历整个链表,进行元素查找,插入和删除,非常重要。一般不移动头头指针。

<李>

单链表中最后一个节点为尾节点,其指针为None,表示结束。

<李>

建立单链表我们首先需要<强>创建头指针节点(引入头指针是为了方便操作单链表,对于头指针节点,只有指针域指向链表第一个节点,不含实际值)

<李> class  linkedList(对象): 　　def 才能__init__(自我): 　　,,,self.head =,节点()#,创建头指针结点 　　,,,self.length =, 0 #,初始链表长度,头指针节点不计入长度 　　def 才能__len__(自我):#,重写特殊方法返回self.length 　　,,,return  self.length

,

<李>

链表初始化之后,开始定义链表方法

<李>

<>强链表头部插入节点:

<李>

待插入节点指向原头指针节点,头指针重新指向待插入节点

<李>

首先需要将原头指针结点,存放到临时变量中(<强>防止头指针变更时,指针断裂导致数据丢失,链表中指针就是连接的纽带,其中某个纽带断裂(即指针指向其他)则后续数据都将丢失)

<李>

将头指针指向新插入节点

<李>

新插入节点指针指向原头指针节点

<李>

长度+ 1

<李>

插入节点既是链表头指针指向的节点也是尾节点(指向None)

<李>

调用节点()传入待插入的值价值创建待插入节点

<李>

判断当前链表是否为空链表,链表为空:

<李>

链表不为空:

<李> ,, def  head_insert(自我,,值):,#,链表头部插入 　　,,,node =,节点(值) 　　,,,if  self.head.next ==,没有: 　　,,,,,self.head.next =,节点 　　,,,,,node.next =,没有 　　,,,: 　　,,,,,#,插入元素指针域指向原头元素 　　,,,,,tmp_head =, self.head.next  #,原头指针节点存储到tmp_head 　　,,,,,self.head.next =, node  #,新头指针指向节点 　　,,,,,node.next =, tmp_head  #,新插入节点指向原头指针节点 　　,,,self.length  +=, 1 <李>

<>强链表头部删除节点:

<李>

头指针指针域(指针域存放下一节点的内存地址,即头指针节点)指向头指针,也就是说链表第一个节点变成了头指针头,由于头不计入链表,所以就相当于删除了第一个节点(有点绕)

<李>

同时返回删除的值

<李>

依旧是先判断链表是否为空,为空则返回假

<李>

链表不为空时:

<李> ,, def  head_del(自我):,#,删除头结点,返回头结点的值 　　,,,if  self.head.next ==,没有: 　　,,,,,return 错误的 　　,,,: 　　,,,,,#,头指针指针域指向自己 　　,,,,,self.head =self.head.next 　　,,,,,self.length  -=1 　　,,,,,return  self.head。李价值 <李>

<>强链表尾部添加节点:

<李>

首先通过而循环(循环条件为节点指针是否为None)找到当前链表的最后一个元素

<李>

然后将当前最后一个元素指向待插入节点

<李>

长度+ 1

<李>

创建待插入节点对象

怎么在Python中实现一个单链表