Python数据结构与算法——第3-9课时——双向链表及添加元素、判断链表是否为空——day67

Python数据结构与算法:第3-9课时:双向链表及添加元素、判断链表是否为空

双向链表

《Python数据结构与算法——第3-9课时——双向链表及添加元素、判断链表是否为空——day67》
《Python数据结构与算法——第3-9课时——双向链表及添加元素、判断链表是否为空——day67》
后继节点,某个节点,前驱节点。

例子:

比如40这个节点的前驱节点就是100, 后继节点就是6
《Python数据结构与算法——第3-9课时——双向链表及添加元素、判断链表是否为空——day67》

定义:

一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接:一个指向前一个节点,当此节点为第一个节点时,指向空值;而另一个指向下一个节点,当此节点为最后一个节点时,指向空值。

所需要的一些操作:

• 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

self.next 为后继节点的地址,
prev 为前继节点的地址。

双链列表定义的代码:

只需要顶一个函数头就可以了,和单链列表一样。

class DLinkList(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):
    """遍历链表"""
    cur = self._head
    while cur != None:
        print(cur.item)
        cur = cur.next

在头部插入一个节点 add:

《Python数据结构与算法——第3-9课时——双向链表及添加元素、判断链表是否为空——day67》
让 之前表头self._head指向 新节点node地址。

实现代码:

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 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.next = cur
        # 将node的next指向cur的下一个节点
        node.prev = cur.prev
        # 将cur的下一个节点的prev指向node
        cur.prev.next = node
        # 将cur的next指向node
        cur.prev = node
    原文作者:冬 泳 怪 鸽
    原文地址: https://blog.csdn.net/asd1103810477/article/details/108552742
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