Python单链表实现与线性表基础解析
本文解析线性表的两种主要形式：顺序表与链表。顺序表支持随机存取但插入删除需移动元素，时间复杂度为O(n)；链表通过指针连接节点，插入删除仅需修改指针，但查找需遍历。文章结合Python代码示例，展示了单链表的节点定义、基本操作及静态链表在缺乏原生指针语言中的实现思路，涵盖循环链表与双向链表的特性。
近期研读数据结构相关书籍后认识到，数据结构的核心类型相对有限，主要包括线性表（如数组、字符串、队列和栈等，它们在本质上有共通之处）以及树结构和图结构。掌握数据结构的理论框架并不复杂，关键在于通过亲手编写这些数据结构及其基本操作方法来进行实践，这样才能有效提升编程能力。
本篇博客将重点介绍线性表的相关内容。
线性表主要包含两种实现方式：顺序表和链表。
一、顺序表
顺序表中，数据元素在内存中的地址是连续的，因此支持随机存取。然而，在执行插入或删除操作时，为了保持地址的连续性，往往需要移动大量元素，导致插入或删除单个元素的时间复杂度为O(n)。在对顺序表进行合并操作时，通常建议先对表内元素进行排序，再执行后续处理，这样可以避免每次都需要从头开始查询，从而提高效率。
二、链表
链表放弃了顺序表的随机存取特性，这意味着每次获取元素都必须从头节点开始遍历查找，导致查找操作的时间复杂度为O(n)。不过，链表在插入、删除以及合并两个链表时具有显著优势，仅需修改少量指针即可完成操作，无需移动大量数据。
链表中的每个节点由数据部分和指向下一个节点的指针组成。通常在链表头部设置一个头结点，该头结点一般不存储实际数据，而是用于存放长度等附加信息，或者干脆不存储任何内容。
在许多编程语言（如Java和Python）中，并没有直接的“指针”概念，而是使用数组。Java中的数组要求定义统一的数据类型，而Python的列表（list）则没有类型限制，因此Python的list在某种程度上更贴近链表的实际含义。这种利用数组来模拟链表的结构被称为静态链表。对于这类语言，使用静态链表来描述链表结构会更加便捷，因为这些语言通常已经提供了内置类来处理链表操作。
此外，还有循环链表和双向链表等变体。双向链表解决了单向链表无法向前搜索的问题，但在修改指针时需要执行更多的操作。
# -*- coding=utf-8 -*-
# 这个例子是Python版本的单链表
class Node(object):
def __init__(self, value, next=0):
self.value = value
self.next = next # 指针
class LinkedList(object):
# 链表的数据结构
def __init__(self):
self.head = 0 # 头部
def __getitem__(self, key):
if self.is_empty():
print 'Linked list is empty.'
return
elif key < 0 or key > self.get_length():
print 'The given key is wrong.'
return
else:
return self.get_elem(key)
def __setitem__(self, key, value):
if self.is_empty():
print 'Linked list is empty.'
return
elif key < 0 or key > self.get_length():
print 'The given key is wrong.'
return
else:
return self.set_elem(key, value)
def init_list(self, data): # 按列表给出 data
self.head = Node(data[0])
p = self.head # 指针指向头结点
print p, self.head
for i in data[1:]:
p.next = Node(i) # 确定指针指向下一个结点
p = p.next # 指针滑动向下一个位置
print self.head.next.next
def get_length(self):
length = 0
p = self.head
while p != 0: # 0 值就是Node结点中默认的 0 值，表示下一个结点没有了，即没有为其赋值
length += 1
p = p.next
return length
def is_empty(self):
if self.head == 0:
return True
else:
return False
def insert_node(self, index, value):
if index < 0 or index > self.get_length():
print 'Can not insert node into the linked list.'
elif index == 0:
temp = self.head
self.head = Node(value, temp)
else:
p, post = self.head, self.head
for i in xrange(index):
post = p
p = p.next
temp = p
post.next = Node(value, temp)
def delete_node(self, index):
if index < 0 or index > self.get_length()-1:
print "Wrong index number to delete any node."
elif self.is_empty():
print "No node can be deleted."
elif index == 0:
temp = self.head
self.head = temp.next
elif index == self.get_length():
p = self.head
for i in xrange(self.get_length()-2):
p = p.next
p.next = 0
else:
p = self.head
for i in xrange(index-1):
p = p.next
p.next = p.next.next
def show_linked_list(self): # 打印链表中的所有元素
if self.is_empty():
print 'This is an empty linked list.'
else:
p, container = self.head, []
for _ in xrange(self.get_length()-1):
container.append(p.value)
p = p.next
container.append(p.value)
print container
def clear_linked_list(self): # 将链表置空
self.head = 0
def get_elem(self, index):
if self.is_empty():
print "The linked list is empty. Can not get element."
elif index < 0 or index > self.get_length()-1:
print "Wrong index number to get any element."
else:
p = self.head
for _ in xrange(index):
p = p.next
return p.value
def set_elem(self, index, value):
if self.is_empty():
print "The linked list is empty. Can not set element."
elif index < 0 or index > self.get_length()-1:
print "Wrong index number to set element."
else:
p = self.head
for _ in xrange(index):
p = p.next
p.value = value
def get_index(self, value):
p = self.head
for i in xrange(self.get_length()):
if p.value == value:
return i
else:
p = p.next
return -1
l = LinkedList()
print "The length of linked list now is: ", l.get_length()
print l.is_empty()
l.init_list([1, 5, 12, "fjd", 45, 999])
print "The length of linked list now is: ", l.get_length()
print l.is_empty()
l.insert_node(4, 100)
l.insert_node(6, "cecil")
l.show_linked_list()
print "The value of index 0 is: ", l.get_elem(0)
l.set_elem(0,1000)
l.show_linked_list()
print "the index of *** is: ", l.get_index(1009)
print "The length of linked list now is: ", l.get_length()
l.delete_node(3)
#l.clear_linked_list()
l.show_linked_list()
以上内容即为本文的全部介绍，希望能为读者的学习带来帮助，同时也欢迎大家继续支持本站。
本站声明
本文内容仅供参考，不代表本站观点。转载或引用请注明出处。如发现内容问题，请通过联系我们页面反馈。
