双向链表 灰太狼 2022-12-21 04:54 210阅读 0赞 一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接:一个指向前一个节点,当此节点为第一个节点时,指向空值;而另一个指向下一个节点,当此节点为最后一个节点时,指向空值。 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIwMDQyOTM1_size_16_color_FFFFFF_t_70] ## 操作 ## * is\_empty() 链表是否为空 * length() 链表长度 * travel() 遍历链表 * add(item) 链表头部添加 * append(item) 链表尾部添加 * insert(pos, item) 指定位置添加 * remove(item) 删除节点 * search(item) 查找节点是否存在 ## 实现 ## class Node(object): """双向链表节点""" def __init__(self, item): self.item = item self.next = None self.prev = None class DLinkList(object): """双向链表""" def __init__(self): self._head = None 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): """遍历链表""" cur = self._head while cur != None: print cur.item, cur = cur.next print "" def add(self, item): """头部插入元素""" node = Node(item) if self.is_empty(): # 如果是空链表,将_head指向node self._head = node else: # 将node的next指向_head的头节点 node.next = self._head # 将_head的头节点的prev指向node self._head.prev = node # 将_head 指向node self._head = node def append(self, item): """尾部插入元素""" node = Node(item) if self.is_empty(): # 如果是空链表,将_head指向node self._head = node else: # 移动到链表尾部 cur = self._head while cur.next != None: cur = cur.next # 将尾节点cur的next指向node cur.next = node # 将node的prev指向cur node.prev = cur def search(self, item): """查找元素是否存在""" cur = self._head while cur != None: if cur.item == item: return True cur = cur.next return False 指定位置插入节点 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIwMDQyOTM1_size_16_color_FFFFFF_t_70 1] def insert(self, pos, item): """在指定位置添加节点""" if pos <= 0: self.add(item) elif pos > (self.length()-1): self.append(item) else: node = Node(item) cur = self._head count = 0 # 移动到指定位置的前一个位置 while count < (pos-1): count += 1 cur = cur.next # 将node的prev指向cur node.prev = cur # 将node的next指向cur的下一个节点 node.next = cur.next # 将cur的下一个节点的prev指向node cur.next.prev = node # 将cur的next指向node cur.next = node 删除元素 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIwMDQyOTM1_size_16_color_FFFFFF_t_70 2] def remove(self, item): """删除元素""" if self.is_empty(): return else: cur = self._head if cur.item == item: # 如果首节点的元素即是要删除的元素 if cur.next == None: # 如果链表只有这一个节点 self._head = None else: # 将第二个节点的prev设置为None cur.next.prev = None # 将_head指向第二个节点 self._head = cur.next return while cur != None: if cur.item == item: # 将cur的前一个节点的next指向cur的后一个节点 cur.prev.next = cur.next # 将cur的后一个节点的prev指向cur的前一个节点 cur.next.prev = cur.prev break cur = cur.next 测试 if __name__ == "__main__": ll = DLinkList() ll.add(1) ll.add(2) ll.append(3) ll.insert(2, 4) ll.insert(4, 5) ll.insert(0, 6) print "length:",ll.length() ll.travel() print ll.search(3) print ll.search(4) ll.remove(1) print "length:",ll.length() ll.travel() [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIwMDQyOTM1_size_16_color_FFFFFF_t_70]: /images/20221120/77616a06508a46989b67556248bb8ce1.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIwMDQyOTM1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190820175340922.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIwMDQyOTM1,size_16,color_FFFFFF,t_70 [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIwMDQyOTM1_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20190820175404247.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIwMDQyOTM1,size_16,color_FFFFFF,t_70
相关 双向链表 一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接:一个指向前一个节点,当此节点为第一个节点时,指向空值;而另一个指向下一个节点,当此节点为最后一个节点时,指向空 灰太狼/ 2022年12月21日 04:54/ 0 赞/ 211 阅读
相关 双向链表 一:双向链表 双向链表的节点包含数据域,前置指针域和后置指针域 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_ ゝ一世哀愁。/ 2022年11月05日 12:57/ 0 赞/ 212 阅读
相关 双向链表 APUE 308页 线程学习时候有一个链表 struct job{ struct job next; struct job prev; 古城微笑少年丶/ 2022年08月05日 05:20/ 0 赞/ 212 阅读
相关 双向链表 前面叙述了关于单链表、双端链表、有序链表的结点插入以及遍历查找等示例。这几种链表都只能从前往后进行遍历,反向遍历是非常麻烦的一件事。 考虑一下下面这个情况:如果文本编辑 亦凉/ 2022年07月18日 05:29/ 0 赞/ 239 阅读
相关 双向链表 一、解析 在单链表中,有了next指针,要查找下一节点的时间复杂度为O(1),如果要查找的是上一节点的话,最坏的时间复杂度是O(n)了,以为每次都要从头开始查找。为了克服这个 「爱情、让人受尽委屈。」/ 2022年07月03日 13:57/ 0 赞/ 295 阅读
相关 双向链表 /双向链表/ include<stdio.h> typedef struct dbnode { int num; 骑猪看日落/ 2022年06月16日 13:08/ 0 赞/ 229 阅读
相关 双向链表和双向循环链表 双向链表和双向循环链表 和单向链表相比,多了一个前驱结点。如果他为空,那么next和prior都指向自己。而对于双循环链表,只需要最后一个元素的next指向head->n ╰+哭是因爲堅強的太久メ/ 2022年05月16日 01:29/ 0 赞/ 294 阅读
相关 双向链表 Problem Description 学会了单向链表,我们又多了一种解决问题的能力,单链表利用一个指针就能在内存中找到下一个位置,这是一个不会轻易断裂的链。但单链表有一个弱 忘是亡心i/ 2022年05月10日 04:34/ 0 赞/ 302 阅读
相关 双向链表 题目描述 构建一个双向链表并进行删除和插入操作,按要求输出。 输入 输入: 第一行输入元素个数M 第二行输入M个元素 第三行输入删除位置 第四行输入插入位 野性酷女/ 2022年04月04日 05:48/ 0 赞/ 282 阅读
相关 双向链表 【一】双向链表 > 单向链表,查找的只能是一个方向,而双向链表可以向前或向后查找。 > 单向链表不能自我删除,需要靠辅助节点;而双向链表可以自我删除 > 双向链表中的 小咪咪/ 2021年08月12日 00:11/ 0 赞/ 460 阅读
还没有评论,来说两句吧...