Write a class called GenDoublLinkedList which is a generic double linked list. T
ID: 638485 • Letter: W
Question
Write a class called GenDoublLinkedList which is a generic double linked list. This link list is similar to the single linked list that was shown in class except that each node in addition to having data and nextLink(which was originally called link) now has prevLink. Download the driver
(DO NOT MODIFY THE DRIVER!) and write the following classes:
The class GenDoubleLinkedList needs to have the following:
Insert Node After Current
Delete Current Node
Example Dialog:
Double Linked List Tester
Create, insert, and move test
1
2
3
4
Previous and Deletion Test
1
2
4
In list test
true
false
Test Done
Head CurrentExplanation / Answer
package com.ketonax.utilities;
import java.util.ArrayList;
public class LinkedList<T> {
private ListNode head, tail, current, previous;
private int length;
public LinkedList() {
head = tail = current = previous = null;// Sets everything to null.
length = 0;
}
public void add(T data) {// Adds new node to the tail end of the list.
length++;// Increases size of the list.
if (head == null) {
current = head = tail = new ListNode(data, tail);
} else {
previous = tail;// Old tail becomes previous.
ListNode newNode = new ListNode(data, null);
tail.link = newNode;
current = tail = newNode;// newNode becomes the new tail.
}
}
public void add(T data, int targetIndex) throws LinkedListException {
ListNode position = find(targetIndex), predecessor = find(targetIndex - 1);
ListNode newNode = new ListNode();
newNode.data = data;
if (predecessor == null && position != head)
throw new LinkedListException("Target index out of bounds.");
else if (position == head) {// At head.
if (head == null) {
newNode.link = position;
current = head = newNode;
} else {
newNode.link = position;
current = head = newNode;
}
} else if (predecessor != null && position == null) {// At tail.
tail.link = newNode;
current = tail = newNode;
} else {// Anywhere else on the list.
current = newNode.link = position;// newNode link is point
predecessor.link = newNode;// Node before position now links to
// newNode.
}
}
public void deleteHead() throws LinkedListException {
length--;// Reduces size of the list.
if (head != null)
head = head.link;
else
throw new LinkedListException(
"Using deleteHead with an empty list.");
}
public void deleteTail() throws LinkedListException {
length--;// Reduces size of the list.
ListNode position = head;
if (head.link != null) {// Checking for list with only 1 node.
while (position != null) {
if (position.link == tail) {// Node position is at node before
// tail
position.link = null;
tail = position;
}
position = position.link;
}
} else
throw new LinkedListException("List has only 1 node (head).");
}
public void delete(int targetIndex) throws LinkedListException {
length--;// Reduces size of the list.
ListNode position, previousPosition;
if (head != null) {
if (targetIndex < 1 || targetIndex > length)
throw new LinkedListException(
"Target position is out of list bounds.");
position = find(targetIndex);
if (position == head)
head = head.link;
else {
previousPosition = find(targetIndex - 1);
if (position == tail) {
previousPosition.link = position.link;
tail = previousPosition;
} else
previousPosition.link = position.link;
}
} else
throw new LinkedListException("Using delete on an empty list.");
}
public void clearList() {
head = null;
tail = null;
current = null;
previous = null;
length = 0;
}
public void setDataAtPosition(int targetIndex, T data)
throws LinkedListException {
if (head != null) {
if (targetIndex < 1 || targetIndex > length)
throw new LinkedListException("Index out of bounds");
else
find(targetIndex).data = data;
} else
throw new LinkedListException(
"Using setDataAtPosition on an empty list.");
}
public T getDataAtPosition(int targetIndex) throws LinkedListException {
if (head != null) {
if (targetIndex < 1 || targetIndex > length)
throw new LinkedListException("Index out of bounds");
else
return find(targetIndex).data;
} else
throw new LinkedListException(
"Using getDataAtPosition on an empty list.");
}
public int getLength() {
return length;
}
public void showList() {
ListNode position = head;
while (position != null) {
System.out.println(position.data);
position = position.link;
}
}
public boolean contains(T target) {
return find(target) != null;
}
217
218 public boolean isEmpty() {
219
220 return head == null;
221
222 }
223
224 public ArrayList<T> toArrayList() {
225
226 ArrayList<T> listToReturn = new ArrayList<T>();
227 ListNode position = head;
228
229 while (position != null) {
230
231 listToReturn.add(position.data);
232 position = position.link;
233
234 }
235
236 return listToReturn;
237
238 }
239
240 // Beginning of internal iterator methods
241 public void resetIteration() {
242
243 current = head;
244 previous = null;
245
246 }
247
248 public boolean hasNext() {
249
250 return current != null;
251
252 }
253
254 public void goToNext() throws LinkedListException {
255
256 if (current != null) {
257
258 previous = current;
259 current = current.link;
260
261 } else if (head != null)
262 throw new LinkedListException(
263 "Iterated too many times, or unitialized iteration");
264 else
265 throw new LinkedListException("Iterating on an empty list");
266
267 }
268
269 public T getDataAtCurrent() throws LinkedListException {
270
271 T result = null;
272
273 if (current != null)
274 result = current.data;
275 else if (head != null)
276 throw new LinkedListException(
277 "Current is past all nodes or uninitialized.");
278 else
279 throw new LinkedListException(
280 "Using getDataAtCurrent with an empty list.");
return result;
}
public void insertNodeAfterCurrent(T data) throws LinkedListException {
length++;// Increases size of the list.
ListNode newNode = new ListNode();
newNode.data = data;
if (current != null) {
newNode.link = current.link;
current.link = newNode;
} else if (head != null)
throw new LinkedListException(
"Current is past all nodes, or unitialized.");
else
throw new LinkedListException(
"Using insertNodeAfterCurrent with an empty list");
}
public void setDataAtCurrent(T data) throws LinkedListException {
if (current != null)
current.data = data;
else if (head != null)
throw new LinkedListException(
"Current is past all nodes or uninitialized.");
else
throw new LinkedListException("Editing an empty list.");
}
public void deleteCurrentNode() throws LinkedListException {
length--;// Reduces size of the list.
if (current != null && previous != null) {
previous.link = current.link;
current = current.link;
} else if (current != null && previous == null) {
head = current.link;
current = head;
} else if (current != null && current.link == null) {
previous.link = current.link;
current = current.link;
tail = previous;
} else
throw new LinkedListException(
"Trying to delete an empty list, or unitialized iteration.");
}
// End of internal iterator methods.
private ListNode find(T target) {
boolean found = false;
ListNode position = head;
while (position != null && found == false) {
if (position.data == target)
found = true;
else
position = position.link;
}
return position;
}
private ListNode find(int targetIndex) {
ListNode position = head;
boolean found = false;
int count = 1;
if (targetIndex < 1)
position = null;
else {
while (position != null && found == false) {
if (count == targetIndex)
found = true;
else
position = position.link;
count++;
}
}
return position;
}
private class ListNode {
T data;
ListNode link;
public ListNode() {
data = null;
link = null;
}
public ListNode(T newData, ListNode linkValue) {
data = newData;
link = linkValue;
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.