[数据结构与算法]Python LinkedList 单向链表基本实现

链表

链表，Linked List， 是一种非连续，非顺序的数据结构，由若干节点组成。（Node即为节点）

节点

单向链表每个节点包含两个部分。第一个部分用于存放数据变量data，第二个部分则是指针next，用于指向下一个节点。

存储方式

链表的存储方式为随机存储，链表的每一个节点分布在内存的不同位置，靠指针关联。

时间复杂度

优缺点

优点：从存储方式可以看出，链表内存利用率比数组高，数组需要在内存中占用连续完整的储存空间。从上面的时间复杂度可以看出，链表可以灵活的插入或者删除，适合大量添加/删除工作。
缺点：定位元素慢，只能通过遍历整个链表查找

代码实现

# Node
class Node(object):
	def __init__(self, data):
		self.data = data
		self.next = None


# 单向链表
class LinkedList(object):
	"""
	1. init()								初始化无node
	2. is_empty()	# return True/False		是否为空链表
	3. get(index) # return node 			根据下标获取节点
	4. get_node(data) # return node			根据节点数据获取节点
	5. get_index(data) # retrun index		根据节点数据获取下标
	6. insert(node, index) 					插入node到指定位置
	7. add(node)							头插入
	8. append(node)							尾插入
	9. update(data, index)					根据节点下标更新节点数据
	9. travel()								遍历并打印所有node
	10. remove(index) # return node 		删除指定位置node
	11. extend(LinkedList)					合并链表
	12. clear()								清空链表
	"""
	def __init__(self):
		""" 初始化无node """	
		self.size = 0
		self.head = None
		self.tail = None

	def is_empty(self):
		""" 判定是否为空链表 """
		return self.head == None

	def get(self, index):
		""" 查找指定位置节点 """	
		if index < 0 or index >= self.size:
			raise Exception("over range!")
		p = self.head
		for i in range(index):
			p = p.next
		return p 

	def get_node(self, data):
		""" 根据节点数据获取节点 """
		p = self.head
		for i in range(self.size):
			if p.data == data:
				return p
			else:
				p = p.next
		print("The data is not in LinkedList!")

	def get_index(self, data):
		""" 根据节点数据获取第一个出现的节点下标 """
		p = self.head
		for i in range(self.size):
			if p.data == data:
				return i
			else:
				p = p.next
		print("The data is not in LinkedList!")

	def insert(self, node, index):
		""" 插入指定位置节点 """
		if index < 0 or index > self.size:
			raise Exception("over range!")

		if self.size == 0:
			# 空链表
			self.head = node
			self.tail = node
		elif index == 0:  
			# 插入头部
			node.next = self.head
			self.head = node
		elif self.size == index:  
			# 插入尾部
			self.tail.next = node
			self.tail = node
		else:  
			# 插入中间
			prev_node = self.get(index-1)
			node.next = prev_node.next
			prev_node.next = node 

		self.size += 1

	def add(self, node):
		""" 头插入 """
		self.insert(node, 0)

	def append(self, node):
		""" 尾插入 """
		self.insert(node,self.size)

	def update(self, data, index):
		""" 根据节点下标更新节点数据 """
		if index <0 or index >= self.size:
			raise Exception("over range!")
		if index == 0:
			self.head.data = data
		elif index == self.size-1:
			self.tail.data = data
		else:
			p = self.head
			for i in range(index):
				p = p.next
			p.data= data

	def travel(self):
		""" 遍历并打印 """
		p = self.head
		if self.size == 0:
			print("No Data!")
		else:
			while (p != None):
				print(p.data)
				p = p.next

	def remove(self, index):
		""" 删除指定节点 """
		if index <0 or index >= self.size:
			raise Exception("over range!")

		# 需要暂存被删除节点进行返回
		if index == 0:  
			# 删除头节点
			removed_node = self.head
			self.head = self.head.next
		elif index == self.size-1:  
			# 删除尾节点
			prev_node = self.get(index-1)
			removed_node = self.tail
			prev_node.next = None
			self.tail = prev_node
		else:
			# 删除中间节点
			prev_node = self.get(index-1)
			next_node = prev_node.next.next
			removed_node = prev_node.next 
			prev_node.next = next_node

		self.size -= 1
		return removed_node

	def extend(self, item):
		""" 合并两个链表 """
		if item.is_empty():
			raise Exception("LinkedList is empty!")

		self.tail.next = item.head
		self.tail = item.tail
		self.size += item.size

	def clear(self):
		""" 清空链表 """
		self.head = None 
		self.tail = None
		self.size = 0