How do I implement a remove by index method for a singly linked list in Java?

Posted by Lars Flyger on Stack Overflow See other posts from Stack Overflow or by Lars Flyger
Published on 2010-04-16T12:53:25Z Indexed on 2010/04/16 13:13 UTC
Read the original article Hit count: 470

Filed under:
|
|

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;
  }
 }
}'

© Stack Overflow or respective owner

Related posts about java

Related posts about linked-list