I am having problems with my add() method in my linked list implementation. It was working fine until I added the method, doubleInPlace(). It seems that the problem has something to do with how I have myTail implemented. Could someone provide any advice on how to solve this issue?
public void add (Object x) {
ListNode temp;
if(isEmpty()){
myHead = new ListNode(x);
myTail = myHead;
}
else{
ListNode addNode = new ListNode(x);
myTail.setNext(addNode);
myTail = myTail.myNext;
}
mySize++;
}
Here is the full implementation of my linked list.
import java.util.*; public class List implements Iterable{
private ListNode myHead;
private ListNode myTail;
private int mySize;
public List() {
myHead = null;
myTail = null;
mySize = 0;
}
public boolean isEmpty() {
return myHead == null;
}
private static class ListNode {
private Object myItem;
private ListNode myNext;
private ListNode (Object item, ListNode next) {
myItem = item;
myNext = next;
}
private ListNode (Object item) {
myItem = item;
myNext = null;
}
public void setNext(Object item){
myNext = new ListNode(item);
}
public void setNext(ListNode node){
myNext = node;
}
public ListNode getNext(){
return myNext;
}
public void setItem(Object item){
myItem = item;
}
}
public Iterator iterator() {
return new ElementIterator();
}
public class ElementIterator implements Iterator {
ListNode p;
int nextElement;
int size;
public ElementIterator() {
p = myHead;
nextElement = 0;
}
public boolean hasNext() {
if (isEmpty()){
return false;
}
return nextElement < size();
}
public Object next() {
Object next = p.myItem;
if (nextElement < size()){
next = get(nextElement);
nextElement++;
}
return next;
}
public void remove() {
// not used
}
}
public String toString() {
String rtn = "( ";
for (ListNode p = myHead; p != null; p = p.myNext) {
rtn = rtn + p.myItem + " ";
}
return rtn + ")";
}
// Return the number of items in this list ("length" in Scheme).
public int size() {
return mySize;
}
// Return true if the list contains the object
public boolean contains (Object obj) {
for (ListNode p = myHead; p != null; p = p.myNext) {
if (obj.equals (p.myItem)) {
return true;
}
}
return false;
}
// Returns the element at the given position in this list.
public Object get (int pos) {
if (pos < 0) {
throw new IllegalArgumentException (
"Argument to get must be at least 0.");
}
if (pos >= size()) {
throw new IllegalArgumentException ("Argument to get is too large.");
}
int k = 0;
for (ListNode p = myHead; p != null; p = p.myNext) {
if (k == pos) {
return p.myItem;
}
k++;
}
return null;
}
public void addToFront (Object obj) {
myHead = new ListNode (obj, myHead);
mySize++;
}
public boolean equals (Object obj) {
List comp = (List) obj;
ListNode comp_node;
Object compare_node;
boolean isEqual = false;
int count = 0;
if(size()!=comp.size()){
return false;
}
if(obj.toString().equals(this.toString())){
return true;
}
return isEqual;
}
/*public void add (Object x) {
ListNode temp;
if(isEmpty()){
myHead = new ListNode(x);
}
else{
temp = new ListNode(x);
ListNode orig = this.myHead;
for (; orig.myNext != null; orig = orig.myNext){
//orig = orig.myNext;
}
//while (orig.myNext != null){
// orig = orig.myNext;
//}
orig.myNext = new ListNode(x);
}
mySize++;
} */
public void add (Object x) {
ListNode temp;
if(isEmpty()){
myHead = new ListNode(x);
myTail = myHead;
}
else{
ListNode addNode = new ListNode(x);
//myTail.myNext = new ListNode(x, null);
myTail.setNext(addNode);
myTail = myTail.myNext;
}
mySize++;
}
public void appendInPlace (List l) {
if(isEmpty()){
myHead = l.myHead;
myTail = l.myTail;
}else if(l.isEmpty()){
return;
}
else{
myTail.myNext = l.myHead;
myTail = l.myTail;
}
}
//remove all links that are equal to object a
public void remove(Object a){
if (isEmpty()){
return;
}
if (myHead.myItem == a){
myHead = myHead.myNext;
mySize--;
}
//loop through the nodes and if item equals a, set item to next item and ref to next's next
ListNode p = myHead;
ListNode lastNode;
lastNode = new ListNode("");
int tempSize = mySize;
for (int i=0; i < tempSize - 1; i++){
if (p.myItem == a){
lastNode.setNext(p.myNext);
mySize--;
}
lastNode = p;
p = p.myNext;
}
//if tail is equal to item, delete last node
removeTail(a);
}
public void removeTail(Object a){
if (myTail.myItem == a){
ListNode temp = myHead;
ListNode temp2 = myTail;
if (mySize == 2){
temp.myNext = null;
myTail = temp;
}
for (int i = 0; i< mySize-2; i++){
temp = temp.myNext;
}
temp.myNext = null;
myTail = temp;
mySize--;
}
}
public void doubleInPlace() {
ListNode p = myHead;
for (; p != null; p = p.myNext) {
ListNode temp = new ListNode(p.myItem, p.myNext);
p.setNext(temp);
p= p.myNext;
}
myTail = p;
}
public void isOK(){
boolean isOK = true;
//Check size is ok
int mySizeCheck = 0;
ListNode temp = myHead;
while (temp != null){
temp = temp.myNext;
mySizeCheck++;
}
if (temp.myItem != myTail.myItem){
throw new IllegalStateException("The tail is not correct.");
}
if (mySize != mySizeCheck){
throw new IllegalStateException("The size is not correct.");
}
}
}