数据结构是大学必修的一门课程。每一位开发人员从开始工作就在接触数据结构,一直贯穿整个职业生涯,除非你转向其它行业。所以数据结构是很重要的一门课程。

       数据结构包括线性数据结构、树等。其中线性结构包括: 链表、堆栈、队列、双端队列、环状队列等。树包括:二叉树、二叉堆、二叉查找树、平衡二叉树等。其实数据结构的知识还是很多的,今天咱们就说一下线性结构中的链表数据结构。

       谈到链表之前,先说一下线性表。线性表是最基本、最简单也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是收尾相接的。线性表友两种存储方式,一种是顺序存储结构,另外一种是链表存储结构。

        顺序存储结构就是两个相邻的元素在内存中也是相邻的。这种存储方式的优点是查询的时间复杂度为O(1),通过首地址和偏移量就可以直接访问到该元素,关于查找的适配算法很多,最快可以达到O(logn)。缺点是插入和删除的时间复杂度最坏能达到O(n),如果你在第一个位置插入一个元素,你需要把数组的每一个元素向后移动一位,如果你在第一个位置删除一个元素,你需要把数组的每一个元素向前移动一位。还有一个缺点,就是当你不确定元素的数量时,你开的数组必须保证能够放下元素最大数量,遗憾的是如果实际数量比最大数量少很多时,你开的数组没有用到的内存就只能浪费掉了。

       我们常用的数组就是一种典型的顺序存储结构.

      

       链表存储结构就是两个相邻的元素在内存中可能不是相邻的,每一个元素都有一个指针域,指针域一般是存储着到下一个元素的指针。这种存储方式的优点是插入和删除的时间复杂度为O(1),不会浪费太多内存,添加元素的时候才会申请内存,删除元素会释放内存。缺点是访问的时候时间复杂度最坏为O(n),关于查找的算法很少,一般只能遍历,这样时间复杂度也是线性(O(n))的了,频繁的申请和释放内存也会消耗时间。

       顺序表的特性是随机读取,也就是访问一个元素的时间复杂度是O(1),链式表的特性是插入和删除的时间复杂度为O(1)。要根据实际情况去选取适合自己的存储方式.

       链表就是链式存储的线性表。根据指针域的不同,链表分为单向链表、双向链表和循环链表等。

       咱们今天用python来实现一个单向链表,每个元素博阿含两个域。值域和指针域,我们把这样的元素称之为节点。每个节点的指针域内有一个指针,指向下一个节点,而最后一个节点则指向一个空值。

        

        一个单向链表的节点被分成两个部分。第一部分保存或者显示关于节点的信息,第二部分存储下一个节点的地址。单向链表只可向一个方向遍历。

        下面用python来实现一个单向链表。 

#LinkList.py

class Node:
	'''该类实例化一个元素节点.'''

	def __init__(self, data):
		self.data = data
		self.next = None


class LinkedList:
	'''实现一个单向链表.'''

	def __init__(self):
		'''初始化链表.
		初始化时,为一个空链表.链表有两个标示head和tail都赋值None.
		'''
		self.head = None
		self.tail = None

	def append(self, data):
		'''向链表新增元素.
		1. 如果该链表是一个空链表,则链表head和tail都指向传进来的node节点.
		2. 如果链表非空,则self.tail.next = node.next 指向新插入元素.
		   tail指向新插入的元素节点.
		'''
		node = Node(data)
		if self.head is None:
			self.head = node
			self.tail = node
		else:
			self.tail.next = node
			self.tail = node

	def insert(self, idx, value):
		'''向链表插入一个元素node.
        1. 从链表头开始遍历链表,当查找的index小于要插入索引的位置时,依次
           指向下一个元素节点.直到找到要插入节点的索引位置.
        2. 首先将插入的值,通过Node类实例化一个元素node.然后将它的next指针
           指向它的下一个元素.即当前新元素节点之前的元素索引位置.
        3. 将当前元素索引指向新插入元素node.
		'''
		cur = self.head
		cur_idx = 0
		while cur_idx < idx - 1:
			cur = cur.next
			if cur.next is None:
				raise Exception('list length less than index')
			cur_idx += 1
		node = Node(value)
		node.next = cur.next
		cur.next = node
		if cur.next is None:
			self.tail = node

	def inter(self):
		'''返回一个链表迭代器.
        1. 首先判断该链表是否为一个空链表。如果时一个空链表,直接返回.
        2. 如果是一个非空链表,首先指针指向head节点,然后将head节点data
           返回.然后while循环,条件是下一个指针元素为真.然后弹出下一个元
           素data,直到遍历到最后一个元素.
		'''
		if not self.head:
			return
		cur = self.head
		yield cur.data
		while cur.next:
			cur = cur.next
			yield cur.data

    def remove(self, idx):
    	'''从链表中删除一个元素节点.
        1. 首先找到要删除的元素节点索引.
        2. 然后将当前节点的next指向下一个下一个元素节点.
    	'''
    	cur = self.head
    	cur_idx = 0
    	while cur_idx < idx-1:
    		cur = cur.next
    		if cur is None:
    			raise Exception('list length less than index')
    		cur_idx +=1
    	cur.next = cur.next.next
    	if cur.next is None:
    		self.tail = cur

if __name__ == "__main__":
	linked_list = LinkedList()

	# 循环插入元素
	for i in range(10):
		linked_list.append(i)

	# 向元素插入一个元素
	linked_list.insert(3, 40)

	# 向元素删除一个元素
	linked_list.remove(4)

	# 遍历该链表
	for node in linked_list.inter():
		print(node)