Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 2 of 2

Thread: Linked List Help

  1. #1
    Junior Member
    Join Date
    Feb 2011
    Posts
    5
    Thanks
    3
    Thanked 0 Times in 0 Posts

    Default Linked List Help

    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!!!!

    public class LinkedListOfDoubles
    {
    private DoubleNode head;
    private DoubleNode tail;
    private int size;
    public static final double NaN;
    public LinkedListOfDoubles()
    {
    this.head = null;
    this.tail = null;
    this.size = 0;
    }

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

    newNode.setNext(head);
    head = newNode;
    tail = head;
    size++;
    }else{
    DoubleNode newNode;
    newNode = new DoubleNode(d);

    newNode.setNext(head);
    head = newNode;
    size++;
    }
    }

    public void addBack(double d)
    {
    if(head == null){
    DoubleNode newNode;
    newNode = new DoubleNode(d);
    newNode.setNext(head);
    size++;
    tail = head.next();
    }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;
    }

    }


  2. #2
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default 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.

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


    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);
     
    }
    }
    Last edited by javapenguin; February 5th, 2011 at 12:14 AM.

  3. The Following User Says Thank You to javapenguin For This Useful Post:

    lieles (February 5th, 2011)

Similar Threads

  1. Having trouble with linked list
    By joecool594 in forum Collections and Generics
    Replies: 6
    Last Post: March 21st, 2011, 08:50 PM
  2. Linked List problem, please help.
    By Axeander in forum What's Wrong With My Code?
    Replies: 10
    Last Post: December 21st, 2010, 05:01 PM
  3. Help with linked list
    By joecool594 in forum Collections and Generics
    Replies: 3
    Last Post: November 28th, 2010, 12:33 PM
  4. Simple linked list
    By Koren3 in forum Collections and Generics
    Replies: 10
    Last Post: November 2nd, 2009, 03:33 AM
  5. Recursive function based on Linked list
    By rosh72851 in forum Collections and Generics
    Replies: 1
    Last Post: March 9th, 2009, 06:23 PM