In: Computer Science
Data Structures in Java
In the following Singly Linked List implementation, add the following methods, and write test cases in another java file to make sure these methods work.
- Write a private method addAfter(int k, Item item) that takes two arguments, an int argument k and a data item, and inserts the item into the list after the K-th list item.
- Write a method removeAfter(Node node) that takes a linked-list Node as an argument and removes the node following the given node.
- Write a method deleteKth that takes an int argument k and deletes the kth element in a linked list, if it exists.
Notice: Please do not modify the other methods in SLList class, just add the methods above.
public class SLList { private Node first; private Node last; private int n; // size of the list // helper node class private class Node { Item item; Node next; } // constructor: initializes an empty list public SLList() { first = last = null; n = 0; } public boolean isEmpty() { return first == null; } // return the size of the list public int size() { return n; } // insert an item at the front of the list public void addFirst(Item item) { if (isEmpty()) { // first & last refer to the same node first = last = new Node(); first.item = last.item = item; } else { //first refers to the new node Node oldFirst = first; first = new Node(); first.item = item; first.next = oldFirst; } n++; // increment size after insertion } // insert item at the end of the list public void addLast(Item item) { if (isEmpty()) { // first & last refer to the same node first = last = new Node(); first.item = last.item = item; } else { // last.next refers to the new node last = last.next = new Node(); last.item = item; } n++; // increment size after insertion } // remove & return the first item in the list public Item removeFirst() { if (isEmpty()) { throw new RuntimeException("Empty List"); } Item removedItem = first.item; // retrieve the data item being removed if (first == last) { // if there's only one node in the list // update both first & last references first = last = null; } else { // otherwise, update first only first = first.next; } n--; // decrement size after removal return removedItem; } // remove & return the last item in the list public Item removeLast() { if (isEmpty()) throw new RuntimeException("empty list"); Item removedItem = last.item; // retrieve the data item being removed if (first == last) { // if there's only one node in the list, // update both first & last references first = last = null; } else { // iterate through the list to locate the last node Node current = first; while (current.next != last) { current = current.next; } last = current; current.next = null; // ... current is the new last node // } // end else n--; // decrement size after removal return removedItem; } // A String representation of this list, so that clients can print it // (There's no need to change it, but you can, if you'd like.) @Override public String toString() { StringBuilder s = new StringBuilder(); Node current = first; while (current != null) { s.append(current.item + " -> "); // s.append(current.item + " "); current = current.next; } s.append("null"); //s.append("\n"); return s.toString(); } private Node getNode(int index) { Node current = first; for (int i = 0; i < index; i++) { current = current.next; } return current; } public Item get(int index) { if (index < 0 || index >= n) { throw new IndexOutOfBoundsException("out of bounds"); } return getNode(index).item; } public Item set(int index, Item item) { if (index < 0 || index >= n) { throw new IndexOutOfBoundsException("out of bounds"); } Node target = getNode(index); Item oldItem = target.item; target.item = item; return oldItem; } }
public class SLList {
private Node first;
private Node last;
private int n; // size of the list
// helper node class
private class Node {
Item item;
Node next;
}
// constructor: initializes an empty list
public SLList() {
first = last = null;
n = 0;
}
public boolean isEmpty() {
return first == null;
}
// return the size of the list
public int size() {
return n;
}
// insert an item at the front of the list
public void addFirst(Item item) {
if (isEmpty()) { // first & last refer to the same node
first = last = new Node();
first.item = last.item = item;
} else { //first refers to the new node
Node oldFirst = first;
first = new Node();
first.item = item;
first.next = oldFirst;
}
n++; // increment size after insertion
}
// insert item at the end of the list
public void addLast(Item item) {
if (isEmpty()) { // first & last refer to the same node
first = last = new Node();
first.item = last.item = item;
} else { // last.next refers to the new node
last = last.next = new Node();
last.item = item;
}
n++; // increment size after insertion
}
// remove & return the first item in the list
public Item removeFirst() {
if (isEmpty()) {
throw new RuntimeException("Empty List");
}
Item removedItem = first.item; // retrieve the data item being removed
if (first == last) { // if there's only one node in the list
// update both first & last references
first = last = null;
}
else { // otherwise, update first only
first = first.next;
}
n--; // decrement size after removal
return removedItem;
}
// remove & return the last item in the list
public Item removeLast() {
if (isEmpty()) throw new RuntimeException("empty list");
Item removedItem = last.item; // retrieve the data item being removed
if (first == last) { // if there's only one node in the list,
// update both first & last references
first = last = null;
}
else { // iterate through the list to locate the last node
Node current = first;
while (current.next != last) {
current = current.next;
}
last = current;
current.next = null;
// ... current is the new last node
//
} // end else
n--; // decrement size after removal
return removedItem;
}
// A String representation of this list, so that clients can print it
// (There's no need to change it, but you can, if you'd like.)
@Override
public String toString() {
StringBuilder s = new StringBuilder();
Node current = first;
while (current != null) {
s.append(current.item + " -> ");
// s.append(current.item + " ");
current = current.next;
}
s.append("null");
//s.append("\n");
return s.toString();
}
private Node getNode(int index) {
Node current = first;
for (int i = 0; i < index; i++) {
current = current.next;
}
return current;
}
private addAfter(int k,Item item)
{
Item head = headItem;
if (k < 1)
System.out.print("Invalid");
if (k == 1) {
Item newItem = new Item(data);
newItem.nextItem = headItem;
head = newItem;
} else {
while (k-- != 0) {
if (k == 1) {
Item newItem = GetItem(data);
newItem.nextItem = headItem.nextItem;
headItem.nextItem = newItem;
}
headItem = headItem.nextItem;
}
if (k!= 1)
System.out.print("Out of range");
}
return head;
}
public Item get(int index) {
if (index < 0 || index >= n) {
throw new IndexOutOfBoundsException("out of bounds");
}
return getNode(index).item;
}
private deleteAfter(Node node)
{
if (headNode == null)
return;
Node tempNode = headNode;
if (position == 0)
{
headNode = tempNode.next;
return;
}
for (int i=0; tempNode!=null && i<position-1; i++)
tempNode = tempNode.next;
if (tempNode == null || tempNode.next == null)
return;
Node next = tempNode.next.next;
tempNode.next = next;
}
void deleteKth(int k)
{
if (headNode == null)
return;
Node tempNode = headNode;
if (k == 0)
{
headNode = tempNode.next;
return;
}
for (int i=0; tempNode!=null && i<k-1; i++)
tempNode = tempNode.next;
if (tempNode == null || tempNode.next == null)
return;
Node nextNode = tempNode.next.next;
tempNode.next = nextNode;
}
public Item set(int index, Item item) {
if (index < 0 || index >= n) {
throw new IndexOutOfBoundsException("out of bounds");
}
Node target = getNode(index);
Item oldItem = target.item;
target.item = item;
return oldItem;
}
}