实现循环双链表类的以下成员方法,题意和算法描述见《习题解 答》图2-9。 //在this循环双链表之后,合并连接 list 中所有结点,并设置list为空 public void concat(CirDoublyList I ist)
时间: 2024-09-27 16:05:22 浏览: 36
在实现循环双链表的`concat`方法时,我们需要将`Ist`(传入的循环双链表)中的所有节点添加到当前列表的尾部,然后更新`Ist`的头指针使其指向最后一个元素,最后将`Ist`的列表置空。这里是一个简单的步骤描述:
1. 获取`Ist`的头结点`head`。
2. 如果`Ist`为空(即`head`为null),直接返回,因为没有内容需要添加。
3. 使用三个指针,一个指向当前列表的尾部(`currentTail`),一个指向`Ist`的头结点(`newHead`),并初始化第三个指针`temp`用于临时存储。
4. 遍历`Ist`,每次迭代:
- 将`temp`设为`newHead`,并将`newHead`指向下一个节点。
- 如果`newHead`不为null,则将其添加到当前列表的尾部(通过将`currentTail.next`设置为`newHead`,同时`newHead.prev`设置为`currentTail`)。
5. 当`newHead`变为null(遍历完`Ist`)时,`currentTail.next`应该已经指向了`Ist`原来的尾部,因此更新`currentTail.next`的`prev`指针为`currentTail`,使其成为真正的尾节点。
6. 更新当前列表的头指针为`currentTail`,因为现在它已经是新的链表首节点。
7. 最后,将`Ist`的头指针`head`置为null,表示`Ist`的列表已空。
```java
public void concat(CirDoublyList<I> Ist) {
Node<T> head = Ist.head;
if (head == null) return;
Node<T> currentTail = this.tail;
Node<T> newHead = head;
Node<T> temp = newHead;
while (newHead != null) {
temp = newHead;
newHead = newHead.next;
if (newHead != null) {
// 添加新节点到当前尾部
temp.next = newHead;
newHead.prev = temp;
currentTail.next = newHead;
}
currentTail = temp;
}
// 更新列表尾部的next指针
currentTail.next.prev = currentTail;
this.head = currentTail; // 新的头节点
Ist.head = null; // 清空输入列表
}
```
阅读全文