Programming Exercise For the following programming exercise, please study the co
ID: 3586849 • Letter: P
Question
Programming Exercise
For the following programming exercise, please study the code SingleLinkedList.java (enclosed in this folder) and work on the following exercises.
1. Write a remove method that removes the item at a specified index.
2. Using the single-linked list shown in the figure above, and assuming that head references the first Node and tail references the last Node, write statements to do each of the following: a. Insert "Bill" before "Tom". b. Insert "Sue" before "Sam". c. Remove "Bill". d. Remove "Sam".
3. Write method remove for class SingleLinkedList: /** Remove the first occurrence of element item. @param item The item to be removed @return true if item is found and removed; otherwise, return false. */ public boolean remove(E item)
4. Write the following method add for class SingleLinkedList without using any helper methods.
/** Insert a new item before the one at position index, starting at 0 for the list head. The new item is inserted between the one at position index - 1 and the one formerly at position index.
@param index The index where the new item is to be inserted @param item The item to be inserted
@throws IndexOutOfBoundsException if the index is out of range */ public void add(int index, E item)
/**
* SingleLinkedList is a class that provides some of the
* capabilities required by the List interface using
* a single linked list data structure.
* Only the following methods are provided:
* get, set, add, remove, size, toString
* @author Your Name
*/
public class SingleLinkedList {
// Nested Class
/**/
/** A Node is the building block for the SingleLinkedList */
private static class Node {
/** The data value. */
private E data;
/** The link */
private Node next = null;
/**
* Construct a node with the given data value and link
* @param data - The data value
* @param next - The link
*/
public Node(E data, Node next) {
this.data = data;
this.next = next;
}
/**
* Construct a node with the given data value
* @param data - The data value
*/
public Node(E data) {
this(data, null);
}
}
/*
*/
// Data fields
/** A reference to the head of the list */
private Node head = null;
/** The size of the list */
private int size = 0;
// Helper Methods
/** Insert an item as the first item of the list.
* @param item The item to be inserted
*/
private void addFirst(E item) {
head = new Node(item, head);
size++;
}
/**
* Add a node after a given node
* @param node The node which the new item is inserted after
* @param item The item to insert
*/
private void addAfter(Node node, E item) {
node.next = new Node(item, node.next);
size++;
}
/**
* Remove the first node from the list
* @returns The removed node's data or null if the list is empty
*/
private E removeFirst() {
Node temp = head;
if (head != null) {
head = head.next;
}
if (temp != null) {
size--;
return temp.data;
} else {
return null;
}
}
/**
* Remove the node after a given node
* @param node The node before the one to be removed
* @returns The data from the removed node, or null
* if there is no node to remove
*/
private E removeAfter(Node node) {
Node temp = node.next;
if (temp != null) {
node.next = temp.next;
size--;
return temp.data;
} else {
return null;
}
}
/**
* Find the node at a specified index
* @param index The index of the node sought
* @returns The node at index or null if it does not exist
*/
private Node getNode(int index) {
Node node = head;
for (int i = 0; i < index && node != null; i++) {
node = node.next;
}
return node;
}
// Public Methods
/**
* Get the data value at index
* @param index The index of the element to return
* @returns The data at index
* @throws IndexOutOfBoundsException if the index is out of range
*/
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException(Integer.toString(index));
}
Node node = getNode(index);
return node.data;
}
/**
* Set the data value at index
* @param index The index of the item to change
* @param newValue The new value
* @returns The data value priviously at index
* @throws IndexOutOfBoundsException if the index is out of range
*/
public E set(int index, E newValue) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException(Integer.toString(index));
}
Node node = getNode(index);
E result = node.data;
node.data = newValue;
return result;
}
/**
* Insert the specified item at the specified position in the list.
* Shifts the element currently at that position (if any) and any
* subsequent elements to the right (adds one to their indicies)
* @param index Index at which the specified item is to be inserted
* @param item The item to be inserted
* @throws IndexOutOfBoundsException if the index is out of range
*/
public void add(int index, E item) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException(Integer.toString(index));
}
if (index == 0) {
addFirst(item);
} else {
Node node = getNode(index - 1);
addAfter(node, item);
}
}
/**
* Append the specified item to the end of the list
* @param item The item to be appended
* @returns true (as specified by the Collection interface)
*/
public boolean add(E item) {
add(size, item);
return true;
}
/**/
/**
* Remove the item at the specified position in the list. Shifts
* any squsequent items to the left (subtracts one from their
* indicies). Returns the tiem that was removed.
* @param index The index of the item to be removed
* @returns The item that was at the specified position
* @throws IndexOutOfBoundsException if the index is out of range
*/
public E remove(int index) {
}
/**/
/**
* Query the size of the list
* @return The number of objects in the list
*/
int size() {
return size;
}
/**
* Obtain a string representation of the list
* @return A String representation of the list
*/
@Override
public String toString() {
StringBuilder sb = new StringBuilder("[");
Node p = head;
if (p != null) {
while (p.next != null) {
sb.append(p.data.toString());
sb.append(" ==> ");
p = p.next;
}
sb.append(p.data.toString());
}
sb.append("]");
return sb.toString();
}
/**/
/**
* Remove the first occurence of element item.
* @param item The item to be removed
* @return true if item is found and removed; otherwise, return false.
*/
public boolean remove(E item) {
}
/**/
/* /**
* Insert a new item before the one at position index,
* starting at 0 for the list head. The new item is inserted
* between the one at position index-1 and the one formally
* at position indes.
* The exercise requirements are to not use any helper methods.
* Since there already is an add method that uses helper
* methods, this one is named add2.
* @param index The index where the new item is to be inserted
* @param item The item to be inserted
* @throws IndexOutOfBoundsException if the indes is out of range
*/
public void add2(int index, E item) {
}
/**/
/**/
public static void exercise_2_5_2() {
// Create the list of figure 2.16
}
/**/
}
/**/
Explanation / Answer
1. public E remove(int index) {
Node temp = head;
Node prev = null;
while(index == 0 || temp!= null){
prev = temp;
temp = temp.next;
}
if(index == 0)
prev.next = temp.next;
return temp;
}
2.
SingleLinkedList lst = new SingleLinkedList();
lst.addAfter(new Node("Tom"),"Bill");
lst.addAfter(new Node("Sam"),"Sue");
lst.remove("Bill");
lst.remove("Sam");3. public boolean remove(E item) {
Node temp = head;
int index =0;
boolean flag = false;
while(temp!= null){
if(temp == item){
flag = true;
break;
}
temp = temp.next;
index++;
}
if(flag)
remove(index);
return flag;
}
4. public void add2(int index, E item) {
if(index > 1)
add(index-1,item);
else
add(0,item);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.