The complete set of Java programs for implementing a singly linked on String dat
ID: 3559606 • Letter: T
Question
The complete set of Java programs for implementing a singly linked on String data elements is attached below. The explanation of each file is as follows:
- MyList.java: The interface for list definitions
- MyAbstractList.java : Abstract class for list definitions
- MyLinkedList.java: Singly linked list implementation
- TestMyLinkedList.java: The driver class with main method
In this question, you are required to modify the code for singly linked list on Strings to implement a
doubly linked list on Integer values:
1. Modify the MyLinkedList.java file so that it becomes a doubly linked list, i.e. in addition to the
next pointer the list already contains, it should also contain a previous pointer.
Hint: Modify the Node class, as well as all necessary methods that involve node operations. YOU
ONLY NEED TO MODIFY THE MyLinkedList.java file.
2. Complete the code in MyLinkedList.java program so that the following incomplete methods are
all implemented:
- get(int index)
- set(int index)
- indexOf(E e)
- lastIndexOf(E e)
- contains(E e)
3. Run the following scenario on your doubly linked list to ensure that it runs correctly.
A. Add the numbers 22, 7, 4, 12, 8, 11, 12, 9, 1, 3 in the given order to the doubly linked list
and display the contents of the list.
B. Remove the first element from the doubly linked list and display the contents of the list after
deletion.
C. Remove the last element from the doubly linked list and display the contents of the list after
deletions.
D. Search for element 12 in the doubly linked list from the front of the list.
Hint: You need to call the indexOf(E e) method here. Implementation of this method is deliberately
left out in the given skeleton code. Please make sure to complete it.
E. Search for element 12 in the doubly linked list from the end of the list.
Hint: You need to call the lastIndexOf(E e) method here. Implementation of this method is
deliberately left out in the given skeleton code. Please make sure to complete it.
F. Retrieve the third element (index=2) in the doubly linked list and display it.
Hint: You need to call the get(int index) method.
**MyLinkedList.java: http://www.cs.armstrong.edu/liang/intro9e/html/MyLinkedList.html
**MyAbstractList.java: http://www.cs.armstrong.edu/liang/intro9e/html/MyAbstractList.html
**MyList.java: http://www.cs.armstrong.edu/liang/intro10e/html/MyList.html
**TestMyLinkedList.java:
Explanation / Answer
MyLinkedList.java
public class MyLinkedList<E> extends MyAbstractList<E> {
private Node<E> head, tail;
/** Create a default list */
public MyLinkedList() {
}
/** Create a list from an array of objects */
public MyLinkedList(E[] objects) {
super(objects);
}
/** Return the head element in the list */
public E getFirst() {
if (size == 0) {
return null;
}
else {
return head.element;
}
}
/** Return the last element in the list */
public E getLast() {
if (size == 0) {
return null;
}
else {
return tail.element;
}
}
/** Add an element to the beginning of the list */
public void addFirst(E e) {
Node<E> newNode = new Node<E>(e); // Create a new node
newNode.next = head; // link the new node with the head
newNode.prev = null;
head = newNode; // head points to the new node
size++; // Increase list size
if (tail == null) // the new node is the only node in list
tail = head;
}
/** Add an element to the end of the list */
public void addLast(E e) {
Node<E> newNode = new Node<E>(e); // Create a new for element e
if (tail == null) {
head = tail = newNode; // The new node is the only node in list
}
else {
tail.next = newNode; // Link the new with the last node
newNode.prev = tail; // link the newnode to the previous node
tail = tail.next; // tail now points to the last node
}
size++; // Increase size
}
/** Add a new element at the specified index
* in this list. The index of the head element is 0 */
public void add(int index, E e) {
if (index == 0) {
addFirst(e);
}
else if (index >= size) {
addLast(e);
}
else {
Node<E> current = head;
for (int i = 1; i < index; i++) {
current = current.next;
}
Node<E> temp = current.next;
current.next = new Node<E>(e);
(current.next).next = temp;
size++;
}
}
/** Remove the head node and
* return the object that is contained in the removed node. */
public E removeFirst() {
if (size == 0) {
return null;
}
else {
Node<E> temp = head;
head = head.next;
size--;
if (head == null) {
tail = null;
}
return temp.element;
}
}
/** Remove the last node and
* return the object that is contained in the removed node. */
public E removeLast() {
if (size == 0) {
return null;
}
else if (size == 1) {
Node<E> temp = head;
head = tail = null;
size = 0;
return temp.element;
}
else {
Node<E> current = head;
for (int i = 0; i < size - 2; i++) {
current = current.next;
}
Node<E> temp = tail;
tail = current;
tail.next = null;
size--;
return temp.element;
}
}
/** Remove the element at the specified position in this
* list. Return the element that was removed from the list. */
public E remove(int index) {
if (index < 0 || index >= size) {
return null;
}
else if (index == 0) {
return removeFirst();
}
else if (index == size - 1) {
return removeLast();
}
else {
Node<E> previous = head;
for (int i = 1; i < index; i++) {
previous = previous.next;
}
Node<E> current = previous.next;
previous.next = current.next;
size--;
return current.element;
}
}
/** Override toString() to return elements in the list */
public String toString() {
StringBuilder result = new StringBuilder("[");
Node<E> current = head;
for (int i = 0; i < size; i++) {
result.append(current.element);
current = current.next;
if (current != null) {
result.append(", "); // Separate two elements with a comma
}
else {
result.append("]"); // Insert the closing ] in the string
}
}
return result.toString();
}
/** Clear the list */
public void clear() {
size = 0;
head = tail = null;
}
/** Return true if this list contains the element e */
public boolean contains(E e) {
if(indexOf(e) > 0)
return true;
return false;
}
/** Return the element at the specified index */
public E get(int index) {
Node<E> e = head;
if (index < 0 || index >= size) {
return null;
}
else if (index == 0) {
return e.element;
}
else if (index == size - 1) {
e = tail;
return e.element;
}
else {
Node<E> previous = head;
for (int i = 1; i < index; i++) {
previous = previous.next;
}
Node<E> current = previous.next;
return current.element;
}
}
/** Return the index of the head matching element in
* this list. Return -1 if no match. */
public int indexOf(E e) {
Node<E> current = head;
int pos = -1;
for (int i = 0; i < size; i++) {
if(current.element == e)
{
pos = i;
break;
}
current = current.next;
}
return pos;
}
/** Return the index of the last matching element in
* this list. Return -1 if no match. */
public int lastIndexOf(E e) {
int i = size;
Node<E> current = tail;
if(current.element == e){
return size;
}
else{
while(i > 0 ){
if(current.element == e){
return size - i;
}
current = current.prev;
i--;
}
}
return i;
}
/** Replace the element at the specified position
* in this list with the specified element. */
public E set(int index, E e) {
System.out.println("Implementation left as an exercise");
return null;
}
/** Override iterator() defined in Iterable */
public java.util.Iterator<E> iterator() {
return new LinkedListIterator();
}
private void checkIndex(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException
("Index: " + index + ", Size: " + size);
}
private class LinkedListIterator
implements java.util.Iterator<E> {
private Node<E> current = head; // Current index
public boolean hasNext() {
return (current != null);
}
public E next() {
E e = current.element;
current = current.next;
return e;
}
public void remove() {
System.out.println("Implementation left as an exercise");
}
}
private static class Node<E> {
E element;
Node<E> next, prev;
public Node(E element) {
this.element = element;
}
}
public void add(E e) {
addLast(e);
}
}
TestMyLinkedList.java
public class TestMyLinkedList {
public static void main(String[] args) {
// Create a list
MyLinkedList<Integer> list = new MyLinkedList<Integer>();
// Add elements to the list
list.add(22); // Add it to the list
System.out.println("(1) " + list);
// Add elements to the list
list.add(7); // Add it to the list
System.out.println("(2) " + list);
// Add elements to the list
list.add(4); // Add it to the list
System.out.println("(3) " + list);
// Add elements to the list
list.add(12); // Add it to the list
System.out.println("(4) " + list);
// Add elements to the list
list.add(8); // Add it to the list
System.out.println("(5) " + list);
// Add elements to the list
list.add(11); // Add it to the list
System.out.println("(6) " + list);
// Add elements to the list
list.add(12); // Add it to the list
System.out.println("(7) " + list);
// Add elements to the list
list.add(9); // Add it to the list
System.out.println("(8) " + list);
// Add elements to the list
list.add(1); // Add it to the list
System.out.println("(9) " + list);
// Add elements to the list
list.add(3); // Add it to the list
System.out.println("(10) " + list);
//22, 7, 4, 12, 8, 11, 12, 9, 1, 3
// Remove elements from the list
list.removeFirst(); // Same as list.remove(0) in this case
System.out.println("(11) " + list);
list.removeLast(); // Remove the element at index 2
System.out.println("(12) " + list);
int index = list.indexOf(12);
System.out.println("index of 12 is: " + index);
index = list.lastIndexOf(12);
System.out.println("Last index of 12 is: " + index);
int element = list.get(2);
System.out.println("Element At 2 Is: " + element);
}
}
Other two files MyAbstractList.java and MyList.java are same
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.