首页 / PYTHON / python实现链表

python实现链表

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python实现链表，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含8012字，纯文字阅读大概需要12分钟。

内容图文

链表：

链表不需要在内存存储一个连续的地方，通常就像一个链一样

它的每个节点包含本身和下一个元素的地址，以此来把两个元素进行关联，这就是一个链表

链表分单项和双向，一般单项就够用了。

链表存在的用意义：

链表是一个存储的数据结构，C语言中存数据用的是数组，存储所有的元素都是在内存中，每一个元素在内存中相连的位置，如果想删除一个元素，那么后边所有的元素都要向前移动一个位置，这样就提高了时间复杂度，如果是链表里的元素，如果删了一个数，那么把前一个的元素指向被删除元素的后一个元素就可以了，时间复杂度是O(1)，数组里面的时间复杂度是O(n),效率不一样，所以这是链表存在的意义，比数组操作的效率高。

用于C语言中代替数组存储数据，效率会高一些

但是在python中直接用list就可以

链表里是用指针指向下一个元素的地址，但是python里没有指针，那就

用变量存一下下一个元素的地址,代替指针

链表定义：

链表可以用类的实例表示，实例有value和next属性，next指向下一个实例

定义节点

class p():pass

实例化一个实例，用a来执行它

a=P()

a指向P类的一个实例的地址

self.next=P()，指向下一个元素

最后一个元素的下一个指针域指向None

python实现链表 - 文章图片

数据域指针域（下一个节点的地址）

最后一个元素的指针域是None就结束了

定义节点类：

代码：

#encoding=utf-8

class Node:

def __init__(self,value=None,next=None):#next(指针域)

self.value=value

self.next=next

n1=Node(1)

n2=Node(2)

n3=Node(3)

n1.next=n2

n2.next=n3

print "n1.value:",n1.value

print "n2.value:",n2.value

print "n2.value:",n3.value

print "######################"

print "n1.next.value:",n1.next.value

print "n2.next.value:",n2.next.value

print "n3.next:",n3.next

结果：

python实现链表 - 文章图片

定义函数打印出所有节点的值：

使用while循环判断，节点.next是否为空，不空，就打印

def printLinkedList(node):

while True:

if node.next != None:

print node.value

else:

print node.value

break

node = node.next#从当前节点跳到下一个节点

printLinkedList(n1)

原理：判断最后一个元素的值是不是None

结果：

python实现链表 - 文章图片

或者：

代码：

def printLinkedValue(node):

while node is not None:

print node.value

node = node.next

return ""

print printLinkedValue(n1)

结果：

D:\>python test.py

递归方式正序输出：

代码：

def printLinkedList(node):

#递归

#自己调用自己，并且有结束的条件，这是递归的原则

if node.next is None:

print node.value

return

print node.value

printLinkedList(node.next)

#return ""

printLinkedList(n1)

结果：

D:\>python test.py

拆解：

n1:1
printLinkedList(n2)
n2:2
printLinkedList(n3)
n3:3

递归方式逆序输出

def printReversedLinkedList(node):

if node.next is None:

print (node.value)

return

printReversedLinkedList(node.next)

print (node.value)

return None

printReversedLinkedList(n1)

结果：

python实现链表 - 文章图片

n1-->n2--n3(打印3，返回)---打印一个2---》1

递归逆序图解：

python实现链表 - 文章图片

递归的时候是往回捣~~

相当于每次执行递归时，记个账本，最后一点点往前算账~~

链表类：

练习代码：

class LinkedList(object):

def __init__(self,head=None):

self.head = head

#重写__len__函数计算链表长度

def __len__(self):

count = 0

if self.head == None:

print "b"*10

return count

print "c"*10

node =self.head

print "d"*10

while node:

print "e"*10

count +=1

node = node.next

print "f"*10

return count

a=LinkedList(n1)

print len(a)

结果：

D:\>python test.py

cccccccccc

dddddddddd

eeeeeeeeee

ffffffffff

eeeeeeeeee

ffffffffff

eeeeeeeeee

ffffffffff

在链表末尾加入一个节点：

练习代码：

def append(self,node):

if self.head == None:

self.head = node

return node

cur_node = self.head

while cur_node.next != None:

print cur_node.value

cur_node = cur_node.next

cur_node.next=node

return cur_node.value

结果：

D:\>python test.py

查找一个节点：

练习代码：

def find(self,value):

if self.head == None:

return

cur_node = self.head

while cur_node:

if cur_node.value == value:

print cur_node.value

return cur_node

else:

cur_node = cur_node.next

a=LinkedList(n1)

print a.find(3)

结果：

D:\>python test.py

<__main__.Node object at 0x00000000058F5D30>

插入一个节点：

练习代码：

def insertFront(self,data):

if self.head == None:

self.head = Node(data)

return self.head

else:

tmp = self.head

self.head=Node(data)

self.head.next = tmp

return self.head

a=LinkedList(n1)

print a.insertFront(5)

print a.insertFront(5).value

结果：

D:\>python test.py

<__main__.Node object at 0x00000000055A5EB8>

删除列表中的某个值对应的节点：

