科技园区建设网站的意义,达州达县网站建设,鞍山做网站公司,网站网络优化外包在前面我们学习了单链表#xff0c;发现单链表还是有一些不够方便#xff0c;比如我们要尾插#xff0c;需要遍历一遍然后找到它的尾#xff0c;这样时间复炸度就为O(N),现在我们引入双向带头链表就很方便了#xff0c;我们先看看它的结构。通过观察#xff0c;我们发现一…在前面我们学习了单链表发现单链表还是有一些不够方便比如我们要尾插需要遍历一遍然后找到它的尾这样时间复炸度就为O(N),现在我们引入双向带头链表就很方便了我们先看看它的结构。通过观察我们发现一个结构体里面我们存两个指针一个指向前面的一个指向后面的这样就是双向了头指针指向尾我们找尾只需要通过头指针找很方便我们找一个指针节点上一个也很便利如果是单链表我们还需要从头开始找。所以是带头双向循环链表真的很方便。我们先创建一个结构体接下来就是对它初始化了。因为我们我们是带头的这个哨兵位的头需要在初始化的时候创建后面我们插入数据也需要创建节点所以我们就将创建节点的过程写成一个函数。我们利用一个函数创建节点初始化时结构体里面的指针指向自己带头双向循环链表也和单链表一样有头插尾插头删尾删在某个位置前插入删除。我们先来看看插入的操作头插头插我们只需要改连接关系就好。首先我们创捷一个节点。然后在哨兵的后面插入节点改变连接关系就可以完成连接。尾插的插又怎么实现呢在之前的单链表我们还需要找尾然后在尾的后面插入改连接关系我们的带头双向循环链表的便利之处在于我们可以快速的找到尾我们哨兵位的prev就是链表的尾。在某个位置前面插入我们应该怎么做在单链表我们需要找到pos位置前面的地址我们要从头开始找。带头双向循环链表的便利在于我们的pos的prev就是我们要找的地址。简单的修改连接关系就能完成我们的插入。写着写着我们发现我们在某个位置插入元素好像和头插尾插有相似的地址。头插就是在哨兵位后一个节点的前面插入我们也可以利用在某处插入元素的函数这样大大节省书写时间。尾插就是在哨兵位的前面插入这个更加简单。所以我们的头插尾插可以复用我们在某处插入的函数。插入讲完了下面我们来说说删除。尾删是怎么操作的在单链表我们需要找到尾同时记录尾的前一个我们将尾释放将尾前一个的next置尾空指针.头删的操作。我们带头双向循环链表有一个哨兵位所以我们需要绕开它然后删除它后面的第一个节点然后修改连接关系。我们删除前需要判断链表是否为空。我们发现删除好像都需要判断是否为空我们前面的尾删也需要所以我们需要在尾删的地方加上判断。如何删除某个节点的我们需要配合一个查找函数来查找节点。我们发现删除某个节点位置的函数也可以与头删尾删复用。尾删我们传哨兵位的prev头删我们传哨兵位的next
