| | |
Name two advantages of using linked lists over arrays to store data.
dynamic sizing; very fast insertions and removals
Name an advantage of using arrays over linked lists to store data.
No additional overhead in terms of memory (for node references) is needed.
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
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.