练习代码：

def delete(self,value):

if self.head==None:

return None

elif self.head.value == value:

self.head = self.head.next

else:

fro_node = None

cur_node = self.head

while cur_node:

if cur_node.value != value:

fro_node=cur_node

cur_node = cur_node.next

else:

fro_node.next = cur_node.next

return cur_node.value

return None

a=LinkedList(n1)

print a.delete(3)

结果：

D:\>python test.py

获取有所节点的值：

练习代码：

def get_all(self):

list=[]

if self.head == None:

return None

else:

cur_node = self.head

while cur_node:

list.append(cur_node.value)

cur_node = cur_node.next

return list

a=LinkedList(n1)

print a.get_all()

结果：

D:\>python test.py

[1, 2, 3]

所有练习代码:

#encoding=utf-8

class Node(object):

def __init__(self,value=None,next=None):

self.value=value

self.next=next

n1=Node(1)

n2=Node(2)

n3=Node(3)

n1.next=n2

n2.next=n3

class LinkedList(object):

def __init__(self,head=None):

self.head = head

def __len__(self):

count = 0

if self.head == None:

return count

node =self.head

while node:

count +=1

node = node.next

return count

def append(self,node):

if self.head == None:

self.head = node

return node

cur_node = self.head

while cur_node.next != None:

print cur_node.value

cur_node = cur_node.next

cur_node.next=node

return cur_node.value

def find(self,value):

if self.head == None:

return

cur_node = self.head

while cur_node:

if cur_node.value == value:

print cur_node.value

return cur_node

else:

cur_node = cur_node.next

def insertFront(self,data):

if self.head == None:

self.head = Node(data)

return self.head

else:

tmp = self.head

self.head=Node(data)

self.head.next = tmp

return self.head

def delete(self,value):

if self.head==None:

return None

elif self.head.value == value:

self.head = self.head.next

else:

fro_node = None

cur_node = self.head

while cur_node:

if cur_node.value != value:

fro_node=cur_node

cur_node = cur_node.next

else:

fro_node.next = cur_node.next

return cur_node.value

return None

def get_all(self):

list=[]

if self.head == None:

return None

else:

cur_node = self.head

while cur_node:

list.append(cur_node.value)

cur_node = cur_node.next

return list

a=LinkedList(n1)

print a.get_all()

内容总结

以上是互联网集市为您收集整理的python实现链表全部内容，希望文章能够帮你解决python实现链表所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/855702.html

来源：【匿名】

【上一篇】Python Tool Kits 【下一篇】浅谈PHP运行Python脚本的方法

更多 ►

【python实现链表】教程文章相关的互联网学习教程文章

Leetcode练习(Python)：哈希表类：第138题：给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深拷贝。我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。

题目：给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深拷贝。我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：val：一个表示 Node.val 的整数。random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。思路：先使用哈希表来构建一个新的链表，然后对这个链表赋予ne...

python数据结构与算法第七天【链表】【图】

1.链表的定义如图：注意：（1）线性表包括顺序表和链表（2）顺序表是将元素顺序地存放在一块连续的存储区里（3）链表是将元素存放在通过链构造的存储快中原文：https://www.cnblogs.com/liuzhiqaingxyz/p/9439814.html

【python】Leetcode每日一题-删除排序链表中的重复元素【代码】【图】

【python】Leetcode每日一题-删除排序链表中的重复元素【题目描述】给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。示例1：输入：head = [1,2,3,4,5], k = 2 输出：[4,5,1,2,3] 示例2：输入：head = [0,1,2], k = 4 输出：[2,0,1] 提示：链表中节点的数目在范围 [0, 500] 内 -100 <= Node.val <= 100 0 <= k <= 2 * 10^9 【分析】思路由于 $ 0 \le k \le 2 * 10^9$ ，k较大，因此需要先求出链表总长度，...

python实现单向链表【代码】

# 节点类class Node:def__init__(self, data, next=None):self.data = dataself.next = nextdef__str__(self):return str(self.data)# 链表类class LinkedList:def__init__(self):self.head = Noneself.length = 0# 链表尾部append数据def append(self, data):node = Node(data)if self.head is None: # head 未空,则此时链表为空，直接将新节点赋给self.headself.head = nodeelse: # head 不为空current = self.headindex = 0wh...

链表 21. 归并两个有序的链表 python【代码】

21. Merge Two Sorted Lists (Easy)链表问题可以考虑哑节点（相当于就是头结点，或者一个哨兵）。思路一：迭代需要三个指针，一个哑节点。哑节点的val值默认为-1. 比较l1和l2的大小,哑节点指向小的那个l1和l2中小的那个后移在接着比较现在l1和l2中val的大小，重复1,2步骤直致结束。思路二：递归class Solution(object):def mergeTwoLists(self, l1, l2):""":type l1: ListNode:type l2: ListNode:rtype: ListNode"""cur = dummy_h...

leetcode刷题_PYTHON(6):链表(6)删除排序链表中的重复元素 II【代码】

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中没有重复出现的数字。返回同样按升序排列的结果链表。提示：链表中节点数目在范围 [0, 300] 内-100 <= Node.val <= 100题目数据保证链表已经按升序排列# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next =...

