一.双向链表的原理
双向链表顾名思义,就是两个方向都可以,像我们的单链表,只能从前往后,而不能从后往前.
这样在我们插入和删除数据的时候,我们就不用去找到要操作节点的上一个节点,只需要找到要操作的节点,直接往前访问就可以了.
二.双向链表的结构
很明显我们需要知道前一个位置是什么,所以我们需要两个指针域.
一个指向上一个节点的指针域,一个指向下一个节点的指针域.
三.双向链表的初始化
画个图你们就知道怎么初始化了:
两个指针都设置为空.
四.双向链表增加元素
1.前插法
跟单链表差不多,但是我们需要增加一个对上一个指针的操作
如果是只有一个头节点,然后插入节点时,新节点的下一个指针就是头节点的下一个指针,也可以是空因为头节点的下一个位置就是空.
然后新节点的上一个位置就是头节点,头节点的下一个位置就是新节点.
如果有其他的节点,那么多了一步就是新插入节点的下一个位置的上一个位置是新节点,也就是L->next->prev = node;
2.尾插法
当然还是需要我们进行遍历到尾节点,跟单链表差不多.
只需要将新插入的节点的下一个位置设为空,上一个位置是刚刚的遍历到的尾节点,然后刚刚的尾结点的下一个位置就是新插入的节点.
3.任意位置插入
任意位置插入,现在我们就不需要再去找前一个节点了,直接找到我们要插入的位置通过前一个指针,就可以找到前一个节点了,然后进行插入操作.
插入操作的解释如下(注意顺序):
要插入节点的上一个位置的下一个位置为新插入的节点
新插入节点的下一个位置是找到插入位置的节点.
新插入节点的上一个位置是插入位置节点的上一个节点
插入位置的节点的上一个节点是新插入的节点.
五.双向链表的遍历
其实是跟单链表是一样的,不过我们居然可以指向前一个位置,那么我们还可以逆向打印.
两个遍历的条件都是p的指针域而不是p本身.
正向打印的时候,需要打印尾结点所以是p->next->data
逆向打印的时候,不需要打印头节点,所以是p->data
六.双向链表删除元素
跟插入一样,现在就不需要遍历找到要删除的前一个节点的位置,只需要找到要删除的位置即可.
所以删除的操作有两种情况,如果要删除位置的下一个为空就是第二种情况,只需要p->prev->next=p->next
如果不是最后一个节点的话,还需要p->next->prev=p->prev
像双向链表的销毁和获取元素等都和单链表一样就不展开了.
七.总结
双向链表比单链表多了一个指向前一个位置的指针,方便了我们进行查找,对插入和删除的时候,我们可以将目标放在我们想要的上面.
需要注意插入和删除的操作,多了一个前面指针的赋值.
