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 for elements, but no concept of an absolute first or last position.
(a) Modify the code to implement circular singly linked lists.
// Linked list implementation
template <typename E> class LList: public List<E> {
private:
Link<E>* head; // Pointer to list header
Link<E>* tail; // Pointer to last element
Link<E>* curr; // Access to current element
int cnt; // Size of list
void init() { // Intialization helper method
curr = tail = head = new Link<E>;
cnt = 0;} void removeall() { // Return link nodes to free store
while(head != NULL) {
curr = head;
head = head->next;
delete curr;}}
public:
LList(int size=defaultSize) { init(); } // Constructor
˜LList() { removeall(); } // Destructor
void print() const; // Print list contents
void clear() { removeall(); init(); } // Clear list
// Insert "it" at current position
void insert(const E& it) {
curr->next = new Link<E>(it, curr->next);
if (tail == curr) tail = curr->next; // New tail
cnt++;}
void append(const E& it) { // Append "it" to list
tail = tail->next = new Link<E>(it, NULL);
cnt++;}
// Remove and return current element
E remove() {
Assert(curr->next != NULL, "No element");
E it = curr->next->element; // Remember value
ink<E>* ltemp = curr->next; // Remember link node
if (tail == curr->next) tail = curr; // Reset tail
curr->next = curr->next->next; // Remove from list
delete ltemp; // Reclaim space
cnt--; // Decrement the count
return it;}
To modify the code to implement a circular singly linked list, you need to make the following changes:
1. Update the `init()` method:
- Set the `tail` pointer to `NULL` instead of creating a new node with `head` pointing to it.
2. Update the `insert()` method:
- Create a new node with the given element and set its `next` pointer to `curr->next`.
- If `tail` is equal to `curr`, then update `tail` to point to the newly inserted node.
- Update `curr->next` to point to the newly inserted node.
3. Update the `append()` method:
- Create a new node with the given element and set its `next` pointer to `NULL`.
- Set `tail->next` to the newly created node.
- Update `tail` to point to the newly appended node.
4. Update the `remove()` method:
- Before removing the current element, check if `curr->next` is `NULL`. If it is, then there are no elements in the list, so throw an exception or handle the error accordingly.
- Store the value of the element to be removed in a variable.
- Store the address of the link node to be removed in a temporary pointer.
- If `tail` is pointing to `curr->next`, update `tail` to `curr`.
- Update `curr->next` to skip the link node to be removed.
- Delete the link node using the temporary pointer.
- Decrement the count.
- Return the stored element.
Note that a circular singly linked list does not have a concept of a "last element" because the last element's `next` pointer points back to the first element. Therefore, the `tail` pointer is not necessary for the circularity of the list, but it can still be used for efficiency purposes, such as appending elements in constant time.