python中的数据结构－链表【代码】【图】

一．什么是链表链表是由一系列节点构成，每个节点由一个值域和指针域构成，值域中存储着用户数据,指针域中存储这指向下一个节点的指针．根据结构的不同，链表可以分为单向链表、单向循环链表、双向链表、双向循环链表等。单向链表的结构如下图所示： head 节点永远指向第一个节点，　tail节点永远指向最后一个节点，节点中最后一个指针指向的是None 值，链表本质上就是由指针链接起来的一系列值．二．为什么使用链表我们经常拿链表...

合并两个排序的链表(python)【代码】

题目描述输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。 1class Solution:2# 返回合并后列表 3def Merge(self, pHead1, pHead2):4# write code here 5 dummy =p = ListNode(-1)6while pHead1 and pHead2:7if pHead1.val < pHead2.val:8 p.next=ListNode(pHead1.val)9 pHead1 = pHead1.next 10else: 11 p.next=ListNode(...

python实现单向链表【代码】

废话不说，直接上代码 #-*-coding=utf-8-*-class Node(object): """节点""" def __init__(self,elem): self.elem=elem self.next=Noneclass SingleLinkList(object): """单链表""" def __init__(self,node=None): self.__head = node def is_empty(self): """判断是否为空""" return self.__head==None def length(self): """链表长度""" #cur游标，用来移动遍...

python——数据结构之单链表的实现【代码】

链表的定义：　　链表(linked list)是由一组被称为结点的数据元素组成的数据结构，每个结点都包含结点本身的信息和指向下一个结点的地址。由于每个结点都包含了可以链接起来的地址信息，所以用一个变量就能够访问整个结点序列。也就是说，结点包含两部分信息：一部分用于存储数据元素的值，称为信息域；另一部分用于存储下一个数据元素地址的指针，称为指针域。链表中的第一个结点的地址存储在一个单独的结点中，称为头结点或首结...

Leetcode练习(Python)：链表类：第92题：反转链表 II：反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

题目：反转链表 II：反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。说明:1 ≤ m ≤ n ≤ 链表长度。示例:输入: 1->2->3->4->5->NULL, m = 2, n = 4输出: 1->4->3->2->5->NULL思路：思路较简单，找到规律就好。程序：# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution:...

python单链表的实现【代码】

‘‘‘ 当加入第一个node节点的时候,会有几个值,(这里的self.tail.next 其实就是node.next) head = item = tail = Node(object element1 memory) item = head = tail = Node(object element1 memory) next = None tail = item = head = Node(object element1 memory)当加入第二个元素node节点的时候,next1值会改变,tail会向后漂移,head将会保留新加入第二个元素后第一个节点变成了 head = item1 = Node(object element1 memory...

剑指offer二叉搜索树与双向链表python【代码】

题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。思路二叉搜索树，自然想到中序遍历。中序遍历出来的结果就是排序的。因为不能创建新的节点，所以，我们定义2个指针，一个指向链表的头，一个指向当前遍历的节点，当遍历到下一个节点的适合，创建和指针双向的连接，然后把此节点改为当前遍历节点。代码# -*- coding:utf-8 -*- # class TreeNode: # ...

55.链表中环的入口结点(python)【代码】

题目描述给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。思路如果slow走了L的长度那么fast走了2L假设从开始到入口点的长度是s，slow在环里走的长度是d那么 l = s + d假设环内slow没走的长度是m，fast走的长度是n*(m+d) + d + s = 2L带入得n*(m+d) + d + s = 2（s+d） => s = m+(n-1)(m+d) m+d就是绕环一圈所以s = m 所以相遇后，让slow和head一起走，相遇点就是入环节点 1class Solution:2def...

【Datastructure In Python】Python模拟链表【代码】【图】

最近一直在学习Python和Perl这两门语言，两者共同点很多，也有不多。希望通过这样的模拟练习可以让自己更熟悉语言，虽然很多时候觉得这样用Python或者Perl并没有体现这两者的真正价值。#! /usr/bin/env python # DataStructure Linkedlistclass Node:"""Member Variable:1. next2. data"""def__init__(self, data):self.data = dataself.next = Nonedef__str__(self):return"NodeInfo: data=%d, next_id=%d" % (self.data, id(self...

首页 / PYTHON / python实现链表

python实现链表

内容导读

内容图文

链表：

链表存在的用意义：

链表定义：

定义节点类：

定义函数 打印出所有节点的值：

使用while循环判断，节点.next是否为空，不空，就打印

递归方式正序输出：

递归方式逆序输出

递归逆序图解：

链表类：

在链表末尾加入一个节点：

查找一个节点：

插入一个节点：

删除列表中的某个值对应的节点：

获取有所节点的值：

所有练习代码:

内容总结

内容备注

内容手机端

【python实现链表】教程文章相关的互联网学习教程文章

PYTHON - 相关标签

链表 - 相关标签

PYTHON - 技术教程分类

PYTHON - 最新教程

PYTHON - 最热教程

定义函数打印出所有节点的值：