Python数据结构与算法之列表(链表,linkedlist)简单实现
在Python中,列表是一种非常常用的数据类型。除了Python内置的列表,还可以使用链表(linkedlist)来实现列表。链表是一种线性数据结构,由一系列节点组成,每个节点包数据和指向下一个节点的指针。在本文中,我们将详细介绍如何使用Python实现链表,并演示如何使用链实现列表。
链表的实现
在Python中,我们可以使用类来实现链表。每个节点可以表示为一个类的实例,包含数据和指向下一个节点的指针。链表本身也可以表示为一个类的实例,包含指向链表头部的指针。下面是一个简单的链表现:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
上述代码中,我们定义了一个Node类表示链表的节点,包含数据和指向下一个节点的指针。我们还定义了一个LinkedList类表示链表本身,包含指向链表头部的指针。
链表的操作
链表支持许多操作,例如添加元素、删除元素、访问元素等。下面是一些常用的链表操作。
添加元素
要向链表中添加元素,我们可以使用append()函数或insert()函数。append()函数用于在链表末尾添加元素,而insert()函数用于在指定位置添加元素。例如:
# 向链表中添加元素
class:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
last_node = self.head
while last_node.next is not None:
last_node = last_node.next
last_node.next = new_node
def insert(self, prev_node, data):
if prev_node is None:
print("Previous node is not in the list")
return
new_node = Node(data)
new_node.next = prev_node.next
prev_node.next = new_node
上述代码中,我们定义了LinkedList类的append()函数和insert()函数。append()函数用于在表末尾添加元素,如果链表为空,则将新节点设置为链表头部。insert()函数用于在指定位置添加元素,如果指定的前一个节点不存在,则输出错误信息。
删除元素
要从链表中删除元素,我们可以使用remove()函数或pop()函数。remove()函数用于删除指定的元素,而pop()函数用于删除指定位置的元素。例如:
# 从链表中删除元素
class LinkedList:
def __init__(self):
self.head = None
def remove(self, key):
curr_node = self.head
if curr_node is not None and curr_node.data == key:
self.head = curr_node.next
curr_node = None
return
prev_node = None
while curr_node is not None and curr_node.data != key:
prev_node = curr_node
curr_node = curr_node.next
if curr_node is None:
return
prev_node.next = curr_node.next
curr_node = None
def pop(self, pos=None):
if self.head is None:
return
curr_node = self.head
if pos == 0:
self.head = curr_node.next
curr_node = None
return
prev_node = None
count = 0
while curr_node is not None and count != pos:
prev_node = curr_node
curr_node = curr_node.next
count += 1
if curr_node is None:
return
prev_node.next = curr_node.next
curr_node = None
上述代码中,我们定义了LinkedList类的remove()函数和pop()函数。remove()函数用于删除指定的元素,如果指定的元素不存在,则不进行何操作。pop()函数用于删除指定位置的元素,如果指定的位置不存在,则不进行任何操作。
访问元素
要访链表中的元素,我们可以使用get()函数。get()函数用于获取指定位置的元素。例如:
# 访问链表中的元素
class LinkedList:
def __init__(self):
self.head = None
def get(self, pos):
curr_node = self.head
count = 0
while curr_node is not None and count != pos:
curr_node = curr_node.next
count += 1
if curr_node is None:
return None
return curr_node.data
上述代码中,我们定义了LinkedList类的get()函数。get()函数用于获取指定位置的元素,如果指定的位置不存在,则返回None。
示例说明
下面是两个示例,演示了如何使用链表实现列表。
示例1:创建、访问和修改列表
下面是一个示例,演了如何使用链表实现列表的创建、访问和修改:
# 创建、访问和修改列表
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
last_node = self.head
while last_node.next is not None:
last_node = last_node.next
last_node.next = new_node
def get(self, pos):
curr_node = self.head
count = 0
while curr_node is not None and count != pos:
curr_node = curr_node.next
count += 1
if curr_node is None:
return None
return curr_node.data
def set(self, pos, data):
curr_node = self.head
count = 0
while curr_node is not None and count != pos:
curr_node = curr_node.next
count += 1
if curr_node is None:
return
curr_node.data = data
my_list = LinkedList()
my_list.append(1)
my_list.append(2)
my_list.append(3)
print(my_list.get(0)) # 输出:1
print(my_list.get(2)) # 输出:3
my_list.set(1, 4)
print(my_list.get(1)) # 输出:4
上述代码中,我们首先定义了Node类和LinkedList类,分别表示链表的节点和链表本身。然后,我们创建了一个包含3个元素的链表my_list,并使用get()函数访问了链表中的元素。接着,我们使用set()函数修改了链表中的元素,并使用get()函数验证了修改结果。
示例2:添加元素、删除元素和遍历表
下面是一个示例,演示了如何使用链表实现列表的添加元素、删除元素和遍历:
# 添加元素、删除元素和遍历链表
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
last_node = self.head
while last_node.next is not None:
last_node = last_node.next
last_node.next = new_node
def remove(self, key):
curr_node = self.head
if curr_node is not None and curr_node.data == key:
self.head = curr_node.next
curr_node = None
return
prev_node = None
while curr_node is not None and curr_node.data != key:
prev_node = curr_node
curr_node = curr_node.next
if curr_node is None:
return
prev_node.next = curr_node.next
curr_node = None
def traverse(self):
curr_node = self.head
while curr_node is not None:
print(curr_node.data)
curr_node = curr_node.next
my_list = LinkedList()
my_list.append(1)
my_list.append(2)
my_list.append(3)
my_list.traverse() # 输出:1 2 3
my_list.remove(2)
my_list.traverse() # 输出:1 3
上述代码中,我们首先定义了Node类和LinkedList类,分别表示链表的和链表本身。然后,我们创建了一个包含3个元素的链表my_list,并使用traverse()函数遍历了链表中的元素。接着,我们使用remove()函数删除了链表中的元素,并使用traverse()函数验证了删除结果。
总之,链表是一种常重要的数据结构,可以用于实现列表等数据类型。我们可以使用类来实现链表,使用append()函数和insert()函数向链表中添加元素,使用remove()函数和pop()函数从链表中删除元素,使用get()函数访问链表中的元素,使用traverse()函数遍历链表中的元素。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Python数据结构与算法之列表(链表,linked list)简单实现 - Python技术站