How do I implement a remove by index method for a singly linked list in Java?
- by Lars Flyger
Hi, I'm a student in a programming class, and I need some help with this code I've written. So far I've written an entire linked list class (seen below), yet for some reason the "removeByIndex" method won't work. I can't seem to figure out why, the logic seems sound to me. Is there some problem I don't know about?
public class List<T> {
//private sub-class Link
private class Link {
private T value;
private Link next;
//constructors of Link:
public Link (T val) {
this.value = val;
this.next = null;
}
public Link (T val, Link next) {
this.value = val;
this.next = next;
}
@SuppressWarnings("unused")
public T getValue() {
return value;
}
}
private static final Exception NoSuchElementException = null;
private static final Exception IndexOutOfBoundsException = null;
private Link chain = null;
//constructors of List:
public List() {
this.chain = null;
}
//methods of List:
/**
* Preconditions: none
* Postconditions: returns true if list is empty
*/
public boolean isEmpty() {
return this.chain == null;
}
/**
* Preconditions: none
* Postconditions: A new Link is added via add-aux
* @param element
*/
public void add(T element) {
this.add_aux(element, this.chain);
}
/**
* Preconditions: none
* Postconditions: A new Link is added to the current chain
* @param element
* @param chain
*/
private void add_aux(T element, Link chain) {
if (chain == null) {
//if chain is null set chain to a new Link with a value of
//element
this.chain = new Link(element);
}
else if (chain.next != null) {
//if chain.next is not null, go to next item in chain and
//try
//to add element
add_aux(element, chain.next);
}
else {
//if chain.next is null, set chain.next equal to a new Link
//with value of element.
chain.next = new Link(element);
}
}
/**
* Preconditions: none
* Postconditions: returns the link at the defined index via nthlink_aux
* @param index
* @return
*/
private Link nthLink (int index) {
return nthLink_aux(index, this.chain);
}
/**
* Preconditions: none
* Postconditions: returns the link at the defined index in the specified
*chain
* @param i
* @param c
* @return
*/
private Link nthLink_aux (int i, Link c) {
if (i == 0) {
return c;
}
else return nthLink_aux(i-1, c.next);
}
/**
* Preconditions: the specified element is present in the list
* Postconditions: the specified element is removed from the list
* @param element
* @throws Exception
*/
public void removeElement(T element) throws Exception {
if (chain == null) {
throw NoSuchElementException;
}
//while chain's next is not null and the value of chain.next is not
//equal to element,
//set chain equal to chain.next
//use this iteration to go through the linked list.
else while ((chain.next != null) && !(chain.next.value.equals(element))){
Link testlink = chain.next;
if (testlink.next.value.equals(element)) {
//if chain.next is equal to element, bypass the
//element.
chain.next.next = chain.next.next.next;
}
else if (testlink.next == null) {
throw NoSuchElementException;
}
}
}
/**
* Preconditions: none
* Postsconditions: the Link at the specified index is removed
* @param index
* @throws Exception
*/
public void removeByIndex(int index) throws Exception {
if (index == 0) {
//if index is 0, set chain equal to chain.next
chain = chain.next;
}
else if (index > 0) {
Link target = nthLink(index);
while (target != null) {
if (target.next != null) {
target = target.next;
}
//if target.next is null, set target to null
else {
target = null;
}
}
return;
}
else throw IndexOutOfBoundsException;
}
/**
* Preconditions: none
* Postconditions: the specified link's value is printed
* @param link
*/
public void printLink (Link link) {
if(link != null) {
System.out.println(link.value.toString());
}
}
/**
* Preconditions: none
* Postconditions: all of the links' values in the list are printed.
*/
public void print() {
//copy chain to a new variable
Link head = this.chain;
//while head is not null
while (!(head == null)) {
//print the current link
this.printLink(head);
//set head equal to the next link
head = head.next;
}
}
/**
* Preconditions: none
* Postconditions: The chain is set to null
*/
public void clear() {
this.chain = null;
}
/**
* Preconditions: none
* Postconditions: Places the defined link at the defined index of the list
* @param index
* @param val
*/
public void splice(int index, T val) {
//create a new link with value equal to val
Link spliced = new Link(val);
if (index <= 0) {
//copy chain
Link copy = chain;
//set chain equal to spliced
chain = spliced;
//set chain.next equal to copy
chain.next = copy;
}
else if (index > 0) {
//create a target link equal to the link before the index
Link target = nthLink(index - 1);
//set the target's next equal to a new link with a next
//equal to the target's old next
target.next = new Link(val, target.next);
}
}
/**
* Preconditions: none
* Postconditions: Check to see if element is in the list, returns true
* if it is and false if it isn't
* @param element
* @return
*/
public boolean Search(T element) {
if (chain == null) {
//return false if chain is null
return false;
}
//while chain's next is not null and the value of chain.next is not
//equal to element,
//set chain equal to chain.next
//use this iteration to go through the linked list.
else while ((chain.next != null) && !(chain.next.value.equals(element))) {
Link testlink = chain.next;
if (testlink.next.value.equals(element)) {
//if chain.next is equal to element, return true
return true;
}
else if (testlink.next == null) {
return false;
}
}
return false;
}
/**
* Preconditions: none
* Postconditions: order of the links in the list is reversed.
*/
public void reverse() {
//copy chain
Link current = chain;
//set chain equal to null
chain = null;
while (current != null) {
Link save = current;
current = current.next;
save.next = chain;
chain = save;
}
}
}'
