Question 1.
L.next.data = "cat";
Question 2.
L.next = new Listnode("rat", L.next);
The list begins:
and after the code looks like:
and this is correct.
operation |
linked list |
array |
remove first |
O(1) |
O(N) |
remove last |
O(N) |
O(1) |
For linked list: To remove the first node you only have to do L = L.next so this is O(1). To remove the last node you must traverse the list from the first node to get to the next to last node to do the delete so this is O(N).
For arrays: To remove the first item you must shift all the remaining items one array location to the left to fill in the hole so this is O(N). To remove the last item there are no shifts because no items are to the right so this is O(1).
// Note: this code has excessive comments to help you understand it in detail. // returns true if val is in circular linked list L; otherwise returns false if (L == null) return false; // no items on list so not found if (L.data.equals(val)) return true; // val is in first node on list Listnode tmp = L.next; while (tmp != L) { // stops from going past first node and going in circles if (tmp.data.equals(val)) return true; // found val at this node tmp = tmp.next; } return false; // did not find val in list