Python学习笔记:Python 链表简介及创建方法

什么是 PYTHON 链表?

Python 链表是 Python 中的一种抽象数据类型,它允许用户在节点中组织信息,然后链接到列表中的另一个节点。这使得在不更改列表中其他项目的索引的情况下更容易插入和删除信息。

链表的数据结构在以下情况下很有用:

  • 你希望在其他项目之间轻松插入项目。
  • 总集合大小未知
  • 搜索项目时不需要随机访问。
  • 无需担心存储数据的内存使用情况。

如何在 Python 中创建链表

考虑到这一点,我们就可以开始思考如何在Python中实现实际数据结构中的链表。通常与此相关的关键方法包括:

  • insert()在链表的头部添加一个项目。
  • find()在链表中查找一个项目。
  • remove()删除具有给定值的给定项目。
  • is_empty():返回链表是否为空。
  • get_count()返回链表中的项数。

有趣的是,在 Python 中没有自然的数据结构可以用来构建这个链表。对于队列和堆栈,我们可以利用 Python 中已经内置的列表数据结构。但是在我们实现链表之前,我们需要构造一个节点类。

这是因为链接列表中的每个项目本身都是一个单独的对象,可以包含它想要的任何信息,以及标识链接列表中的下一个项目。它必须有一个指向或标识它包含的信息的属性,以及一个指向链表中下一个节点的属性。为此,我们还必须添加允许我们提取此节点和下一个节点包含的数据的行为,以及设置或调整这些属性的能力。因此,这可以实现为:

Class Node(object):
def __init__(self, val):
self.val = val
self.next = None
def get_data(self):
return self.val
def set_data(self, val):
self.val = val
def get_next(self):
return self.next
def set_next(self, next):
self.next = next

我们有val和next属性,它们对应于节点持有的数据,同时也指向链表中的下一个节点。我们最初将next设置为None的事实表明我们在开始时创建了一个没有给定下一个节点的节点。然后我们还添加了允许我们打印出当前val和下一个节点的方法,以及更改val和设置下一个节点的能力。

考虑到这一点,我们就可以创建链表了。我们将专注于单向链表,这意味着每个节点只有一个指向链表中下一个节点的链接,正如我们在上面的节点实现中看到的那样。

如何在 Python 中构建单向链表

第一步是创建构造函数,每当创建链表时都会调用该构造函数。在这种情况下,我们从两个属性开始:

  • Head:链表中的第一个节点。
  • Count:链表中的节点数。

我们将首先创建一个空的head,以便我们从一个空的链表开始。这也意味着我们不必head在第一次添加项目时检查是否有 a 。我们还添加了一个count属性,以便在添加或删除项目时,我们可以从中添加或减去一个。这意味着当我们想要检查链表中有多少项时,我们可以简单地调用这个属性而不是遍历整个列表。这通过增加添加和删除函数的复杂性而创建了一个权衡,同时在尝试找到长度时消除了时间复杂性。

这可以按如下方式实现:

Class LinkedList(object):
def __init__(self, head = None):
self.head = head
self.count = 0

如何在 Python 中将项目添加到链接列表

对于链接列表,能够向列表本身添加项目或节点非常重要。现在,我们只关注将项目添加到链表的头部。但是,这可以扩展到在列表中的任何位置添加项目,具体取决于这是按索引还是在另一个项目之前或之后。我们在头部执行此操作的方法很简单,并且是一个很好的起点。

我们首先实例化一个新节点,将数据分配给新节点,将新节点的下一个设置为当前链表的头部,然后将链表的头部设置为新节点。与在 Python 中对标准列表执行相同的操作相比,这使得该过程变得简单易行且时间复杂度较低。这可以按如下方式实现:

 def insert(self, data):
new_node = Node(data)
new_node.set_next(self.head)
self.head = new_node
self.count += 1

现在我们可以将项目添加到我们的链接列表中,接下来我们要做的是搜索该链接列表以查看哪些数据是链接列表的一部分。有多种方法可以做到这一点,包括按值或按索引搜索。为了简单起见,我们将专注于按值搜索。

