1.*Given the following definition of a circular linked list (CLL) class:
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
public class Node {
public String data;
public Node next;
public Node(String data, Node next) {
this.data = data; this.next = next;
}
}
public class LinkedList {
private Node rear; // pointer to last
node of CLL 12. … 13. }
14.
The class keeps a circular linked list, with a rear pointer to the last node.Implement the following method in the LinkedList class, to delete the first occurrence of a given item from the linked list. The method returns true if the item is deleted, or false if the item is not found.
15. 16. 17. 18. 19.
public boolean delete(String target) {
/* COMPLETE THIS METHOD */
}
SOLUTION
public boolean delete(String target) {
20.
21. if (rear == null) { // list is empty
22.
23. }
24.
25. if (rear == rear.next) { // list has only one
node
26. if (target.equals(rear.data)) { // found,
delete, leaves empty list
27. rear = null;
return false;
28.
29.
30.
31.
32. }
33.
34.
35.
36.
37.
38.
39. 40. 41. 42. 43. 44. 45. 46. 47. 48.} 49.
return true;
} else { // not found
return false;
}
Node prev=rear, curr=rear.next; do{
if (target.equals(curr.data)) {
prev.next = curr.next;
if (curr == rear) { // if curr is last
node, prev becomes new last node
rear == prev;
}
return true;
}
// skip to next node
prev = curr;
curr = curr.next;
} while (prev != rear);
return false; // not found
50.* Implement a method in the circular linked list class of problem 1, to add a new item after a specified item. (If the new item happens to be added after the last, then it should become the new last item.) If the item does not exist in the list, the method should return false, otherwise true.
51. public boolean addAfter(String newItem, String
afterItem) {
52. /* COMPLETE THIS METHOD */ 53. }
54.
55.
SOLUTION
56. public boolean addAfter(String newItem,
String afterItem) {
57.
58.
59.
60.
61.
62.
63.
if (rear == null) { // empty
return false;
}
Node ptr=rear; do{
if (afterItem.equals(ptr.data)) {
Node temp = new
Node(newItem,ptr.next);
64. ptr.next = temp;
65. if (ptr == rear) { // new node
becomes last
66.
67. 68. 69. 70. 71. 72. 73. 74.
rear = temp; }
return true;
}
ptr = ptr.next;
} while (ptr != rear);
return false; // afterItem not in list
}
75.A doubly linked list (DLL) is a linked list with nodes that point both
forward and backward. Here’s an example:
<---> 7 <---> 1 76.
Here’s a DLL node definition:
3 <---> 5
77. public class DLLNode {
78. public String data;
79. public DLLNode prev, next;
80. public DLLNode(String data, DLLNode next,
DLLNode prev) {
81. this.data = data; this.next = next;
this.prev = prev;
82. }
83. }
84.
The next of the last node will be null, and the prev of the first node will be null.Implement a method to move a node (given a pointer to it) to the front of a DLL.
// moves target to front of DLL
85. public static DLLNode moveToFront(DLLNode
front, DLLNode target) {
86. /** COMPLETE THIS METHOD **/ 87. }
88.
SOLUTION
// moves target to front of DLL
89. public static DLLNode moveToFront(DLLNode
front, DLLNode target) {
90. if (target == null || front == null ||
target == front) {
91. return;
92. }
93. // delink the target from the list
94. target.prev.next = target.next;
95. // make sure there is something after
target before setting its prev
96. 97. 98. 99. 100. 101. 102. 103. 104.
if (target.next != null) {
target.next.prev = target.prev;
}
target.next = front;
target.prev = null;
front.prev = target;
return target;
}
105.With the same DLLNode definition as in the previous problem, implement a method to reverse the sequence of items in a DLL. Your code should NOT create any new nodes – it should simply resequence the original nodes. The method should return the front of the
resulting list. public static DLLNode
reverse(DLLNode front) {
106. /** COMPLETE THIS METHOD **/ 107. }
108.
SOLUTION
public static DLLNode reverse(DLLNode front) {
109. if (front == null) {
110. return null;
111. }
112. DLLNode rear=front, prev=null;
113. while (rear != null) {
114. DLLNode temp = rear.next;
115. rear.next = rear.prev;
116. rear.prev = temp;
117. prev = rear;
118. rear = temp;
119. }
120. return prev;
121. }
122.
123.Implement a RECURSIVE method to delete all occurrences of an item from a (non-circular) linked list. Use the Node class definition of problem 1. Return a pointer to the first node in the updated list.
124. public static Node deleteAll(Node front,
String target) {
125. /* COMPLETE THIS METHOD */ 126. }
127.
SOLUTION
128. public static Node deleteAll(Node front,
String target) {
129. if (front == null) { return null; }
130. if (front.data.equals(target)) {
131.
target);
132. 133.
target);
134.
135. 136.
return deleteAll(front.next,
}
front.next = deleteAll(front.next,
return front;
}
137.* Implement a RECURSIVE method to merge two sorted linked lists into a single sorted linked list WITHOUT duplicates. No new nodes must be created: the nodes in the result list are a subset of the nodes in the original lists, rearranged appropriately. You may assume that the original lists do not have any duplicate items.For instance:
l1 = 3->9->12->15 138. l2 = 2->3->6->12 139.
should result in the following:
140.
2->3->6->9->12->15
Assuming a Node class defined like this: public class Node {
141. 142. 143. 144.
public int data;
public Node next;
}
Complete the following method:
145. public static Node merge(Node frontL1, Node
frontL2) {
146. … 147. }
148.
SOLUTION
public static Node merge(Node frontL1, Node
frontL2) {
149. if (frontL1 == null) { return front L2;
}
150. if (frontL2 == null) { return front L1;
}
151. if (frontL1.data == frontL2.data) {
152. 153.
frontL2.next);
154.
// keep one copy
frontL1.next = merge(front1.next,
return frontL1;
155. }
156. if (frontL1.data < frontL2.data) {
157. frontL1.next = merge(front1.next,
frontL2);
158. return frontL1;
159. }
160. frontL2.next = merge(front2.next,
frontL1);
161.
162. }
return frontL2;