03-13 5,783 views
数据结构是大学必修的一门课程。每一位开发人员从开始工作就在接触数据结构,一直贯穿整个职业生涯,除非你转向其它行业。所以数据结构是很重要的一门课程。
数据结构包括线性数据结构、树等。其中线性结构包括: 链表、堆栈、队列、双端队列、环状队列等。树包括:二叉树、二叉堆、二叉查找树、平衡二叉树等。其实数据结构的知识还是很多的,今天咱们就说一下线性结构中的链表数据结构。
谈到链表之前,先说一下线性表。线性表是最基本、最简单也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是收尾相接的。线性表友两种存储方式,一种是顺序存储结构,另外一种是链表存储结构。
顺序存储结构就是两个相邻的元素在内存中也是相邻的。这种存储方式的优点是查询的时间复杂度为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)