双向链表是指每个节点都包含两个指针分别指向其前驱和后继的链表，双向链表在遍历时更灵活，可以向前或向后遍历，在查找元素时也可以使用二分查找来提高效率。javaSE中的LinkedList就是一个双向链表，今天先不考虑javaSE中的实现，以自己的想法写一个双向链表并测试其可用性。
首先定义节点类，它应该包含一个数据域和两个指针域，如图：
节点结构
然后来考虑节点的操作，双向链表中无论添加还是删除节点，都会影响相邻两个节点的相邻指针指向，而这一对相邻指针指向的改变具有原子性，也就是说，应该将这一对行为封装成方法而不是每次都手动给他们赋值，这样可以避免逻辑混乱。这个方法还要考虑到双向链表本身具有的头尾指针，如果增删的位置在头尾就要对头尾指针进行修改。
原子方法：插入到特定节点之后
原子方法：插入到特定节点之前
原子方法：剔除特定节点
关于原子方法，本来我的想法是写在节点类里的，毕竟面向对象嘛，但是后来考虑如果这样设计，节点类就会占用更多空间，链表中肯定会有大量节点，所以这样并不合理。
接下来就是对外公布的方法：
公开方法
接下来编写测试类，我采取的方法是同时操作自己写的LinkedList和jdk中的标准LinkedList，之后对比它们的元素是否相同。代码如下：
测试类
测试结果
换了几组不同的操作来测试，均通过（此处省略一万次翻车经历。。。。）我需要一个暴漫表情来回血。这东西在写之前我觉得思路清晰运筹帷幄，然而事实却是测试驱动不断debug。。。看来思维严密性还有待提高。
网友评论