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 of Figure 4.8 to implement circular singly linked lists.

(b) Modify the code of Figure 4.14 to implement circular doubly linked lists.

Transcribed Image Text:

// Linked list implementation class LList implements List { private Link head; private Link tail; protected Link curr; int cnt; //Constructors // Constructor LList (int size) { this(); } LList() { Ignore size curr = tail = head = new Link (null); // Create header cnt = 0; } public void clear() { // Remove all elements // Drop access to links head.setNext (null); curr = tail = head = new Link (null); // Create header cnt = 0; } } // Insert "it" at current position public void insert (E it) { curr.setNext (new Link (it, curr.next())); if (tail == curr) tail = curr.next(); // New tail cnt++; // Pointer to list header // Pointer to last element // Access to current element // Size of list } public void append (E it) { // Append "it" to list tail = tail.setNext (new Link (it, null)); cnt++; public void moveToStart() {curr = head; } } -- // Remove and return current element public E remove () { if (curr.next() == null) return null; E it = curr.next().element (); if (tail == curr.next()) tail = curr; curr.setNext (curr.next() .next()); cnt--; return it; // Set curr at list start // Nothing to remove // Remember value // Removed last // Remove from list // Decrement count. // Return value Figure 4.8 A linked list implementation.