单向链表是一种线性数据结构,每个节点只包含一个指向下一个节点的指针。单向链表的第一个节点称为头节点,最后一个节点称为尾节点。单向链表的特点是只能从前往后遍历,不能倒序遍历。
单向链表的实现方式有两种:一种是用数组实现,另一种是用指针实现。在用指针实现的单向链表中,每个节点都有一个指向下一个节点的指针,通过指针可以访问链表中的每一个节点。
使用单向链表的场景包括:需要频繁插入和删除元素的数据结构、需要排序的数据结构、需要实现栈和队列等。
以下是一个简单的单向链表实现的 Python 代码示例:
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 not self.head:
self.head = new_node
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
def print_list(self):
cur_node = self.head
while cur_node:
print(cur_node.data, end=" -> ")
cur_node = cur_node.next
print("None")
示例
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.print_list()
CopyCopy
在这个示例中,我们定义了一个 Node 类表示链表中的节点,包含一个 data 属性表示节点数据,一个 next 属性表示下一个节点的指针。LinkedList 类表示单向链表,包含一个 head 属性表示链表的头节点。LinkedList 类还实现了 append 方法用于在链表尾部插入节点,以及 print_list 方法用于遍历链表并打印节点数据。