3.链表(python数据结构与算法学习) 系统管理员 2021-05-12 11:50 633阅读 0赞 ### 为什么需要链表 ### 顺序表的构建需要预先知道数据大小来申请连续的存储空间,而在进行扩充时又需要进行数据的搬迁,所以使用起来并不是很灵活。 链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。 ### 链表的定义 ### 链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是不像顺序表一样连续存储数据,而是在每一个节点(**数据存储区+下个节点链接区**)里存放下一个节点的位置信息(**即地址**)。 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70] ## 3.1 单向链表 ## 单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个**信息域**(元素域)和一个**链接域**。这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值。 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70 1] * 表元素域elem用来存放具体的数据。 * 链接域next用来存放下一个节点的位置(python中的标识) * 变量p指向链表的头节点(首节点)的位置,从p出发能找到表中的任意节点。 ### 节点实现(对应上图中的结点) ### class Node(object): """单链表结点""" def __init__(self, elem): self.elem = elem # 存放元素 self.next = None # 指向下一个结点 ### 单链表的操作(函数从简至繁) ### * is\_empty() 链表是否为空 * length() 链表长度 * travel() 遍历整个链表 * add(item) 链表头部添加元素 * append(item) 链表尾部添加元素 * search(item) 查找节点是否存在 * remove(item) 删除节点 * insert(pos, item) 指定位置添加元素 ### 单链表的实现 ### class SingleLinkList(object): """单链表""" def __init__(self, node=None): self.__head = node # 初始化头结点的指向 def is_empty(self): """链表是否为空""" return self.__head == None #### 链表长度 #### def length(self): """链表长度""" count = 0 cur = self.__head while cur != None: count += 1 cur = cur.next return count #### 遍历整个链表 #### def travel(self): """遍历整个链表""" cur = self.__head while cur != None: print(cur.elem) cur = cur.next #### 链表头部添加元素 #### ![在这里插入图片描述][20200604103017603.png] def add(self, item): """链表头部添加元素""" node = Node(item) node.next = self.__head # 4行5行代码不可交换顺序 self.__head = node #### 链表尾部添加元素 #### def append(self, item): """链表尾部添加元素""" node = Node(item) cur = self.__head if self.is_empty(): # 假如一开始链表就为空 self.__head = node else: while cur.next != None: cur = cur.next cur.next = node #### 查找结点是否存在 #### def search(self, item): """查找节点是否存在""" cur = self.__head while cur != None: if cur.elem == item: return "该节点存在" else: cur = cur.next return "该节点不存在" #### 删除结点 #### ![在这里插入图片描述][2020060410302724.png] def remove(self, item): """删除节点""" cur = self.__head pre = None while cur != None: if cur.elem == item: if pre == None: # 考虑链表只有一个结点,而且该结点正好需要删除 self.__head = cur.next else: pre.next = cur.next return "节点已删除" else: pre = cur cur = cur.next return "该链表中不存在您想删除的节点" #### 指定位置添加元素 #### ![在这里插入图片描述][2020060410303764.png] def insert(self, pos, item): """指定位置添加元素""" if pos <= 0: self.add(item) elif pos >= self.length(): self.append(item) else: count = 0 cur = self.__head pre = None while count < pos: pre = cur cur = cur.next count += 1 node = Node(item) pre.next = node node.next = cur print("插入完成") ### 链表与顺序表的对比 ### 链表失去了顺序表随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大,但对存储空间的使用要相对灵活。 链表与顺序表的各种操作复杂度如下所示: <table> <thead> <tr> <th>操作</th> <th align="center">链表</th> <th>顺序表</th> </tr> </thead> <tbody> <tr> <td>访问元素</td> <td align="center">O(n)</td> <td>O(1)</td> </tr> <tr> <td>在头部插入/删除</td> <td align="center">O(1)</td> <td>O(n)</td> </tr> <tr> <td>在尾部插入/删除</td> <td align="center">O(n)</td> <td>O(1)</td> </tr> <tr> <td>在中间插入/删除</td> <td align="center">O(n)</td> <td>O(n)</td> </tr> </tbody> </table> **注意**:虽然表面看起来复杂度都是 O(n),但是链表和顺序表在插入和删除时进行的是完全不同的操作。**链表**的主要耗时操作是遍历查找,删除和插入操作本身的复杂度是O(1)。**顺序表**查找很快,主要耗时的操作是拷贝覆盖。因为除了目标元素在尾部的特殊情况,顺序表进行插入和删除时需要对操作点之后的所有元素进行前后移位操作,只能通过拷贝和覆盖的方法进行。 ## 3.2 单向循环列表 ## 单链表的一个变形是单向循环链表,链表中最后一个结点的next域不再为None,而是指向链表的头结点。 ![在这里插入图片描述][2020060410304850.png] ### 单向循环列表的操作(参考单链表) ### * is\_empty() 判断链表是否为空 * length() 返回链表的长度 * travel() 遍历 * add(item) 在头部添加一个节点 * append(item) 在尾部添加一个节点 * insert(pos, item) 在指定位置pos添加节点 * remove(item) 删除一个节点 * search(item) 查找节点是否存在 #### 实现: #### class Node(object): """单向循环链表结点""" def __init__(self, elem): self.elem = elem self.next = None class SingleCycleLink(object): """单向循环链表""" def __init__(self, node=None): self.__head = node if node != None: node.next = self.__head def is_empty(self): """判断链表是否为空""" return self.__head == None def length(self): """返回链表的长度""" if self.is_empty(): return 0 count = 1 cur = self.__head while cur.next != self.__head: count += 1 cur = cur.next return count def travel(self): """遍历""" if self.is_empty(): print(None) return cur = self.__head while cur.next != self.__head: print(cur.elem) cur = cur.next print(cur.elem) def add(self, item): """在头部添加一个节点""" node = Node(item) if self.is_empty(): self.__head = node node.next = self.__head cur = self.__head while cur.next != self.__head: cur = cur.next cur.next = node node.next = self.__head self.__head = node def append(self, item): """在尾部添加一个节点""" node = Node(item) if self.is_empty(): self.__head = node node.next = self.__head cur = self.__head while cur.next != self.__head: cur = cur.next cur.next = node node.next = self.__head def insert(self, pos, item): """在指定位置pos添加节点""" if pos <= 0: self.add(item) elif pos >= (self.length()): self.append(item) else: cur = self.__head pre = None node = Node(item) count = 0 while count < pos: count += 1 pre = cur cur = cur.next pre.next = node node.next = cur def remove(self, item): """删除一个节点""" if self.is_empty(): print("链表为空") return pre = None cur = self.__head while cur.next != self.__head: # 头结点 if cur == self.__head: # 找到尾结点 end_cur = self.__head while end_cur.next != self.__head: end_cur = end_cur.next if cur.elem == item: self.__head = cur.next end_cur.next = self.__head return else: # 中间结点 if cur.elem == item: pre.next = cur.next return pre = cur cur = cur.next # 尾结点 if cur.elem == item: if cur == self.__head: # 链表只有一个结点 self.__head = None else: pre.next = cur.next def search(self, item): """查找节点是否存在""" if self.is_empty(): print("链表为空") return else: cur = self.__head while cur.next != self.__head: if cur.elem == item: print("该结点存在") return else: cur = cur.next if cur.elem == item: print("该结点存在") return print("该结点不存在") ## 3.3 双向链表 ## 一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接:一个指向前一个节点,当此节点为第一个节点时,指向空值;而另一个指向下一个节点,当此节点为最后一个节点时,指向空值。 ![在这里插入图片描述][20200604103108751.png] ### 双向链表的操作(参考单链表) ### * is\_empty() 链表是否为空 * length() 链表长度 * travel() 遍历链表 * add(item) 链表头部添加 * append(item) 链表尾部添加 * insert(pos, item) 指定位置添加 * remove(item) 删除节点 #### 实现: #### class Node(object): """双链表结点""" def __init__(self, elem): self.elem = elem self.prev = None self.next = None class DoubleLinkList(object): """双链表""" def __init__(self, node=None): self.__head = node def is_empty(self): """链表是否为空""" return self.__head == None def length(self): """链表长度""" cur = self.__head count = 0 while cur != None: count += 1 cur = cur.next return count def travel(self): """遍历链表""" if self.is_empty(): print("该链表为空。无法遍历") cur = self.__head while cur != None: print(cur.elem) cur = cur.next def add(self, item): """链表头部添加""" node = Node(item) if self.is_empty(): self.__head = node else: node.next = self.__head self.__head.prev = node self.__head = node def append(self, item): """链表尾部添加""" node = Node(item) if self.is_empty(): self.__head = node else: cur = self.__head while cur.next != None: cur = cur.next cur.next = node node.prev = cur def insert(self, pos, item): """指定位置添加""" if pos <= 0: self.add(item) elif pos >= self.length(): self.append(item) else: node = Node(item) count = 0 cur = self.__head while count < pos: count += 1 cur = cur.next node.next = cur node.prev = cur.prev cur.prev.next = node cur.prev = node def remove(self, item): """删除节点""" if self.is_empty(): print("该链表为空,无法删除结点") else: cur = self.__head while cur != None: if cur.elem == item: if cur.prev != None: cur.prev.next = cur.next else: self.__head = cur.next if cur.next != None: cur.next.prev = cur.prev break cur = cur.next def search(self, item): """查找节点是否存在""" cur = self.__head while cur != None: if cur.elem == item: return "该结点存在" cur = cur.next return "该结点不存在" [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70]: /images/20210511/c1a81e20e8a549d6b9532da9921a8156.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70 1]: /images/20210511/35bf521bf05c44b08c1db86e98ca7544.png [20200604103017603.png]: /images/20210511/6cb74e865c51456d805724e43633b414.png [2020060410302724.png]: /images/20210511/81ee6fff236d4296841cd947eed4acd1.png [2020060410303764.png]: /images/20210511/805eec188cdb42859ab809ac1dba0911.png [2020060410304850.png]: /images/20210511/f95dc367bfa8482bb144c0233c79dfb6.png [20200604103108751.png]: /images/20210511/6f4cc36006f74af19b5da0895f2c4e63.png
还没有评论,来说两句吧...