为此,我们可以遍历链表以查看是否有任何节点的数据与我们要搜索的值相匹配。这意味着在最坏的情况下,我们必须遍历链表中的所有项目。因此,时间复杂度为O(n)。当我们找到该项目时,我们可以返回该节点。或者在该值不存在的情况下,我们可以返回None以避免抛出任何错误。

def find(self, val):
item = self.head
while item != None:
if item.get_data() == val:
return item
else:
item = item.get_next()
return None

如何从 Python 链表中删除项目

如果我们能找到项目,从链表中删除它们怎么样?我们不仅希望能够添加和查找项目,我们还希望能够删除链表中的项目。这是另一个可以用不同方式构建的函数,但在本例中,我们将重点关注删除具有特定值而不是按索引的项目。然后,这遵循与上面的查找功能类似的逻辑。

从链表中删除一个项目与常规列表的主要区别在于,在链表中,节点仍然可以存在于某处。我们只是将前一个节点的指针从该节点更改为下一个节点。与常规列表相比,这使得从链接列表中删除项目相对容易,因为并非删除节点之后的所有项目都必须更改其索引。只需要更改节点之间的连接。这可以按如下方式实现:

    def remove(self, item):
current = self.head
previous = None
while current is not None:
if current.data == item:
break
previous = current
current = current.get_next()
if current is None:
raise ValueError(f"{item} is not in the list")
if previous is None:
self.head = current.next
self.count -= 1
else:
previous.set_next(current.get_next())
self.count -= 1

需要了解的 Python 链表函数

创建链表的主要功能后,我们可以开始添加其他方法,使链表的使用更简单。我们可以添加的两个补充方法包括获取链表的长度和查看链表是否为空。

  1. 查找链表的长度

第一种返回链接长度的方法相对简单。这是因为我们实现构造函数方法以及insert和remove方法的方式。为此,我们创建了count属性,每当我们将新节点插入链表时该属性就会上升,而每当我们使用该remove方法移除节点时该属性就会下降。因此,我们可以返回存储在count属性中的值,如下所示:

   def get_count(self):
return self.count

2.判断 PYTHON 链表是否为空

看看链表是否为空呢?我们可以用类似的方式来获取count属性并检查它是否为零。head为了简单起见,我们可以通过查看属性是否为空来轻松检查链表是否为空。如果由于某种原因count属性没有正确实现,我们可以很容易地检查 是否head为空,因为这表明我们根本没有节点。

 def is_empty(self):
return self.head == None

将 Python 链表代码放在一起

Class Node(object):
def __init__(self, val):
self.val = val
self.next = None
def get_data(self):
return self.val
def set_data(self, val):
self.val = val
def get_next(self):
return self.next
def set_next(self, next):
self.next = next
Class LinkedList(object):
def __init__(self, head = None):
self.head = head
self.count = 0
def insert(self, data):
new_node = Node(data)
new_node.set_next(self.head)
self.head = new_node
self.count += 1
def find(self, val):
item = self.head
while item != None:
if item.get_data() == val:
return item
else:
item = item.get_next()
return None
def remove(self, item):
current = self.head
previous = None
while current is not None:
if current.data == item:
break
previous = current
current = current.get_next()
if current is None:
raise ValueError(f"{item} is not in the list")
if previous is None:
self.head = current.next
self.count -= 1
else:
previous.set_next(current.get_next())
self.count -= 1
def get_count(self):
return self.count
def is_empty(self):
return self.head == None

然后你可以单独添加其他功能,例如:

  • deleteAt(index)删除给定索引处的项目
  • findAt(index)查找给定索引处的项目
  • insertAt(index)在给定索引处插入一个项目

这也可以扩展为双向链表,其中每个节点都有指向链表中下一个节点和前一个节点的链接。你现在可以创建一个链接列表,这将使你更容易插入和删除项目。当然你要知道非随机访问的弊端和查找项的困难,但这要取决于你对链表的应用。

给TA打赏
共{{data.count}}人
人已打赏
python

Python学习笔记:python range()函数用法

2023-2-23 15:23:21

python算法

Python学习笔记:Python 8种排序算法

2023-2-23 15:36:32

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索
打开微信,扫描左侧二维码,关注【旅游人lvyouren】,发送【101】获取验证码,输入获取到的验证码即可解锁复制功能,解锁之后可复制网站任意一篇文章,验证码每月更新一次。
提交