The Java code for implementing a singly linked on String data
elements is given as a bundle of interfaces/abstract classes, concrete implementations and the driver
class 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 mainmethod
In this question, you are required to modify the code for singly linked list 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 linkedlist to ensure that it runs correctly.
A. Add the numbers 22, 7, 4, 12, 8, 11, 12, 9, 1, 3in 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.
C. Remove the last element from the doubly linked list and display the contents of the list.
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 left as an
exercise 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 left as
an exercise in the given skeleton code. Please makesure 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 here.
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
//package week10;
public abstract class MyAbstractList<E> implements MyList<E> {
protected int size = 0; // The size of the list
/** Create a default list */
protected MyAbstractList() {
}
/** Create a list from an array of objects */
protected MyAbstractList(E[] objects) {
for (int i = 0; i < objects.length; i++)
add(objects);
}
/** Add a new element at the end of this list */
public void add(E e) {
add(size, e);
}
/** Return true if this list contains no elements */
public boolean isEmpty() {
return size == 0;
}
/** Return the number of elements in this list */
public int size() {
return size;
}
/** Remove the first occurrence of the element o from this list.
* Shift any subsequent elements to the left.
* Return true if the element is removed. */
public boolean remove(E e) {
if (indexOf(e) >= 0) {
remove(indexOf(e));
return true;
}
else
return false;
}
}
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
//package week10;
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
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
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() {
head = tail = null;
}
/** Return true if this list contains the element o */
public boolean contains(E e) {
System.out.println("Implementation left as an exercise");
return true;
}
/** Return the element from this list at the specified index */
public E get(int index) {
System.out.println("Implementation left as an exercise");
return null;
}
/** Return the index of the head matching element in this list.
* Return -1 if no match. */
public int indexOf(E e) {
System.out.println("Implementation left as an exercise");
return 0;
}
/** Return the index of the last matching element in this list
* Return -1 if no match. */
public int lastIndexOf(E e) {
System.out.println("Implementation left as an exercise");
return 0;
}
/** 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;
}
private static class Node<E> {
E element;
Node<E> next;
public Node(E element) {
this.element = element;
}
}
}
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package week10;
/**
*
* @author exc067000
*/
public class TestMyLinkedList {
public static void main(String[] args) {
// Create a list
MyLinkedList<String> list = new MyLinkedList<String>();
// Add elements to the list
list.add("LL 1"); // Add it to the list
System.out.println("(1) " + list);
list.add(0, "LL 2"); // Add it to the beginning of the list
System.out.println("(2) " + list);
list.add("LL 3 "); // Add it to the end of the list
System.out.println("(3) " + list);
list.add("LL 4"); // Add it to the end of the list
System.out.println("(4) " + list);
list.add(2, "LL 5"); // Add it to the list at index 2
System.out.println("(5) " + list);
list.add(5, "LL 6"); // Add it to the list at index 5
System.out.println("(6) " + list);
// Remove elements from the list
list.remove("LL 3"); // Same as list.remove(0) in this case
System.out.println("(7) " + list);
list.remove(2); // Remove the element at index 2
System.out.println("(8) " + list);
list.remove(list.size() - 1); // Remove the last element
System.out.println("(9) " + list);
}
}
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
//package week10;
public interface MyList<E> {
/** Add a new element at the end of this list */
public void add(E e);
/** Add a new element at the specified index in this list */
public void add(int index, E e);
/** Clear the list */
public void clear();
/** Return true if this list contains the element */
public boolean contains(E e);
/** Return the element from this list at the specified index */
public E get(int index);
/** Return the index of the first matching element in this list.
* Return -1 if no match. */
public int indexOf(E e);
/** Return true if this list contains no elements */
public boolean isEmpty();
/** Return the index of the last matching element in this list
* Return -1 if no match. */
public int lastIndexOf(E e);
/** Remove the first occurrence of the element o from this list.
* Shift any subsequent elements to the left.
* Return true if the element is removed. */
public boolean remove(E e);
/** Remove the element at the specified position in this list
* Shift any subsequent elements to the left.
* Return the element that was removed from the list. */
public E remove(int index);
/** Replace the element at the specified position in this list
* with the specified element and returns the new set. */
public Object set(int index, E e);
/** Return the number of elements in this list */
public int size();
}
elements is given as a bundle of interfaces/abstract classes, concrete implementations and the driver
class 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 mainmethod
In this question, you are required to modify the code for singly linked list 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 linkedlist to ensure that it runs correctly.
A. Add the numbers 22, 7, 4, 12, 8, 11, 12, 9, 1, 3in 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.
C. Remove the last element from the doubly linked list and display the contents of the list.
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 left as an
exercise 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 left as
an exercise in the given skeleton code. Please makesure 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 here.
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
//package week10;
public abstract class MyAbstractList<E> implements MyList<E> {
protected int size = 0; // The size of the list
/** Create a default list */
protected MyAbstractList() {
}
/** Create a list from an array of objects */
protected MyAbstractList(E[] objects) {
for (int i = 0; i < objects.length; i++)
add(objects);
}
/** Add a new element at the end of this list */
public void add(E e) {
add(size, e);
}
/** Return true if this list contains no elements */
public boolean isEmpty() {
return size == 0;
}
/** Return the number of elements in this list */
public int size() {
return size;
}
/** Remove the first occurrence of the element o from this list.
* Shift any subsequent elements to the left.
* Return true if the element is removed. */
public boolean remove(E e) {
if (indexOf(e) >= 0) {
remove(indexOf(e));
return true;
}
else
return false;
}
}
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
//package week10;
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
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
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() {
head = tail = null;
}
/** Return true if this list contains the element o */
public boolean contains(E e) {
System.out.println("Implementation left as an exercise");
return true;
}
/** Return the element from this list at the specified index */
public E get(int index) {
System.out.println("Implementation left as an exercise");
return null;
}
/** Return the index of the head matching element in this list.
* Return -1 if no match. */
public int indexOf(E e) {
System.out.println("Implementation left as an exercise");
return 0;
}
/** Return the index of the last matching element in this list
* Return -1 if no match. */
public int lastIndexOf(E e) {
System.out.println("Implementation left as an exercise");
return 0;
}
/** 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;
}
private static class Node<E> {
E element;
Node<E> next;
public Node(E element) {
this.element = element;
}
}
}
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package week10;
/**
*
* @author exc067000
*/
public class TestMyLinkedList {
public static void main(String[] args) {
// Create a list
MyLinkedList<String> list = new MyLinkedList<String>();
// Add elements to the list
list.add("LL 1"); // Add it to the list
System.out.println("(1) " + list);
list.add(0, "LL 2"); // Add it to the beginning of the list
System.out.println("(2) " + list);
list.add("LL 3 "); // Add it to the end of the list
System.out.println("(3) " + list);
list.add("LL 4"); // Add it to the end of the list
System.out.println("(4) " + list);
list.add(2, "LL 5"); // Add it to the list at index 2
System.out.println("(5) " + list);
list.add(5, "LL 6"); // Add it to the list at index 5
System.out.println("(6) " + list);
// Remove elements from the list
list.remove("LL 3"); // Same as list.remove(0) in this case
System.out.println("(7) " + list);
list.remove(2); // Remove the element at index 2
System.out.println("(8) " + list);
list.remove(list.size() - 1); // Remove the last element
System.out.println("(9) " + list);
}
}
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
//package week10;
public interface MyList<E> {
/** Add a new element at the end of this list */
public void add(E e);
/** Add a new element at the specified index in this list */
public void add(int index, E e);
/** Clear the list */
public void clear();
/** Return true if this list contains the element */
public boolean contains(E e);
/** Return the element from this list at the specified index */
public E get(int index);
/** Return the index of the first matching element in this list.
* Return -1 if no match. */
public int indexOf(E e);
/** Return true if this list contains no elements */
public boolean isEmpty();
/** Return the index of the last matching element in this list
* Return -1 if no match. */
public int lastIndexOf(E e);
/** Remove the first occurrence of the element o from this list.
* Shift any subsequent elements to the left.
* Return true if the element is removed. */
public boolean remove(E e);
/** Remove the element at the specified position in this list
* Shift any subsequent elements to the left.
* Return the element that was removed from the list. */
public E remove(int index);
/** Replace the element at the specified position in this list
* with the specified element and returns the new set. */
public Object set(int index, E e);
/** Return the number of elements in this list */
public int size();
}
Facebook
Twitter