Exercise 4.6
A circular linked list is one in which the next field for the last link node of the list
points to the first link node of the list. This can be useful when you wish to have a
relative positioning of the elements, but no concept of an absolute first or last
position.
(a) Modify the code of a singly linked list to implement a circular singly linked
list.
(b) Modify the code of a doubly linked list to implement a circular doubly linked
list.
Solution (4.6a)
=========
The following members are modified:
template <class Elem>
void LList<Elem>::LList(const int sz) {
head = tail = curr = new link; // Create header
head->next = head;
}
template <class Elem>
void LList<Elem>::clear() { // Remove Elems
while (head->next != NULL) { // Return to free
curr = head->next; // (keep header)
head->next = curr->next;
delete curr;
}
tail = curr = head->next = head; // Reinitialize
}
// Insert Elem at current position
template <class Elem>
void LList<Elem>::insert(const Elem& item) {
assert(curr != NULL); // Must be pointing to Elem
curr->next = new link(item, curr->next);
if (tail->next != head) tail = tail->next;
}
template <class Elem> // Put at tail
void LList<Elem>::append(const Elem& item){
tail = tail->next = new link(item, head);
}
评论0