实现双向链表:创建、插入与删除操作

需积分: 15 1 下载量 46 浏览量 更新于2024-09-14 收藏 5KB TXT 举报
"双向链表是一种特殊的链表结构,它包含指向前后节点的指针,使得在链表中的导航更为灵活。本资源介绍了如何创建一个双向链表,并提供了相关的节点类(IntNode)和双向链表类(IntSLList)的实现。在IntNode类中,定义了节点的数据域(myNodeData)、前驱节点引用(prior)和后继节点引用(next)。IntSLList类中包含了初始化链表、判断链表是否为空、在头部添加节点、在尾部添加节点以及从头部删除节点的方法。" 在双向链表中,每个节点除了存储数据外,还包含两个指针,一个用于指向其前一个节点,另一个用于指向其后一个节点。这使得双向链表可以从前向后或者从后向前遍历,相比单链表提供了更丰富的操作可能性。 `IntNode` 类是双向链表的基本组成单元,包含以下方法: 1. 构造函数:有三种构造方式,一种不带参数,用于创建空节点;一种带有数据,用于创建含有数据的新节点,前驱和后继节点默认为null;另一种带有数据和前后节点引用,用于在已有链表中插入节点。 `IntSLList` 类是双向链表的实现,关键成员变量包括头节点(head)和尾节点(tail),以及以下方法: 1. 初始化构造函数:创建一个空的双向链表,头节点和尾节点都为null。 2. `isEmpty` 方法:检查链表是否为空,如果头节点为null,则链表为空。 3. `addToHead` 方法:在链表头部添加新节点,如果链表为空,新建的节点既是头节点也是尾节点。否则,新节点会成为新的头节点,原头节点成为新节点的后继节点。 4. `addToTail` 方法:在链表尾部添加新节点,如果链表为空,新建的节点既是头节点也是尾节点。否则,新节点会插入到尾节点之后,成为新的尾节点。 5. `deleteFromHead` 方法:从链表头部删除节点。如果链表只有一个节点,同时删除头节点和尾节点,返回-1表示链表为空。否则,将头节点更新为其后继节点,保持链表连接。 通过这些基本操作,我们可以构建、修改和操作双向链表。这种数据结构在很多场景下非常有用,例如在需要频繁进行插入和删除操作的列表中,或者在需要支持反向遍历的情况。