数据结构 双向链表的创建和读取详解及实例代码

下面我为你详细讲解“数据结构 双向链表的创建和读取详解及实例代码”的完整攻略。

什么是双向链表？

双向链表是一种常见的线性数据结构，与单向链表相比，它可以在节点之间建立双向连接，使得在需要反向遍历链表时效率更高。每个节点同时保存了指向前一个节点和后一个节点的指针，因此双向链表也叫做双链表。

双向链表的创建

定义节点类

首先，我们需要定义一个表示节点的类，该类应该包含以下属性和方法：

• prev：指向前一个节点的指针
• next：指向后一个节点的指针
• data：节点存储的数据

class Node:
    def __init__(self, prev=None, next=None, data=None):
        self.prev = prev
        self.next = next
        self.data = data

创建双向链表

通过定义好表示节点的类，我们可以开始创建双向链表。双向链表创建的基本过程为：

• 创建头结点；
• 逐个添加新节点，并保证前后连接正确，直至链表结尾。

class DoublyLinkedList:
    def __init__(self):
        self.head = Node()

    def add_node(self, data):
        new_node = Node(data=data)
        cur_node = self.head
        while cur_node.next is not None:
            cur_node = cur_node.next
        cur_node.next = new_node
        new_node.prev = cur_node

在上述代码中，我们创建了一个空的链表，即头结点。接下来，我们逐个添加新节点。在添加新节点时，我们首先定义一个Node类的实例new_node，然后将new_node添加到链表结尾。遍历链表需要从头结点self.head开始，逐个向后遍历，直到链表结尾。

示例一

我们来看一个双向链表的创建示例，假设我们需要创建一个双向链表，其中依次包含以下数据：1, 2, 3。

dlist = DoublyLinkedList()
dlist.add_node(1)
dlist.add_node(2)
dlist.add_node(3)

上述代码首先创建了一个双向链表实例dlist，然后依次往链表中添加三个节点，分别存储数据1、2、3。在添加节点时，由于是从头结点开始遍历，因此新节点会依次添加到链表末尾。

双向链表的读取

双向链表的读取可以分为以下几种情况：

• 遍历链表，依次读取每个节点；
• 按下标读取链表中某个位置上的节点；
• 从链表头部或尾部读取节点。

遍历链表

遍历链表需要从头结点开始，依次向后遍历每个节点。

class DoublyLinkedList:
    # ...
    def traverse(self):
        cur_node = self.head
        while cur_node.next is not None:
            cur_node = cur_node.next
            print(cur_node.data)

在上述代码中，我们定义了一个traverse()方法，用于遍历双向链表并依次打印每个节点data值。

示例二

我们来看一个遍历双向链表的示例，假设我们已经创建了一个双向链表实例dlist，其中包含三个节点，对应的数据依次为：1、2、3。

dlist.traverse()

上述代码即可遍历整个链表，并依次打印每个节点的数据。

按下标读取节点

按下标读取节点需要从链表头结点开始遍历，并循环移动到目标下标位置的节点。需要注意的是，由于双向链表支持反向遍历，因此需要根据下标与链表长度的关系进行判断，选择从头部还是尾部开始遍历。

class DoublyLinkedList:
    # ...
    def get_node(self, index):
        # 从头结点开始遍历
        if index < 0:
            return None
        cur_node = self.head
        i = -1
        while i < index and cur_node.next is not None:
            cur_node = cur_node.next
            i += 1
        # 从尾部开始遍历
        if i < index:
            return None
        return cur_node

在上述代码中，我们定义了一个get_node()方法，用于根据下标读取链表中某个位置上的节点。在该方法中，我们首先通过判断下标的正负号来决定是从头部还是尾部开始遍历，然后按照下标逐个移动到目标节点位置并返回。

示例三

我们来看一个按下标读取节点的示例，假设我们已经创建了一个双向链表实例dlist，其中包含三个节点，对应的数据依次为：1、2、3。现在我们需要读取链表中第二个位置上的节点。

node = dlist.get_node(1)
if node is not None:
    print(node.data)

上述代码中，我们通过调用get_node()方法，并传入目标下标1，来获取链表中第二个节点并打印其数据值。

以上就是“数据结构 双向链表的创建和读取详解及实例代码”的完整攻略。需要注意的是，双向链表的操作相对单向链表要复杂一些，尤其是遍历和插入节点等操作中需要考虑的情况比较多，因此在实际开发中需要仔细思考并进行充分测试。