【数据结构】链表的模拟实现(双向链表)

学习是一个循序渐进的过程,在模拟实现完单向链表后,接下来实现双向链表,且双向链表就是我们使用Java库里面的链表时候的底层的样子,所以现在来模拟实现一遍。

其实在实现完单向链表之后,双向链表就已经很简单了,具体实现思路我们不过多阐述,代码里面有注释,但会在需要注意的地方进行表述和解释。

双向链表图解:

【数据结构】链表的模拟实现(双向链表)_第1张图片

 主要需要实现功能:


1:实现双向链表头插。

2:实现双向链表尾插。

3:实现双向链表全部元素打印。

4:实现得到双向链表元素个数。

5:实现双向链表某个位置插入元素。

6:实现双向链表某个位置删除元素。

7:实现双向链表删除根据传入某个需要删除的元素。

8:实现双向链表判断是否包含某个元素。


 

在实现功能之前,双向链表定义是跟单向链表定义差不多的,主要不同点在于多了一个成员是前驱prev用于记录结点前一个元素:
【数据结构】链表的模拟实现(双向链表)_第2张图片
 

1)实现双向链表头插:

【数据结构】链表的模拟实现(双向链表)_第3张图片

 2)实现双向链表尾插:

【数据结构】链表的模拟实现(双向链表)_第4张图片

 3)实现双向链表所有元素打印:

【数据结构】链表的模拟实现(双向链表)_第5张图片

 4)实现得到双向链表元素个数:

因为在每一个添加和删除的方法里面都有size加减,故直接调用对象的size就可以得到元素个数。



5)实现双向链表某个位置插入元素:

【数据结构】链表的模拟实现(双向链表)_第6张图片



 

6)实现双向链表某个位置删除元素:
 

【数据结构】链表的模拟实现(双向链表)_第7张图片

7) 实现双向链表删除根据传入某个需要删除的元素

【数据结构】链表的模拟实现(双向链表)_第8张图片

 

8) 实现双向链表判断是否包含某个元素:

【数据结构】链表的模拟实现(双向链表)_第9张图片

测试样例:
1:头插元素:

【数据结构】链表的模拟实现(双向链表)_第10张图片

 2:尾插元素:

【数据结构】链表的模拟实现(双向链表)_第11张图片

 

 3:在某位置插入结点:
【数据结构】链表的模拟实现(双向链表)_第12张图片

 4:删除某个节点元素:

【数据结构】链表的模拟实现(双向链表)_第13张图片

3.1:测试异常情况:

【数据结构】链表的模拟实现(双向链表)_第14张图片

【数据结构】链表的模拟实现(双向链表)_第15张图片

 4:测试是否包含某个元素结点:

【数据结构】链表的模拟实现(双向链表)_第16张图片

 

5:删除某个元素:

【数据结构】链表的模拟实现(双向链表)_第17张图片

 

 

你可能感兴趣的