双向链表遍历以及增删改查操作(思路分析)
遍历:
我们的双向链表的遍历和单链表的遍历操作都是一样的
- 不同的是我们的双向链表结点中不仅维护了一个next引用,还维护了一个pre引用,这个引用指向每个结点前一个结点,所以我们的双向链表不仅仅是可以向后遍历,还可以向前遍历
增加:(我们这里的增加操作是指添加到双向链表的最后)
- 我们要增加,那么就要先找到双向链表中的最后一个结点,我们用一个临时变量temp记录这个最后的结点
- 先让我们的temp的next指向新的结点: temp.next = newHeroNode; 然后让新的结点的pre指向temp : newHeroNode.pre = temp;
- 这里我们可以发现: 我们的单向链表就是使用一条线连接起来的,所以我们每次不管是增加还是删除都是通过一个一个结点加上对应的next属性来完成的, 而我们的双向链表是使用两条线连接起来的,所以我们在双向链表中的操作都是通过一个一个结点加上对应的next属性和pre属性来完成的
- 当我们初始化一个新的结点的时候我们新结点的next和pre属性都是默认值,都是null
修改:
我们对于双向链表的修改的思路也是和单向链表是一样的,我们只需要找到对应的结点,然后修改该结点的对应的数据域的值就可以了,我们在修改的操作中并不移动结点,所以我们并不需要修改指针域
删除:
我们的双向链表的删除的时候不用找到待删除结点的前一个节点,我们的双向链表是可以实现自我删除某个节点的,但是我们也可以找到待删除结点的上一个结点,通过待删除结点的上一个结点来删除待删除结点也是可以的,但是没有必要,我们通过自我删除的方式更容易理解
- 自我删除即使直接找到待删除结点,通过待删除结点来删除
- 那么具体如何删除?
- 我们先找到待删除结点temp,
- 之后让temp结点的前一个节点的next引用指向temp结点的下一个节点: temp.pre.next = temp.next;
- 我们其实可以发现: temp.pre其实就是待删除结点的前一个节点,所以我们说双向链表可以实现自我删除的原因其实就是我们可以通过待删除结点的pre引用直接找到我们的待删除结点的前一个节点
- 然后让待删除结点的后一个节点的pre引用指向temp结点的上一个结点: temp.next.pre = temp.pre;
- 我们使用temp的下一个节点的pre引用指向temp结点的时候要注意: 如果这个时候我们删除的结点不是最后一个节点那么就没有问题, 但是如果这个时候我们是删除最后一个节点,那么这个时候就会出现一个空指针异常,因为我们的temp已经是最后一个结点了,这个时候temp没有下一个节点,所以如果是删除最后一个结点,这个时候我们要注意:删除最后一个结点的时候我们只需要让待删除结点的上一个结点的next指向null即可(也就是指向待删除结点的next),
- 其实我们能想到: 如果我们的待插入节点是链表中的最后一个节点,那么我们的待删除结点就没有下一个节点,那么也就自然不用连后面的线(也就是不用执行 temp.next.pre = temp.pre)