Python3数据结构03 - 双向链表

  • 原创
  • Madman
  • /
  • /
  • 0
  • 2178 次阅读

Synopsis: 前两篇介绍了顺序表和链表中的单链表,本文将介绍链表的另一种实现:双向链表,它的每个节点和两个指针域,分别指向前驱节点和后继节点。从双向链表中的任意一个节点开始,都可以很方便地访问它的前驱节点和后继节点

代码已上传到 https://github.com/wangy8961/python3-algorithms ,欢迎star

1. 双向链表

双向链表(Doubly linked list),又称为双链表,是链表的一种,它的每个数据节点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个节点开始,都可以很方便地访问它的前驱节点和后继节点。一般我们都构造双向循环链表

2. Python实现

接下来我们使用Python 3来构建双向链表数据结构,首先需要定义一个节点类:

class Node:
    '''双向链表的节点'''
    def __init__(self, value):
        self.value = value  # 节点的信息域
        self.prev = None    # 指针域,指向前驱节点
        self.next = None    # 指针域,指向后继节点

    def __repr__(self):
        return 'Node({!r})'.format(self.value)

然后定义双向链表类:

class DoublyLinkedList:
    def __init__(self, node=None):
        '''创建一个双向链表对象时,如果不传入头节点,则创建空链表'''
        self.__head = node

2.1 判断是否空链表

只需要判断单链表的__head属性是否为None即可,如果是None表示没有头节点,则是空链表

def is_empty(self):
    '''判断是否为空链表'''
    return self.__head is None

2.2 求链表的长度

定义一个游标cur,用来表示遍历到的当前节点,初始时等于链表的头节点(即cur = self.__head)。count变量用于统计已遍历了多少个节点,初始时等于0。当cur移动到尾节点时,cur.next == None,此时再将cur往后移动时,需要退出while循环

该方法最后返回count即可

def length(self):
    '''求链表的长度'''
    cur = self.__head  # 游标,用来表示当前节点
    count = 0  # 用来统计已遍历的节点数目

    # 1. 如果是空链表,self.__head为None,则cur为None,不会进入循环体,最后返回 count = 0,符合
    # 2. 如果不是空链表,当cur移动到尾节点时,cur.next 是None,循环体中的 cur = cur.next 会让 cur = None,继续往后移动时会退出循环
    while cur is not None:
        count += 1
        cur = cur.next  # 向后移动游标

    return count

2.3 遍历链表

逻辑跟求长度一样,注意,这里使用生成器语法,将每个节点的值产出供客户代码使用

def travel(self):
    '''遍历整个链表'''
    cur = self.__head  # 游标,用来表示当前节点
    while cur is not None:
        yield cur.value  # 生成当前节点的值
        cur = 
                                
                            
未经允许不得转载: LIFE & SHARE - 王颜公子 » Python3数据结构03 - 双向链表

分享

作者

作者头像

Madman

如需 Linux / Python 相关问题付费解答,请按如下方式联系我

0 条评论

暂时还没有评论.

专题系列