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

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

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

主要需要实现功能:

1:实现双向链表头插。

2:实现双向链表尾插。

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

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

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

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

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

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

在实现功能之前,双向链表定义是跟单向链表定义差不多的,主要不同点在于多了一个成员是前驱prev用于记录结点前一个元素且多了一个尾结点,用于记录尾部元素,便于后面尾插以及很多操作:

1)实现双向链表头插:

2)实现双向链表尾插:

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

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

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

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

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

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

8)实现双向链表删除根据传入某个需要删除的元素(删除重复出现的所有元素)

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

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

2:尾插元素:

3:在某位置插入结点:

4:删除某个节点元素:

3.1:测试异常情况:

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

5:删除某个元素:

6:删除重复的元素:

经验分享 程序员 微信小程序 职场和发展