# Linked List Help

• February 4th, 2011, 05:54 PM
lieles
Hi, I have having a lot of trouble with linked lists, i understand the theory, but I can't seem to figure out how to write the code. I have to make a linked list of doubles and finish writing the rest of the class, any help is really really appreciated:)
I am having the most trouble with removing nodes, and also with addback() (the tail reference)
Thank you!!!!

{
private DoubleNode tail;
private int size;
public static final double NaN;
{
this.tail = null;
this.size = 0;
}

public void addFront(double d)
{
if(size == 0){
DoubleNode newNode;
newNode = new DoubleNode(d);

size++;
}else{
DoubleNode newNode;
newNode = new DoubleNode(d);

size++;
}
}

public void addBack(double d)
{
DoubleNode newNode;
newNode = new DoubleNode(d);
size++;
}else{

DoubleNode newNode;
tail.next() = newNode;
newNode = new DoubleNode(d);
tail = newNode;
tail.setNext(tail);
size++;
}
}

public void remove(double d)
{

}

public void removeThreshold(double d, double threshold)
{
DoubleNode compare = head;
double d1 = d + threshold;
double d2 = d - threshold;
if(compare.getItem() >= d2 && compare.getItem() <= d1 ){

}
}

public int size()
{
return size;
}

public int withinThreshold(double d, double threshold)
{
int count = 0;
double d1 = d + threshold;
double d2 = d + threshold;
for(DoubleNode compare = head; compare.next() != null; compare = compare.next()){
if(compare.getItem() >= d2 && compare.getItem() <= d1){
count++;
}
}
return count;
}

public double maximum()
{
DoubleNode compare = head;
if(size >= 1){
while(compare.next() != null){
if(compare.next() > compare || compare.next() == compare){
compare = compare.next();
}
}
return compare.getItem();
}else{
return Double.NaN;
}
}

public double minimum()
{
DoubleNode compare = head;
if(size >= 1){
while(compare.next() != null){
if(compare.next() > compare || compare.next() == compare){
compare = compare.next();
}
}
return compare.getItem();
}else{
return Double.NaN;
}
}

public double mean()
{
double mean = 0.0;
DoubleNode curr = head;
mean += curr.getItem();
if (size >= 1){
curr = curr.next();
mean += curr.getItem();
}
return (mean / size);
}

public double elementAt(int index)
{

}
public String toString()
{
DoubleNode curr = head;
String list = "{";
list += curr;
while(curr == null){
list += ", ";
curr = curr.next();
list += curr;
}
list += "}";
return list;
}

}
• February 4th, 2011, 09:32 PM
javapenguin
Re: Linked List Help
I happen to have written a DoublyLinkedLIst(same as Linked List) class earlier and you can look at it if you want. These can hold any parameter type.

However, you can later make a main method that has one of these that holds type Double if you want.

Code java:

```package ProjectOfDoom;   public interface MyCollection<T> {   public void add(int index, T data); public void remove(int index); public void addFirst(T data); public void addLast(T data); public void removeFirst(); public void removeLast();   public void removeRange(int from, int to); public void removeAll(); public int Size(); public T get(int value);     }```

Code java:

```import javax.swing.Icon; import javax.swing.ImageIcon; import javax.swing.JOptionPane; import java.util.*; import java.io.*; //Paul Adcock // Assignment 4 // Lasted Worked On: 12/31/2010   /* this class is the Doubly Linked list class. It has a Node that holds a reference to some date of type T and has a reference   to the next Node and to the previous Node. It is a generic class than can hold date types. */     public class DoublyLinkedList<T> implements MyCollection<T> {   /* This is the generic class Node, a private innner class of DoublyLnkedList. */ private class Node<T> { /* * variables * T data - a variable of generic type * a Node next, which refers to the Node after the current Node * a Node previous, which refers to the Node before the current Node */ private T data; private Node<T> next; private Node<T> previous;   /* * Constructor Node(T data, Node<T> next, Node<T> previous) * parameters T data * a Node next * a Node previous */ public Node(T data,Node<T> next, Node<T> previous) { this.data = data; this.next = next; this.previous=previous; }   /* * returns the data of that Node */ public T getData() { return data; }   /* * returns the Node after the current Node */ public Node<T> getNext() { return next; }   /* * returns the Node before the current Node */ public Node<T> getPrevious() { return previous; }   /* * sets the Node after the current Node to next */ public void setNext(Node<T> next) { this.next = next; }   /* * sets the Node before the current Node to previous */ public void setPrevious(Node<T> previous) { this.previous = previous; }   /* * creates a copy of the Node and returns that copy * @see java.lang.Object#clone() */ public Node<T> clone() { Node<T> copy = new Node<T>(this.getData(), this.getNext(), this.getPrevious()); return copy; } }   /* * data for class DoublyLinkedList * Node head - beginning of DoublyLinkedList * Node tail - end of DoublyLinkedList * int side - size of DoublyLinkedList * */ private Node<T> head;//head of the linked list private Node<T> tail; // tail of linked list private int size; private DoublyLinkedList<T> subDLL; private DoublyLinkedList<T> anotherOne, anotherOne2; private ImageIcon icon; private DoublyLinkedList<T> copiedDLL; private Icon icon2; /* * constructor DoublyLinkedList() * no parameters */ public DoublyLinkedList() { /* * sets head and tail to null * sets size to 0 */ head = null; tail = null; size = 0; icon = new ImageIcon("doh3.jpg"); }       /* * returns a String of all the elements in the DoublyLinkedList * @see java.lang.Object#toString() */ public String toString() { String str = "[";   Node<T> curr;   for (curr=head;curr!=null;curr = curr.getNext()) { str = str + curr.getData().toString(); if (curr.getNext()!=null) str = str + " "; } str = str + "]"; return str;     }   public T middle() {   int middle = (int) (Size() -1 ) /2; return (get(middle));   }   /* * removeRange(int from, int to) * from - the starting index to remove * to - the last index to remove * removes all values between from and to */ public void removeRange(int from, int to) { if (from < 0 || from >= Size() || to < 0 || to >=Size()) { return; }   if (from >=to) { for (int j = from; j >= to; j--) { remove(j); } return; }   for (int i = from; i <=to; i++) { remove(i); } }   // adds the data as the first element. If the list size is 0, makes first element tail. If head is not null, it puts the old // tail as the second element and the new element as the new head. /* * addFirst(T data) * data - the type of data * adds the data to the beginning of the DoublyLinkedList */ public void addFirst(T data) { /* Since this is the first Object, previous should be null */ Node<T> newNode = new Node<T>(data,head,null); //We know that if head is null, the list is empty if (head==null) { //If the list is empty, tail will be newNode tail = newNode; }   if(head!=null) head.setPrevious(newNode);   //We want to set head to be newNode // if the list was empty before, both head and tail will be set to newNode; head = newNode; //Increment Size size++; }   /* * removes the data the begining of the DoublyLinkedList */ // an alternate way of doing this would just be to call remove(0) public void removeFirst() { if (size == 0) { JOptionPane pane = new JOptionPane(); pane.setIcon(icon); pane.showMessageDialog(null, "Cannot remove from an empty list!", "Invalid removal", JOptionPane.ERROR_MESSAGE); pane.setMessageType(JOptionPane.ERROR_MESSAGE);   return; } Node<T> current = head; // creates a Node called current and sets it to head.   head = head.getNext(); //move head to the next element   current.setNext(null); size--; }   /* * addLast(T data) * parameters data * data- the data to be added * adds data to end of DoublyLinkedList */ public void addLast(T data) { //If there are no elements, use the addFirst method if (tail == null) { addFirst(data); return; } /* Create the new Node from the data. Set next to null * because this will be the last element and will not * have a next. Set previous to tail because tail has * not been changed yet and is currently referencing * that element that will be directly before this element */ Node<T> newNode = new Node<T>(data,null,tail); /* Since the tail variable still references the element * directly before the new element, we can set that node's * next to our new element. */ tail.setNext(newNode); //Set tail to our new Node tail = newNode; //Increment size size++; }   /* * returns the size of the DoublyLinkedList */ public int Size() { return(size); }   /* * add(int index, T data) * parameters index, data * index - the index to add the data * data- the data to add * adds the data at the specified index */ public void add(int index,T data) { int i; if (index == 0) { addFirst(data); return;   } if (index>size) { JOptionPane.showMessageDialog(null, "Cannot add out of bounds!", "Invalid command", JOptionPane.ERROR_MESSAGE); return; }     if (index < 0) { JOptionPane.showMessageDialog(null, "Cannot add out of bounds!", "Invalid command", JOptionPane.ERROR_MESSAGE); return; }   if (head==null) { addFirst(data); return; }   if (index == size) { addLast(data); return; }   //step 1 Node<T> current;   current = head;   for (i=0;i<index-1;i++) { current = current.getNext(); }   //current now refers to object immediately before new node   //step 2 Node<T> newnode = new Node<T>(data,current.getNext(), current.getPrevious());   //step 3   current.setNext(newnode);     size++; }   /* * remove(int index) * parameters index * index- the index of the data to remove * removes the data at the specified index */ public void remove(int index) { if ((index<0) || (index>=size)) { JOptionPane.showMessageDialog(null, "You cannot remove an out-of-bounds value!", "Invalid removal", JOptionPane.ERROR_MESSAGE); return; }       Node <T> next2, previous3; Node<T> NodeToRemove = head; // sets Node to remove originally to head     for (int v = 0; v < index; v++) { NodeToRemove = NodeToRemove.getNext(); // traverse to Node we want to remove }   previous3 = NodeToRemove.getPrevious(); // sets previous3 to value before Node to remove next2 = NodeToRemove.getNext(); // sets next2 to value after Node to remove   // if the value before the Node we want to remove is null, it probably means that the Node to be removed is the head. (Either that or some goof set it to null and added it anyway to the list.) if (previous3 == null) { // if the next one is also null, it means that this Node is you're only Node so it clears the whole list if (next2 == null) { head = null; tail = null; } // otherwise it sets the head to the value after the removed Node else { head = next2; } } // otherwise it just sets the next2 to be the Node right after previous3 else { previous3.setNext(next2); }   if (next2 == null) { if (previous3 == null) { head = null; tail = null; }   else { tail = previous3; } } else { next2.setPrevious(previous3); }     size--; }   /* * get(int i) * parametsrs i * i - the index * returns the data at index i */ public T get(int i) { if (i < 0 || i >= size) return null;   if (i ==0) { Node<T> thisNode = head; return(head.getData()); }   if (i == size - 1) { Node<T> thisNode = tail; return(tail.getData()); } Node<T> specialNode = head; for (int x = 1; x < i + 1; x++) { specialNode = specialNode.getNext(); } return(specialNode.getData());   // How do I get it to return the data at i?     }   public Node<T> getNodeAt(int index) { Node<T> temp5 = head; for (int i =0; i < index; i++) { temp5 = temp5.getNext(); } return temp5; } /* * getSubList(int from, int to) * parameters from, to * from - the starting index * to - the ending index * gets the data from index from to index to and copies it into another DoublyLinkedList * and returns that DoublyLinkedList */ public DoublyLinkedList<T> getSubList(int from, int to) { DoublyLinkedList<T> sub = new DoublyLinkedList<T>(); int count = 0; for (int value = from; value <=to; value++) { sub.add(count, this.get(value)); count++; } return sub; }   /* * swap(int first, int second) * parameters first, second * first - the index of the first value to be swapped * second - the index of the second value to be swapped * swaps the data at index first and index second * Not yet written */ public void swap(int first, int second) { if (first < 0 || first >=Size() || second < 0 || second >=Size()) return;   // no use bothering to swap an index with itself if (first == second) return; Node<T> prevTemp; Node<T> prevTemp2; Node<T> nextTemp; Node<T> nextTemp2;     prevTemp = getNodeAt(first).getPrevious(); prevTemp2 = getNodeAt(second).getPrevious(); nextTemp = getNodeAt(first).getNext(); nextTemp2 = getNodeAt(second).getNext(); getNodeAt(first).setPrevious(prevTemp2); getNodeAt(first).setNext(nextTemp2); getNodeAt(second).setPrevious(prevTemp); getNodeAt(second).setNext(nextTemp);   }   /* * getIndex(T data) * parameters data * data - the data to look for * if it finds the data, it returns the index where it finds it * otherwise it returns -1 if it cannot find it */ public int getIndex(T data) { for (int x =0; x < Size(); x++) { if (this.get(x).equals(data)) return x; } return -1; } // calls get method of first index   /* * returns the data at the beginning of the DoublyLinkedList */ public T front() { if (head == null) return null;   return(get(0)); }   // calls get Method of last index /* * returns the data at the end of the DoublyLinkedList */ public T back() { if (tail == null) return null;   return(get(size - 1)); }   /* * removes the data at the end of the DoublyLinkedList */ public void removeLast() {   if (head == null) { JOptionPane.showMessageDialog(null, "Cannot remove from an empty list!", "Invalid removal", JOptionPane.ERROR_MESSAGE); return; } remove(Size() -1 ); }   // gets a String for the first bracket. Then stores each set of first and last, 2nd and 2nd to last, etc, in a String array; // it then sets the third string to the concatination of all of the Strings in the array. It thens puts these together and adds // the last set of brackets and returns the final string. public String printAlternate() { /* This method returns a string that has the data in the following fashion (assume for this example that the list stores String objects) If the list is currently [amit is now here], it will return a string �[amit here is now]� If the list is currently [amit is now currently here], it will return a string �[amit here is currently now]� */ String str = "["; String [] str2 = new String[size]; for (int v = 0; v < size; v++) { str2[v] = this.get(v) + " " + this.get(size - (v+1) ); } String str3 = ""; for (int x = 0; x < size - 2; x++) { str3 = str2[x].concat(str2[x+1]); } String str4 = str + " " + str3 + " " + "]"; return(str4); }   // removes all data /* * removes all data in the DoublyLinkedList */ public void removeAll() { int x = 0; int y = this.Size() - 1;   removeRange(x,y); } /* * copies the data from this DoublyLinkedList into another one and returns that * DoublyLinkedList * @see java.lang.Object#clone() */ public DoublyLinkedList<T> clone() { DoublyLinkedList<T> copy = new DoublyLinkedList<T>(); for (int x = 0; x < this.Size(); x++) { copy.add(x, this.get(x)); } return copy; }   public void addMyCollection(MyCollection<T> aCollection) { for (int i =0; i < aCollection.Size(); i++) { addLast(aCollection.get(i)); }   }   public DoublyLinkedList<T> getSubList2(MyCollection<T> collection, int from, int to) {   DoublyLinkedList<T> sub = new DoublyLinkedList<T>(); int count = 0; for (int value = from; value <=to; value++) { sub.add(count, collection.get(value)); count++; } return sub; }             public DoublyLinkedList<T> getSubList4(Vector<T> aVector, int from, int to) { DoublyLinkedList<T> sub = new DoublyLinkedList<T>(); int count = 0;   for (int i = from; i <= to; i++) { sub.add(count, aVector.get(i)); count++; } return sub; } public DoublyLinkedList ( DoublyLinkedList<T>original) { copiedDLL = original.clone(); this.copiedDLL = copiedDLL;   }         public DoublyLinkedList ( MyCollection<T> collection, int from, int to) { anotherOne = getSubList2(collection, from, to); this.anotherOne = anotherOne; }       public Object[] toArray() { Object[] obj = new Object[this.Size()]; for (int i =0 ; i < this.Size(); i++) { obj[i] = this.get(i); } return obj; }   public void addCloneAt(int index, int indexToClone) { if (index < 0 || index >Size()) return; if (indexToClone <0 || indexToClone >=Size()) return; add(get(indexToClone), index);   } }```