| | |
Name two advantages of using linked lists over arrays to store data.
dynamic sizing; very fast insertions and removals
Name two advantages of using arrays over linked lists to store data.
No additional overhead in terms of memory (for node references) is needed. Also, arrays easily support binary searches while a linked list doesn't.
Write a minimal private inner class called Node that can be used to build a linked list of strings.
private class Node {
String string;
Node next;
}
Describe two errors in the following code, whose insertSecond() method is intended to insert a new item as the second item of the linked list in question.
public class LinkedListH<Item> {
private class Element {
Item item;
Element next;
}
private Element first;
private int size = 0;
public void insertSecond(Item item) {
Element second = new Element();
second.item = item;
first.next = second;
second.next = first.next.next;
size++;
}
⋮
}
After the statement first.next = second; the local variable second has a null reference for its next instance variable. This breaks the list, "dropping" (and thus permanently losing) any existing 3rd, 4th, 5th, etc. elements.
Additionally, the case of an empty list is not addressed.
Consider the program below and then answer the questions posed:
class Node {
public int iData; // data item (key)
public Node next; // next node in list
public Node(int id){ // constructor
iData = id;
}
}
class LinkList {
private Node first; // reference to first node on list
public LinkList() { // constructor
first = null;
}
public Node find(int key) { // find the node with a given key
Node current = first; // start at the first node
while (current != null && current.iData != key)
current = current.next; // go to next node
return current;
}
public void displayList() { // display the list
for (Node current = first; current != null; current = current.next)
System.out.println(current.iData); // print data
}
public void insertFirst(int key) { // insert a node at the front of the list
// See question (a)...
}
public Node delete(int key) { // delete the node with a given key
// See question (b)...
}
}
class LinkListApp {
public static void main(String[] args) {
LinkList theList = new LinkList(); // create a list
theList.insertFirst(22);
theList.insertFirst(44);
theList.insertFirst(66);
Node d = theList.delete(44);
d = theList.delete(88);
theList.displayList(); // display list
} // end main()
}
Implement the insertFirst method that inserts a new node with the given data key at the front of the linked list. Assume the list is not empty.
Implement the delete method that deletes a node with the given data key from the related LinkList object, and returns the Node containing the key. Assume the list is not empty. If the key does not exist in the list, null should be returned and no action should be taken.
Predict the printed results of the main method in LinkListApp
public void insertFirst(int key) { // insert a node at the front
Node node = new Node(key);
node.next = first;
first = node;
}
public Node delete(int key) { // delete the node with a given key
// if the list is empty, there is nothing to delete..
if (first == null)
return null;
Node node = first;
// if the key was found on the 1st node, reset "first"..
if (node.iData == key) {
first = node.next;
return node;
}
// traverse the list to find parent of node with the given key..
while (node.next != null && node.next.iData != key) {
node = node.next;
}
if (node.next == null) { // then key wasn't present
return null;
}
else { // re-route references to skip over node to be deleted..
Node deletedNode = node.next;
node.next = node.next.next;
return deletedNode;
}
}
66 22
The following class is meant to describe a circular linked list (where the "next" element referenced by the last node in the list is the first element in the list). This class should keep only one instance variable, which is a reference to the first node of the list. What code should be added to the body of the method addFirst() below so that this method adds a new node containing the given item between the first and last nodes of the list.
public class CircularLinkedList- { private class Node { Item item; Node next; } private Node first; public boolean isEmpty() { return (first == null); } public void addFirst(Item item) { ////////////////////////// // WHAT CODE GOES HERE? // ////////////////////////// }
Answers vary, but the following code will do it:
Node newNode = new Node();
newNode.item = item;
if (this.isEmpty()) {
first = newNode;
first.next = first;
}
else if (first.next == first) {
newNode.next = first;
first.next = newNode;
first = newNode;
}
else {
Node n = first;
while (n.next != first) {
n = n.next;
}
n.next = newNode;
newNode.next = first;
first = newNode;
}
A doubly circular linked list is a list where each node points to its successor and its predecessor in a circular manner. The head variable points to the first node in the list. An empty list is represented by a null value in head. The prev value of the first list node points to the last node (i.e., the "tail") and the next value of the last node in the list points to the first node. The structure of a node and an (incomplete) list class are given by the following class definitions.
public class Node {
public int value;
Node next; // "next" points to the successor
Node prev; // "prev" points to the predecessor
}
public class List {
public Node head; // head must point to first node in list
public List() { // Constructor
head = null; // Empty list
}
//... other methods ...
}
Write a Java method for the List class that inserts a Node object x at the head of the doubly circular list:
public void insertAtHead(Node x) {
// write the code that should go here...
}
Write a Java method for the List class that inserts an Node object x at the tail of the doubly circular list:
public void insertAtTail(Node x) {
// write the code that should go here...
}Write a Java method for the List class that deletes the Node object at the tail of the doubly circular list:
public void deleteAtTail() {
// write the code that should go here...
}
public void insertAtHead(Node x) {
if (head == null) { // no nodes in circular list
head = x;
head.next = head;
head.prev = head;
}
else { // one or more nodes in list
head.prev.next = x;
x.prev = head.prev;
x.next = head;
head.prev = x;
head = x;
}
}
public void insertAtTail(Node x) {
insertAtHead(x);
head = head.next;
}
public void deleteAtTail() {
if (head == null) { // no nodes in circular list
; //do nothing (optionally throw exception)
}
else if (head.next == head) { // one node in list
head = null;
}
else {
Node newTail = head.prev.prev;
newTail.next = head;
head.prev = newTail;
}
}
Complete the class SortedList.java by providing a body to the insertInOrder(Item item) method so that it inserts items into the list in such a way that the list is always "in order" from least to greatest in a manner consistent with Item's implementation of the Comparable interface.
The given main() method uses this method to insert 10 randomly generated numbers into an initially empty SortedList object, and then prints the list from head to tail, as the sample run below suggests.
$ java SortedList↵
7->79->81->82->90->107->116->122->146->165->
Complete the class ReversableList.java by providing a body to the reverse() method so that it reverses the current list.
Importantly, no new nodes should be constructed in the implementation of the reverse() method.
The given main() method prompts the user for a length $n \ge 0$ of a list to reverse, fills a list with integers from 1 to $n$, prints it, reverses it with the reverse() method, and prints the result -- as seen in the sample runs below.
$ java ReversableList↵ Length of list to reverse? 7↵ list : 1->2->3->4->5->6->7-> reversed list : 7->6->5->4->3->2->1->
$ java ReversableList↵ Length of list to reverse? 2↵ list : 1->2-> reversed list : 2->1->
Complete the class DealableList.java by providing a body to the deal() method so that it returns a stack of two DealableList objects, consisting of the odd-positioned and even-positioned elements of the original list, respectively. The original list should be empty at the conclusion of the method.
Importantly, no new nodes should be constructed in the implementation of the deal() method.
A sample run is shown. As you test your code, modify the for-loop in the main method to make sure appropriate output is also displayed when there is an even number of elements in the list at the time deal() is called.
$ java DealableList↵
0->1->2->3->4->5->6->7->8->9->10->11->
1->3->5->7->9->11->
0->2->4->6->8->10->
Complete the class ZippableList.java by providing a body to the zipTogetherWith(ZippableList method so that the nodes of the list passed as a parameter are inserted as every other node of the current list (i.e., first node of first list, first node of second list, second node of first list, second node of second list, ...)
Any extra elements in either the current list, or the list passed as a parameter, should be added to the end of new list, in their original order. Also, no elements should remain in the list passed as a parameter at the conclusion of the method.
Importantly, no new nodes should be constructed in the implementation of the zipTogetherWith() method.
The main() method provided allows one to test the zipTogetherWith() method on different sized lists, as shown in the sample runs below.
$ java ZippableList↵ Lengths of two lists to be zipped together (separated by a space)? 5 8↵ this list : 0->2->4->6->8-> that list : 1->3->5->7->9->11->13->15-> after zipping that list into this list... this list : 0->1->2->3->4->5->6->7->8->9->11->13->15-> that list :
$ java ZippableList↵ Lengths of two lists to be zipped together (separated by a space)? 9 4↵ this list : 0->2->4->6->8->10->12->14->16-> that list : 1->3->5->7-> after zipping that list into this list... this list : 0->1->2->3->4->5->6->7->8->10->12->14->16-> that list :
$ java ZippableList↵ Lengths of two lists to be zipped together (separated by a space)? 0 3↵ this list : that list : 1->3->5-> after zipping that list into this list... this list : 1->3->5-> that list :
$ java ZippableList↵ Lengths of two lists to be zipped together (separated by a space)? 5 0↵ this list : 0->2->4->6->8-> that list : after zipping that list into this list... this list : 0->2->4->6->8-> that list :
Complete the class RandomList whose objects are linked lists of random integer values and which has the following methods:
removeAdjacentDuplicates() and removeAdjacentDuplicatesR() which both reduce any sublists of two or more adjacent nodes with identical values present upon the list's construction, down to a single node with that common value. However, removeAdjacentDuplicates() should do this iteratively, while removeAdjacentDuplicatesR() should do this recursively (and in a way that hides the Node class from the client).
getMax() which returns the maximum integer value stored in the list
removeMaxValues() which, after identifying the maximum value in the list, removes all nodes containing that maximum value.
The constructor for this class takes two arguments, bound and size, and should create a list of size nodes whose values are randomly chosen from the integers 0,1,2,3,...,(bound-1).
Add code to the given class only where indicated to accomplish the desired behavior (as suggested by the sample runs that follow. Do not add any additional instance variables. You may add only one private instance method.
Importantly, if size == n for a given list -- both the construction of that list and all the methods described above should have $O(n)$ time complexity.
$ java RandomList↵
Random list:
3->2->1->0->0->3->0->1->1->0->3->1->2->3->0->
List with adjacent duplicates removed:
3->2->1->0->3->0->1->0->3->1->2->3->0->
Another Random list:
0->1->3->0->0->1->0->2->0->2->1->0->3->2->1->
List with adjacent duplicates removed recursively:
0->1->3->0->1->0->2->0->2->1->0->3->2->1->
A Third Random list:
1->3->2->1->1->0->1->2->3->2->1->1->3->2->3->
Successively removing max values:
1->2->1->1->0->1->2->2->1->1->2->
1->1->1->0->1->1->1->
0->
$ java RandomList↵
Random list:
1->3->1->3->2->0->3->2->1->2->2->2->3->1->0->
List with adjacent duplicates removed:
1->3->1->3->2->0->3->2->1->2->3->1->0->
Another Random list:
2->1->0->3->3->1->0->0->0->0->0->1->3->2->3->
List with adjacent duplicates removed recursively:
2->1->0->3->1->0->1->3->2->3->
A Third Random list:
0->0->1->2->3->0->0->2->2->0->3->0->3->2->0->
Successively removing max values:
0->0->1->2->0->0->2->2->0->0->2->0->
0->0->1->0->0->0->0->0->
0->0->0->0->0->0->0->
Add a method itemInTheMiddle()to the RandomList class above that returns the item associated with the middle node of the list, but does so in a single traversal of the list and without knowing the size of the list ahead of time. In the case of a list with $2k$ items for some integer $k$, return the $(k+1)^{th}$ item.
As a slightly cryptic hint: If a tortoise and a hare run a race and the hare runs twice as fast as the tortoise, where is the tortoise when the hare wins?
Let a "list with a loop" be a data structure similar to a linked list, except what would have been the tail of the list now references some earlier node (or possibly itself).
Complete the class ListWithLoopDetection by providing bodies to the methods described below, so that objects of this class -- which may be assumed to either represent a linked list or a "list with a loop" -- can detect if they have a loop.
addItem(Item item): returns nothing, but adds an item to the list -- this operation should take $O(1)$ time.
insertLoopToPosition(int pos): returns nothing, but makes the tail node in the list reference the node at position pos in the list (note, position $0$ is the head of the list). This operation should take $O(n)$ time.
loopExists() returns true if and only if the list contains a loop (i.e., the next reference of the last unique node of the list references an item earlier in the list.)
Restrictions:
The main() method may not be altered.
You may add exactly one instance variable and exactly one instance method, beyond those mentioned above and those included in the provided code, to the outer class.
As the main() method suggests, the class should support a generic type parameter to allow list objects of this class to store objects of a specified type.
Your code may not make any assumptions about the number of elements in the list inside the loopExists() method. This is explained in more detail in one of the comments in the main() method.
Two sample runs are shown below:
$ java ListWithLoopDetection↵
8 7 6 5 4 3 2 1 0
No Loop Exists
$ java ListWithLoopDetection↵
9 8 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 ...
Loop Exists
As an extra challenge, add a method deleteItem(Item item) that deletes all nodes of the list storing that item. This action should preserve the order of the remaining nodes -- although if an item deleted is at the "junction point" forming a loop, the loop should be broken.
Complete the class Set.java by providing code in areas indicated in that file. Do not change any code outside of these areas. When complete, this Set class should support the construction of (mathematical) set of objects of any class that implements the Comparable interface, along with methods union(), intersection(), and difference(), which each output a new Set object where:
thisSet.union(thatSet) is the set of all items that occur in either thisSet, thatSet, or both.
thisSet.intersection(thatSet) is the set of all items that occur in both thisSet and thatSet.
thisSet.difference(thatSet) is the set of all items that occur in thisSet, but not thatSet.
Restrictions:
The implementation should be appropriately hidden from "the client" but should use a linked-list of nodes, whose (comparable) contents are in order from least to greatest, starting at the head.
union(), intersection(), and difference() should all employ recursion to accomplish their tasks, and must not use any arrays in that process. (The only allowed usage of an array in this class is in the uniqueLettersIn() and setOfUniqueCharsFromString() methods, which have already been provided.)
union(), intersection(), and difference() should leave unchanged the sets on which they operate (e.g., thisSet and thatSet above).
union(), intersection(), and difference() should each run with time complexity $O(n)$, making only one traversal of the linked lists involved each!
The main() method provided in the given code tests the Set class with two quick sets created from the unique characters in two strings: "the quick brown fox jumps" and "over the lazy dog". Feel free to test your completed methods with different strings -- but the output using the strings given should agree with the following sample run:
$ java Set↵
set1: {b,c,e,f,h,i,j,k,m,n,o,p,q,r,s,t,u,w,x}
set2: {a,d,e,g,h,l,o,r,t,v,y,z}
set1 intersect set2:
{e,h,o,r,t}
set1 union set2:
{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}
set1 difference set2:
{b,c,f,i,j,k,m,n,p,q,s,u,w,x}
An unrolled linked list is a variation on a linked list which stores multiple elements in each node. One version of this data structure uses an array within each node towards this end. This can dramatically increase cache performance (when the array size is related to the cache size by some integer multiplier), while simultaneously decreasing memory overhead associated with storing references.
The partially completed class UnrolledDoublyLinkedList suggests one implementation of an unrolled linked list. The exact process followed in adding and removing items from an unrolled linked list can vary quite a lot from one implementation to another -- but often, when a node's array fills, it splits into two, with half of the items going to one node and half going to the other. Removal is often similar, with node arrays merging when they are small enough. By doing this, we keep all of the arrays "mostly full" and thus don't waste memory.
The particulars of how adding and removing items from the collection for this particular problem are given in the comments shown in the code given above. Complete the given class, using the implementation described, and adding code only in the indicated places.
The following provides a sample run corresponding to the main() method of the given class, which tests the class. In this method, several values (the ones preceded by a "+") are first added to the collection of integers stored by one of UnrolledDoublyLinkedList objects, showing the state of the list after each addition. Then, upon iterating through the collection, each stored integer is printed. Finally, all of the values added are removed -- but in a different order (see the values preceded by a "-") and with the attempted removal of some integers that were never even in the collection (no removal happens in this situation, of course). Again, the state of the list is shown after each attempted removal.
Use the following sample run to check things -- your code should produce identical results.
$ java UnrolledDoublyLinkedList↵
+ 3 : H->[3]->
+ 7 : H->[3,7]->
+ 0 : H->[0,3,7]->
+ 11 : H->[0,3,7,11]->
+ 13 : H->[0,3]->[7,11,13]->
+ 2 : H->[0,2,3]->[7,11,13]->
+ 1 : H->[0,1,2,3]->[7,11,13]->
+ 9 : H->[0,1]->[2,3,9]->[7,11,13]->
+ 10 : H->[0,1,10]->[2,3,9]->[7,11,13]->
+ 8 : H->[0,1,8,10]->[2,3,9]->[7,11,13]->
+ 4 : H->[0,1]->[4,8,10]->[2,3,9]->[7,11,13]->
+ 5 : H->[0,1,5]->[4,8,10]->[2,3,9]->[7,11,13]->
+ 6 : H->[0,1,5,6]->[4,8,10]->[2,3,9]->[7,11,13]->
0 1 5 6 4 8 10 2 3 9 7 11 13
- 1 : H->[0,5,6]->[4,8,10]->[2,3,9]->[7,11,13]->
- 8 : H->[0,5,6]->[4,9,10]->[2,3]->[7,11,13]->
- 13 : H->[0,5,6]->[4,9,10]->[2,3]->[7,11]->
- 11 : H->[0,5,6]->[4,9,10]->[2,3]->[7]->
- 7 : H->[0,5,6]->[4,9,10]->[2,3]->
- 15 : H->[0,5,6]->[4,9,10]->[2,3]->
- 6 : H->[0,5,10]->[4,9]->[2,3]->
- 5 : H->[0,4,9,10]->[2,3]->
- 4 : H->[0,9,10]->[2,3]->
- 9 : H->[0,2,3,10]->
- 12 : H->[0,2,3,10]->
- 3 : H->[0,2,10]->
- 2 : H->[0,10]->
- 0 : H->[10]->
- 20 : H->[10]->
- 10 : H->
- 14 : H->