Python3数据结构03 - 双向链表

  • 原创
  • Madman
  • /
  • 2018-09-04 14:08
  • /
  • 0
  • 130 次阅读

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 = cur.next  # 向后移动游标

2.4 在尾部添加元素

首先需要找到尾节点,方法是定义cur游标(指示当前节点)遍历链表,当cur.next是None时,就表示找到了尾节点。然后,将尾节点的next指向新增节点,并将新增节点的prev指向尾节点

def append(self, value):
    '''在链表的尾部添加节点。注意:传入的 value 是节点的值'''
    node = Node(value)

    if self.is_empty():  # 如果是空链表
        self.__head = node
    else:
        cur = self.__head  # 游标,用来表示当前节点
        # 遍历链表,直到找到了尾节点后,退出循环
        while cur.next is not None:
            cur = cur.next
        # 此时,cur 表示尾节点
        cur.next = node  # 将尾节点的 next 指向新增节点
        node.prev = cur  # 将新增节点的 prev 指向尾节点

2.5 在头部插入元素

需要先将新增节点的next指向原来的头节点,再将原来的头节点的prev指向新增节点,最后将链表对象的__head属性重新指向新增节点,顺序不能倒置,否则将丢失之前所有节点

def head_add(self, value):
    '''在链表的头部添加节点'''
    node = Node(value)

    if self.is_empty():  # 如果是空链表
        self.__head = node
    else:
        node.next = self.__head  # 1. 将新增节点的 next 指向原来的头节点
        node.next.prev = node  # 2. 再将原来的头节点的 prev 指向新增节点
        self.__head = node  # 3. 最后将链表的 __head 属性指向新增节点即可

2.6 在指定位置插入元素

该方法需要传入下标pos和元素的值,为了跟列表等一样,这里规定pos从0开始计数,即头节点的pos为0

在指定位置pos插入元素,我们只需要找到pos所在位置的节点,这里用cur游标来表示它

def insert(self, pos, value):
    '''在指定位置添加节点。 pos 表示节点的下标,为了跟列表等一样,这里规定 pos 从0开始计数,即头节点的 pos 为0'''
    if pos <= 0:  # 暂时不支持负数的下标。如果传入负数或者0,统一在头部插入
        self.head_add(value)
    elif pos > self.length() - 1:  # 如果传入的下标大于链表的长度减去1,默认使用在尾部插入
        self.append(value)
    else:
        cur = self.__head  # 游标,用来表示 pos 位置的节点
        count = 0
        while count < pos:  # 当count = pos 时,表示已经找到了 pos 的节点,退出循环
            count += 1
            cur = cur.next  # 向后移动游标
        # 退出循环后,cur 指向 pos 所在的节点
        node = Node(value)
        node.next = cur  # 1. 将新增节点的 next 指向 cur
        node.prev = cur.prev  # 2. 将新增节点的 prev 指向 cur 的前驱节点
        cur.prev.next = node  # 3. 将 cur 的前驱节点的 next 重新指向新增节点
        cur.prev = node  # 4. 将 cur 的 prev 重新指向新增节点

2.7 查看元素是否在链表中

逻辑跟遍历链表类似,每遍历一个节点时,比较节点的值是否与要查找的元素相等,如果相等则直接返回True,否则继续向后遍历。注意,while循环条件不能遗忘尾节点

def search(self, value):
    '''查找指定的元素值是否在链表中,也适合空链表的情况'''
    cur = self.__head
    while cur is not None:
        if cur.value == value:
            return True
        else:
            cur = cur.next
    return False  # 遍历完整个链表也没找到时

2.8 在链表中删除指定元素值

使用cur游标指示遍历过程中的当前节点,如果cur.value与要删除的元素值相等时,表示找到了要删除的节点

def remove(self, value):
    '''在链表中删除指定元素值,跟列表中的 remove() 类似,也是删除第一个遇到的元素'''
    cur = self.__head

    while cur is not None:  # 向后遍历链表
        if cur.value == value:  # 表示找到了要删除的节点,此时,cur 指向要删除的节点
            if cur.prev is None:  # 特殊情况1: 如果要删除的节点是头节点时
                if cur.next is None:  # 特殊情况2: 链表只有一个节点,刚好它就是要删除的节点,此时 cur.next 是 None
                    self.__head = None  # 变回空链表
                else:  # 链表不只一个节点
                    self.__head = cur.next
                    cur.next.prev = None  # 将 cur 的后继节点的 prev 重新指向 None,因为它现在是新的头节点了
            elif cur.next is None:  # 特殊情况3: 如果要删除的节点是尾节点时,cur.next是None
                cur.prev.next = None
            else:
                cur.prev.next = cur.next  # 1. 将 cur 的前驱节点的 next 重新指向 cur 的后继节点
                cur.next.prev = cur.prev  # 2. 将 cur 的后继节点的 prev 重新指向 cur 的前驱节点,这样 cur 就从双向链表中退出来了

            # 当找到要删除的节点时,需要退出 while 循环
            break
        else:
            cur = cur.next  # 向后移动

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

未经允许不得转载: LIFE & SHARE - 王颜公子 » Python3数据结构03 - 双向链表

分享

作者

作者头像

Madman

如果博文内容有误或其它任何问题,欢迎留言评论,我会尽快回复; 或者通过QQ、微信等联系我

0 条评论

暂时还没有评论.

发表评论前请先登录