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 24 of 24

Thread: Generic Doubly Linked List

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

    Talking Generic Doubly Linked List

    I need to create a DoublyLinkedList class

    import javax.swing.JOptionPane;
    import java.util.*;
    import java.io.*;
     
    public class DoublyLinkedList<T> 
    {
    	private class Node<T>
    	{
    		private T data;
    		private Node<T> next;
                   private Node<T> previous;
     
    		public Node(T data,Node<T> next, Node<T> previous)
    		{
    			this.data = data;
    			this.next = next;
                           this.previous=previous;
    		}
     
    		public T getData()
    		{
    			return data;
    		}
     
    		public Node<T> getNext()
    		{
    			return next;
    		}
     
    public Node<T> getPrevious()
    {
    return previous;
    }
     
    		public void setNext(Node<T> next)
    		{
    			this.next = next;
    		}		
     
    public void setPrevious(Node<T> previous)
    {
    this.previous = previous;
    }
    	}
     
    	private Node<T> head;//head of the linked list
           private Node<T> tail; // tail of linked list
    	private int size;
     
    	public DoublyLinkedList()
    	{
    		head = null;
                    tail = null;
    		size = 0;
    	}
     
    	public String toString()
    	{
    		String str = "[";
     
    		Node<T> curr;
     
    		for (curr=head;curr!=null;curr = curr.getNext())
    		{
    			str = str + curr.getData();
    			if (curr.getNext()!=null)
    				str = str + " ";
    		}
    		str = str + "]";
    		return str;
     
    // can this stay the same?  I did copy some of this from the SinglyLinkedList code we got in class.  I don't know exactly how to edit it to make it a DoublyLinkedList.
    // i.e. a list that refers to two things, next and previous, rather than just next.  It makes adding something at the end or close to the end more efficient than a SinglyLinkedList.  
    	}
     
    	public void addFirst(T data)
    	{
    		Node<T> newnode = new Node<T>(data,head);
     
    		head = newnode;
     
    		size++;
    	}
     
    	public void removeFirst()
    	{
               if (size == 0)
    {
    JOptionPane.showMessageDialog(null, "Cannot remove from an empty list!", "Invalid removal", JOptionPane.ERROR_MESSAGE);
    return;
    }
    		Node<T> current = head;
     
    		head = head.getNext(); //move head to the next element
    		current.setNext(null);
    	}
     
    	public void addLast(T data)
    	{
    		Node<T> current;
     
    		if (head==null)
    		{
    			addFirst(data);
    			return;
    		}
     
    		current = head;
     
    		while (current.getNext()!=null)
    			current = current.getNext();
     
    		Node<T> newnode = new Node<T>(data,null);
     
    		current.setNext(newnode);
    		size++;
     
    	}
     
    	public void add(int index,T data)
    	{
    		int i;
     
    		if (index>size)
    			return;
     
    		if (head==null)
    		{
    			addFirst(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());
     
    		//step 3
     
    		current.setNext(newnode);
    		size++;
    	}	
     
    	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> current,previous2;
     
    		current = head;
    		previous2 = null;
     
    		for (int i=0;i<index;i++)
    		{
    			previous2 = current;
    			current = current.getNext();
    		}
     
    		if (index!=0)
    			previous2.setNext(current.getNext());
    		else
    		{
    			head = head.getNext();
    		}
    		size--;
    	}
     
    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]”
    */
    }
    }

     import javax.swing.JOptionPane;
    import java.io.*
    import java.util.*
    public class SortedDoublyLinkedList<T> extends Comparable
    {
     
    private DoublyLinkedList<String> list;
     
    // it need not be String, just a type that implements Comparable
     
    // how do I write similar codes for this one if I can't access Node as it's private and he told me it should stay private.  
    public SortedDoublyLinkedList() 
    {
    list = new DoublyLinkedList<String>(); 
    }
     
    public String toString()
    {
    // works like the toString() method for DoublyLinkedList should, probably not how it currently [B]does[/B]
    }
     
    public void add(T data)
    {
    /*
    This method adds the data to the list so that the list is
    maintained in “increasing order”. For example, if the existing list is [amit here is now] and you
    are trying to add the string “me”, the list will become [amit here is me now].
    */
    }
     
    public void removeFirst()
    {
     
    }
     
    public void removeLast()
    {
     
    }
     
     
    }


    Assignment 4: Sorted and Unsorted Doubly Linked Lists
    Out: 5th October 2010 Type: Medium Due: 12th October 2010 (Tue) at 11:59pm
    Note: You can use Eclipse for this assignment if you wish.
    In this assignment you will create a generic class that represents a doubly linked list. You will write several
    methods for this class. Lastly you will use this class to create a doubly linked list that arranges the data within it
    in a sorted order.
    Proceed as follows:
    1. Create a generic class DoublyLinkedList by suitably modifying the SinglyLinkedList class developed during
    lectures. This class should keep track of only the head and the tail of the linked list, along with its current
    size. Define an inner class Node that stores data and two references: Node objects that are “previous”
    and “next” to this node in the list.
    2. Write the following methods for it:
    a. Constructor with no parameters.
    b. addFirst(T data): Adds a new node that contains the passed data to the beginning of the
    list.
    c. addLast(T data): Adds a new node that contains the passed data to the end of the list.
    d. add(int i, T data): Adds a new node so that in the new list, it is at index “i”, if “i’ makes
    sense.
    e. remove(int i): Removes the node that is currently at index “i”, if one exists.
    f. T get(int i): Returns the data at index “i”, if the index is valid.
    g. size(): Returns the current size of the list
    h. T front(): Returns the data from the node at the beginning of the list.
    i. T back(): Returns the data from the node at the end of the list.
    j. toString(): Returns a string that has the data printed in the order that it is stored in the list.
    3. Write a new method 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]”
    4. Create a generic class SortedDoublyLinkedList. This class internally uses the DoublyLinkedList class to
    represent a list that has been arranged in “increasing order” of its data. To determine “increasing
    order”, this class uses the compareTo method. That is, this new list can only store objects for which the
    compareTo method has been defined.
    a. Write a method add(T data). This method adds the data to the list so that the list is
    maintained in “increasing order”. For example, if the existing list is [amit here is now] and you
    are trying to add the string “me”, the list will become [amit here is me now].
    b. Write a method removeFirst() that removes the first element in the list. (Hint: this works
    the same way as the DoublyLinkedList’s removeFirst().)
    c. Write a method removeLast() that removes the last element in the list. (Hint: this works the
    same way as the DoublyLinkedList’s removeLast().)
    The SortedDoublyLinkedList class should have only four public methods: add, removeFirst,
    removeLast and toString.
    Last edited by javapenguin; October 11th, 2010 at 03:30 PM.


  2. #2
    Forum VIP
    Join Date
    Jul 2010
    Posts
    1,707
    Thanks
    25
    Thanked 338 Times in 313 Posts

    Default Re: Generic Doubly Linked List

    So, whats wrong?
    NOTE TO NEW PEOPLE LOOKING FOR HELP ON FORUM:

    When asking for help, please follow these guidelines to receive better and more prompt help:
    1. Put your code in Java Tags. To do this, put [highlight=java] before your code and [/highlight] after your code.
    2. Give full details of errors and provide us with as much information about the situation as possible.
    3. Give us an example of what the output should look like when done correctly.

    Join the Airline Management Simulation Game to manage your own airline against other users in a virtual recreation of the United States Airline Industry. For more details, visit: http://airlinegame.orgfree.com/

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

    javapenguin (October 11th, 2010)

  4. #3
    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: Generic Doubly Linked List

    Quote Originally Posted by aussiemcgr View Post
    So, whats wrong?
    First off, how to fix the Node constructor now for each time I make a new Node.

    This code was changed from a SinglyLinkedList code:

    public class SinglyLinkedList<T> 
    {
    	private class Node<T>
    	{
    		private T data;
    		private Node<T> next;
     
    		public Node(T data,Node<T> next)
    		{
    			this.data = data;
    			this.next = next;
    		}
     
    		public T getData()
    		{
    			return data;
    		}
     
    		public Node<T> getNext()
    		{
    			return next;
    		}
     
    		public void setNext(Node<T> next)
    		{
    			this.next = next;
    		}		
    	}
     
    	private Node<T> head;//head of the linked list
    	private int size;
     
    	public SinglyLinkedList()
    	{
    		head = null;
    		size = 0;
    	}
     
    	public String toString()
    	{
    		String str = "[";
     
    		Node<T> curr;
     
    		for (curr=head;curr!=null;curr = curr.getNext())
    		{
    			str = str + curr.getData();
    			if (curr.getNext()!=null)
    				str = str + " ";
    		}
    		str = str + "]";
    		return str;
    	}
     
    	public void addFirst(T data)
    	{
    		Node<T> newnode = new Node<T>(data,head);
     
    		head = newnode;
    		size++;
    	}
     
    	public void removeFirst()
    	{
    		Node<T> current = head;
     
    		head = head.getNext(); //move head to the next element
    		current.setNext(null);
    	}
     
    	public void addLast(T data)
    	{
    		Node<T> current;
     
    		if (head==null)
    		{
    			addFirst(data);
    			return;
    		}
     
    		current = head;
     
    		while (current.getNext()!=null)
    			current = current.getNext();
     
    		Node<T> newnode = new Node<T>(data,null);
     
    		current.setNext(newnode);
    		size++;
     
    	}
     
    	public void add(int index,T data)
    	{
    		int i;
     
    		if (index>size)
    			return;
     
    		if (head==null)
    		{
    			addFirst(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());
     
    		//step 3
     
    		current.setNext(newnode);
    		size++;
    	}	
     
    	public void remove(int index)
    	{
    		if ((index<0) || (index>=size))
    			return;
     
    		Node<T> current,previous;
     
    		current = head;
    		previous = null;
     
    		for (int i=0;i<index;i++)
    		{
    			previous = current;
    			current = current.getNext();
    		}
     
    		if (index!=0)
    			previous.setNext(current.getNext());
    		else
    		{
    			head = head.getNext();
    		}
    		size--;
    	}
    }

  5. #4
    Forum VIP
    Join Date
    Jul 2010
    Posts
    1,707
    Thanks
    25
    Thanked 338 Times in 313 Posts

    Default Re: Generic Doubly Linked List

    1. Create a generic class DoublyLinkedList by suitably modifying the SinglyLinkedList class developed during
    lectures.
    Doesn't that mean that since Node is created in SinglyLinkedList, that you can copy and paste that code into DoublyLinkedList. Grabbing all of the code from SinglyLinkedList and modifying it seems to be what he wants from you.
    NOTE TO NEW PEOPLE LOOKING FOR HELP ON FORUM:

    When asking for help, please follow these guidelines to receive better and more prompt help:
    1. Put your code in Java Tags. To do this, put [highlight=java] before your code and [/highlight] after your code.
    2. Give full details of errors and provide us with as much information about the situation as possible.
    3. Give us an example of what the output should look like when done correctly.

    Join the Airline Management Simulation Game to manage your own airline against other users in a virtual recreation of the United States Airline Industry. For more details, visit: http://airlinegame.orgfree.com/

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

    Smile Re: Generic Doubly Linked List

    Quote Originally Posted by aussiemcgr View Post
    Doesn't that mean that since Node is created in SinglyLinkedList, that you can copy and paste that code into DoublyLinkedList. Grabbing all of the code from SinglyLinkedList and modifying it seems to be what he wants from you.
    Yes, but for one, how do you modify the constructor to get it to work now with tail? tail could be null, or it could be head if size =1, or it could be anything else.

    My constructor is what's really going wrong right now.

    Every time I make a new Node, I need to pass it tail as well, but how do I tell it which value of tail to put for the methods?

    Do I have to have cases where tail would be null, where there is only one element[hence tail = head], or any other case?

     if (tail ==null)
    {
    // something, usually an error message
    }
     
    if (size == 1)
    {
    // whatever operation is needed, like setting size to 0 if remove, setting head to new value if addFirst() and setting tail to one after old head value
    }

    I want to edit this part:

    public void addLast(T data)
        {
            Node<T> current;
     
        /*    if (head==null)
            {
                addFirst(data);
                return;
            }
     
            current = head; */
     
    // I want to do something like this instead of current = head; and the rest.
     
    current = tail;
    if (tail == null)
    {
    addFirst(data);
    return;
    }
     
    tail = current.next; // puts tail at position of new value, but I think I'm forgetting something
     
     
     
          /*  while (current.getNext()!=null)
                current = current.getNext();
     
            Node<T> newnode = new Node<T>(data,null); // need to fix or remove this
     
            current.setNext(newnode); */
            size++;
     
        }
    Last edited by javapenguin; October 11th, 2010 at 04:16 PM.

  7. #6
    Forum VIP
    Join Date
    Jul 2010
    Posts
    1,707
    Thanks
    25
    Thanked 338 Times in 313 Posts

    Default Re: Generic Doubly Linked List

    Ok, so is this LinkedList a cirlce. By that I mean: Is the next node for the last node the first node and visa versa?

    If so, when you construct your first node, its head and tail are equal to itself. If you add another node, you need to change the first node's tail and head to the new node, and the new node's tail and head needs to be equal to the first node. Then when you add a third, the last node's head is equal to the first node, the second node's head is equal to the last node, and the first node's tail is equal to the last node.

    If it is just a straight line effectively, you will know the first node's tail will always be null and the last node's head will always be null. So when you add a new node, you just go through the DoublyLinkedList until a Node's head is equal to null (which indicates it is last), then set that node's head to your new node, your new node's tail to the previously last node, and your new node's head to null (indicating it is last).
    NOTE TO NEW PEOPLE LOOKING FOR HELP ON FORUM:

    When asking for help, please follow these guidelines to receive better and more prompt help:
    1. Put your code in Java Tags. To do this, put [highlight=java] before your code and [/highlight] after your code.
    2. Give full details of errors and provide us with as much information about the situation as possible.
    3. Give us an example of what the output should look like when done correctly.

    Join the Airline Management Simulation Game to manage your own airline against other users in a virtual recreation of the United States Airline Industry. For more details, visit: http://airlinegame.orgfree.com/

  8. The Following User Says Thank You to aussiemcgr For This Useful Post:

    javapenguin (October 11th, 2010)

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

    Post Re: Generic Doubly Linked List

    Quote Originally Posted by aussiemcgr View Post
    Ok, so is this LinkedList a cirlce. By that I mean: Is the next node for the last node the first node and visa versa?

    If so, when you construct your first node, its head and tail are equal to itself. If you add another node, you need to change the first node's tail and head to the new node, and the new node's tail and head needs to be equal to the first node. Then when you add a third, the last node's head is equal to the first node, the second node's head is equal to the last node, and the first node's tail is equal to the last node.

    If it is just a straight line effectively, you will know the first node's tail will always be null and the last node's head will always be null. So when you add a new node, you just go through the DoublyLinkedList until a Node's head is equal to null (which indicates it is last), then set that node's head to your new node, your new node's tail to the previously last node, and your new node's head to null (indicating it is last).
    No, it's not a circular list.

    package Assignment4;
     
    import javax.swing.JOptionPane;
    import java.util.*;
    import java.io.*;
     
    public class DoublyLinkedList<T>
    {
        private class Node<T>
        {
            private T data;
            private Node<T> next;
                   private Node<T> previous;
     
            public Node(T data,Node<T> next, Node<T> previous)
            {
                this.data = data;
                this.next = next;
                           this.previous=previous;
            }
     
            public T getData()
            {
                return data;
            }
     
            public Node<T> getNext()
            {
                return next;
            }
     
    public Node<T> getPrevious()
    {
    return previous;
    }
     
            public void setNext(Node<T> next)
            {
                this.next = next;
            }      
     
    public void setPrevious(Node<T> previous)
    {
    this.previous = previous;
    }
        }
     
        private Node<T> head;//head of the linked list
           private Node<T> tail; // tail of linked list
        private int size;
     
        public DoublyLinkedList()
        {
            head = null;
                    tail = null;
            size = 0;
        }
     
        public String toString()
        {
            String str = "[";
     
            Node<T> curr;
     
            for (curr=head;curr!=null;curr = curr.getNext())
            {
                str = str + curr.getData();
                if (curr.getNext()!=null)
                    str = str + " ";
            }
            str = str + "]";
            return str;
     
    // can this stay the same?  I did copy some of this from the SinglyLinkedList code we got in class.  I don't know exactly how to edit it to make it a DoublyLinkedList.
    // i.e. a list that refers to two things, next and previous, rather than just next.  It makes adding something at the end or close to the end more efficient than a SinglyLinkedList.  
        }
     
        public void addFirst(T data)
        {
            Node<T> newnode = new Node<T>(data,head);
     
            head = newnode;
     
            size++;
        }
     
        public void removeFirst()
        {
               if (size == 0)
    {
    JOptionPane.showMessageDialog(null, "Cannot remove from an empty list!", "Invalid removal", JOptionPane.ERROR_MESSAGE);
    return;
    }
            Node<T> current = head;
     
            head = head.getNext(); //move head to the next element
            current.setNext(null);
        }
     
        public void addLast(T data)
        {
            Node<T> current;
     
           /* if (head==null)
            {
                addFirst(data);
                return;
            }
     
            current = head;
     
            while (current.getNext()!=null)
                current = current.getNext();
     
            Node<T> newnode = new Node<T>(data,null);
     
            current.setNext(newnode);*/
            current = tail;
            if (tail == null)
            {
            	addFirst(data);
            	return;
            }
     
            tail = current.next;
            current.setNext(tail);
            size++;
     
        }
     
        public void add(int index,T data)
        {
            int i;
     
            if (index>size)
                return;
     
            if (head==null)
            {
                addFirst(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());
     
            //step 3
     
            current.setNext(newnode);
            size++;
        }  
     
        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> current,previous2;
     
            current = head;
            previous2 = null;
     
            for (int i=0;i<index;i++)
            {
                previous2 = current;
                current = current.getNext();
            }
     
            if (index!=0)
                previous2.setNext(current.getNext());
            else
            {
                head = head.getNext();
            }
            size--;
        }
     
        public T get(int i)
        {
        	if (i < 0 || i >=size)
    return null;
     
    // How do I get it to return the data at i?  
        }
        public T front()
        {
        	if (head == null)
        		return null;
     
        	return(get(0));
        }
     
        public T back()
        {
        	if (tail == null)
        		return null;
     
        	return(get(size - 1));
        }
    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]”
    */
    }
    }
    Last edited by javapenguin; October 11th, 2010 at 04:36 PM.

  10. #8
    Forum VIP
    Join Date
    Jul 2010
    Posts
    1,707
    Thanks
    25
    Thanked 338 Times in 313 Posts

    Default Re: Generic Doubly Linked List

    Ok, so your here is what I get from your code:
    Constructor - seems fine
    toString - up to you
    addFirst - You should create a Node<T> by sending it data,head,and null. You then have to also remember to set the old head's tail to the new head.
    removeFirst - You need to remember to set the second element's tail to null, as it will now be the first element.

    Tackle those before we move on. If you understand what you need to change, you may be able to fix the other methods on your own.
    Last edited by aussiemcgr; October 11th, 2010 at 05:10 PM.
    NOTE TO NEW PEOPLE LOOKING FOR HELP ON FORUM:

    When asking for help, please follow these guidelines to receive better and more prompt help:
    1. Put your code in Java Tags. To do this, put [highlight=java] before your code and [/highlight] after your code.
    2. Give full details of errors and provide us with as much information about the situation as possible.
    3. Give us an example of what the output should look like when done correctly.

    Join the Airline Management Simulation Game to manage your own airline against other users in a virtual recreation of the United States Airline Industry. For more details, visit: http://airlinegame.orgfree.com/

  11. The Following User Says Thank You to aussiemcgr For This Useful Post:

    javapenguin (October 11th, 2010)

  12. #9
    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: Generic Doubly Linked List

    Quote Originally Posted by aussiemcgr View Post
    Ok, so your here is what I get from your code:
    Constructor - seems fine
    toString - up to you
    addFirst - You should create a Node<T> by sending it data,head,and null. You then have to also remember to set the old head's tail to the new head.
    removeFirst - You need to remember to set the second element's tail to null

    Tackle those before we move on. If you understand what you need to change, you may be able to fix the other methods on your own.
    is my addLast() method doing this:

    1.) creating a Node current and setting it to tail

    2.) setting the tail to the value after current;

    3.) setting the old tail to the new tail.previous

    if not, how would it do that?

    Again, I don't have a circular list, i.e., tail.next != head and head.previous != tail.

  13. #10
    Forum VIP
    Join Date
    Jul 2010
    Posts
    1,707
    Thanks
    25
    Thanked 338 Times in 313 Posts

    Default Re: Generic Doubly Linked List

    Ok, so for addLast you know that your new node will have a head of null and a tail of the previous last node. You also know that the previous last node's head will have to be set to your new node. Lastly, make sure you set the tail node to be the new last or all hell will break lose.

    By attaching the pointers prior to setting the new node to tail you avoid all that garbage of finding the previous tail and stuff. For that reason, I would probably do your step #1 last. It is stylistic, but I think setting the pointers first is both easier and probably makes it faster.
    NOTE TO NEW PEOPLE LOOKING FOR HELP ON FORUM:

    When asking for help, please follow these guidelines to receive better and more prompt help:
    1. Put your code in Java Tags. To do this, put [highlight=java] before your code and [/highlight] after your code.
    2. Give full details of errors and provide us with as much information about the situation as possible.
    3. Give us an example of what the output should look like when done correctly.

    Join the Airline Management Simulation Game to manage your own airline against other users in a virtual recreation of the United States Airline Industry. For more details, visit: http://airlinegame.orgfree.com/

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

    Question Re: Generic Doubly Linked List

    Quote Originally Posted by aussiemcgr View Post
    Ok, so for addLast you know that your new node will have a head of null and a tail of the previous last node. You also know that the previous last node's head will have to be set to your new node. Lastly, make sure you set the tail node to be the new last or all hell will break lose.

    By attaching the pointers prior to setting the new node to tail you avoid all that garbage of finding the previous tail and stuff. For that reason, I would probably do your step #1 last. It is stylistic, but I think setting the pointers first is both easier and probably makes it faster.


    I thought head was the first Node in the list and tail was the last Node in the list. Was I wrong?

    In a list of size 5, head would certainly not be null. Unless I'm mistaken about what head and tail are, that is.

    in addLast, I have:

     public void addLast(T data)
        {
            Node<T> current;
     
           /* if (head==null)
            {
                addFirst(data);
                return;
            }
     
            current = head;
     
            while (current.getNext()!=null)
                current = current.getNext();
     
            Node<T> newnode = new Node<T>(data,null);
     
            current.setNext(newnode);*/
            current = tail;
            if (tail == null)
            {
            	addFirst(data);
            	return;
            }
     
            tail = current.next;
            current.setNext(tail);
            size++;
     
        }

    right now.



    all that stuff including newnode and the while loop have been commented out as I found that I don't need to go from head and move to the last spot to get to the end and then reset it., which was what that loop and stuff was doing. I can just use the value tail and work from there. Hence the reason it's DoublyLinkedList.

    I want the current tail to be set to the previous of the new tail:
    Node <T> current;
     
    current = tail;
     
    tail = current.next;  // makes new tail now have well, makes it go after in the index where the original value of tail was
     
    tail.setPrevious(current); // puts the old tail value before the new tail
    Will that work, or will something go wrong?
    Last edited by javapenguin; October 11th, 2010 at 05:32 PM. Reason: Confused

  15. #12
    Forum VIP
    Join Date
    Jul 2010
    Posts
    1,707
    Thanks
    25
    Thanked 338 Times in 313 Posts

    Default Re: Generic Doubly Linked List

    Oh, sorry, I was using the wrong terminology. I was using head and tail when I meant next and previous. This post:
    Ok, so for addLast you know that your new node will have a head of null and a tail of the previous last node. You also know that the previous last node's head will have to be set to your new node. Lastly, make sure you set the tail node to be the new last or all hell will break lose.

    By attaching the pointers prior to setting the new node to tail you avoid all that garbage of finding the previous tail and stuff. For that reason, I would probably do your step #1 last. It is stylistic, but I think setting the pointers first is both easier and probably makes it faster.
    Should be:
    Ok, so for addLast you know that your new node will have a next of null and a previous of the previous last node. You also know that the previous last node's next will have to be set to your new node. Lastly, make sure you set the tail node to be the new last or all hell will break lose.

    By attaching the pointers prior to setting the new node to tail you avoid all that garbage of finding the previous tail and stuff. For that reason, I would probably do your step #1 last. It is stylistic, but I think setting the pointers first is both easier and probably makes it faster.
    NOTE TO NEW PEOPLE LOOKING FOR HELP ON FORUM:

    When asking for help, please follow these guidelines to receive better and more prompt help:
    1. Put your code in Java Tags. To do this, put [highlight=java] before your code and [/highlight] after your code.
    2. Give full details of errors and provide us with as much information about the situation as possible.
    3. Give us an example of what the output should look like when done correctly.

    Join the Airline Management Simulation Game to manage your own airline against other users in a virtual recreation of the United States Airline Industry. For more details, visit: http://airlinegame.orgfree.com/

  16. The Following User Says Thank You to aussiemcgr For This Useful Post:

    javapenguin (October 11th, 2010)

  17. #13
    Forum VIP
    Join Date
    Jul 2010
    Posts
    1,707
    Thanks
    25
    Thanked 338 Times in 313 Posts

    Default Re: Generic Doubly Linked List

    I would change this code (removed commented out sections):
    public void addLast(T data)
    {
    	Node<T> current;
     
            current = tail;
            if (tail == null)
            {
                addFirst(data);
                return;
            }
     
            tail = current.next;
            current.setNext(tail);
            size++;
     
    }

    to be:
    public void addLast(T data)
    {
    	if (tail == null)
            {
                addFirst(data);
                return;
            }
    	Node<T> newNode = new Node(data,null,tail);
    	tail.setNext(newNode);
    	tail = newNode;
            size++;
    }

    Nice and simple. You see, by setting the pointers first, we don't have to have a current variable and we can avoid that worry. Should work, but I haven't tried it.
    NOTE TO NEW PEOPLE LOOKING FOR HELP ON FORUM:

    When asking for help, please follow these guidelines to receive better and more prompt help:
    1. Put your code in Java Tags. To do this, put [highlight=java] before your code and [/highlight] after your code.
    2. Give full details of errors and provide us with as much information about the situation as possible.
    3. Give us an example of what the output should look like when done correctly.

    Join the Airline Management Simulation Game to manage your own airline against other users in a virtual recreation of the United States Airline Industry. For more details, visit: http://airlinegame.orgfree.com/

  18. The Following User Says Thank You to aussiemcgr For This Useful Post:

    javapenguin (October 11th, 2010)

  19. #14
    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: Generic Doubly Linked List

    Quote Originally Posted by aussiemcgr View Post
    I would change this code (removed commented out sections):
    public void addLast(T data)
    {
    	Node<T> current;
     
            current = tail;
            if (tail == null)
            {
                addFirst(data);
                return;
            }
     
            tail = current.next;
            current.setNext(tail);
            size++;
     
    }

    to be:
    public void addLast(T data)
    {
    	if (tail == null)
            {
                addFirst(data);
                return;
            }
    	Node<T> newNode = new Node(data,null,tail);
    	tail.setNext(newNode);
    	tail = newNode;
            size++;
    }

    Nice and simple. You see, by setting the pointers first, we don't have to have a current variable and we can avoid that worry. Should work, but I haven't tried it.
    Ok, but what does:

      public void addLast(T data)
        {
            Node<T> current;
     
     
            current = tail;
            if (tail == null)
            {
            	addFirst(data);
            	return;
            }
     
            tail = current.next; // should set the new tail to be the value after new tail.  wait, that value doesn't exist, but what happens? 
            tail.setPrevious(current); // should set the old tail to be before the new tail.
            size++;
     
        }

    do?

    Ok, maybe yours will work, while mine might throw a NullPointerException. However, why does the head have to be null?
    Last edited by javapenguin; October 11th, 2010 at 05:51 PM.

  20. #15
    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: Generic Doubly Linked List

    Quote Originally Posted by aussiemcgr View Post
    I would change this code (removed commented out sections):
    public void addLast(T data)
    {
    	Node<T> current;
     
            current = tail;
            if (tail == null)
            {
                addFirst(data);
                return;
            }
     
            tail = current.next;
            current.setNext(tail);
            size++;
     
    }

    to be:
    public void addLast(T data)
    {
    	if (tail == null)
            {
                addFirst(data);
                return;
            }
    	Node<T> newNode = new Node(data,null,tail);
    	tail.setNext(newNode);
    	tail = newNode;
            size++;
    }

    Nice and simple. You see, by setting the pointers first, we don't have to have a current variable and we can avoid that worry. Should work, but I haven't tried it.
    Thanks. However, what will it do with the value that was originally the tail? Does it automatically set the previous value to be be the old tail.

    like this:

    oldtail = newnode.previous;

    Does it take care of it so I don't have to do that?

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

    Angry Re: Generic Doubly Linked List

    package Assignment4;
     
    import javax.swing.JOptionPane;
    import java.util.*;
    import java.io.*;
     
     
     
    public class DoublyLinkedList<T>
    {
        private class Node<T>
        {
            private T data;
            private Node<T> next;
                   private Node<T> previous;
     
            public Node(T data,Node<T> next, Node<T> previous)
            {
                this.data = data;
                this.next = next;
                           this.previous=previous;
            }
     
            public T getData()
            {
                return data;
            }
     
            public Node<T> getNext()
            {
                return next;
            }
     
    public Node<T> getPrevious()
    {
    return previous;
    }
     
            public void setNext(Node<T> next)
            {
                this.next = next;
            }      
     
    public void setPrevious(Node<T> previous)
    {
    this.previous = previous;
    }
        }
     
        private Node<T> head;//head of the linked list
           private Node<T> tail; // tail of linked list
        private int size;
     
        public DoublyLinkedList()
        {
            head = null;
                    tail = null;
            size = 0;
        }
     
        public String toString()
        {
            String str = "[";
     
            Node<T> curr;
     
            for (curr=head;curr!=null;curr = curr.getNext())
            {
                str = str + curr.getData();
                if (curr.getNext()!=null)
                    str = str + " ";
            }
            str = str + "]";
            return str;
     
    // can this stay the same?  I did copy some of this from the SinglyLinkedList code we got in class.  I don't know exactly how to edit it to make it a DoublyLinkedList.
    // i.e. a list that refers to two things, next and previous, rather than just next.  It makes adding something at the end or close to the end more efficient than a SinglyLinkedList.  
        }
     
        public void addFirst(T data)
        {
           // Node<T> newnode = new Node<T>(data,head);
         //  Node<T> newnode;
           // newnode = head;
          //  head = newnode.previous; // sets the head 
          //  newnode = head.next; // puts old head after new head
     
     
     
           // size++;
     
            Node<T> newNode = new Node<T>(data,head,null);
            head.setPrevious(newNode);
            head = newNode;
                size++;
        }
     
        public void removeFirst()
        {
               if (size == 0)
    {
    JOptionPane.showMessageDialog(null, "Cannot remove from an empty list!", "Invalid removal", JOptionPane.ERROR_MESSAGE);
    return;
    }
            Node<T> current = head;
     
            head = head.getNext(); //move head to the next element
            current.setNext(null);
        }
     
        public void addLast(T data)
        {
            if (tail == null)
                {
                    addFirst(data);
                    return;
                }
            Node<T> newNode = new Node<T>(data,null,tail);
            tail.setNext(newNode);
            tail = newNode;
                size++;
        }
     
        public void add(int index,T data)
        {
            int i;
     
            if (index>size)
                return;
     
            if (index < 0)
            	return;
     
            if (head==null)
            {
                addFirst(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());
     
            //step 3
     
            current.setNext(newnode);
            size++;
        }  
     
        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> current,previous2;
     
            current = head;
            previous2 = null;
     
            for (int i=0;i<index;i++)
            {
                previous2 = current;
                current = current.getNext();
            }
     
            if (index!=0)
                previous2.setNext(current.getNext());
            else
            {
                head = head.getNext();
            }
            size--;
        }
     
        public T get(int i)
        {
        	if (i < 0 || i >= size)
        		return null;
     
        	// How do I get it to return the data at i?
        }
        public T front()
        {
        	if (head == null)
        		return null;
     
        	return(get(0));
        }
     
        public T back()
        {
        	if (tail == null)
        		return null;
     
        	return(get(size - 1));
        }
    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]
    */
    }
    }

  22. #17
    Forum VIP
    Join Date
    Jul 2010
    Posts
    1,707
    Thanks
    25
    Thanked 338 Times in 313 Posts

    Default Re: Generic Doubly Linked List

    Quote Originally Posted by javapenguin View Post
    Thanks. However, what will it do with the value that was originally the tail? Does it automatically set the previous value to be be the old tail.

    like this:

    oldtail = newnode.previous;

    Does it take care of it so I don't have to do that?
    I'll comment the code for you, hopefully it will make more sense now:
    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(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++;
    }
    NOTE TO NEW PEOPLE LOOKING FOR HELP ON FORUM:

    When asking for help, please follow these guidelines to receive better and more prompt help:
    1. Put your code in Java Tags. To do this, put [highlight=java] before your code and [/highlight] after your code.
    2. Give full details of errors and provide us with as much information about the situation as possible.
    3. Give us an example of what the output should look like when done correctly.

    Join the Airline Management Simulation Game to manage your own airline against other users in a virtual recreation of the United States Airline Industry. For more details, visit: http://airlinegame.orgfree.com/

  23. The Following User Says Thank You to aussiemcgr For This Useful Post:

    javapenguin (October 11th, 2010)

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

    Exclamation Re: Generic Doubly Linked List

    Quote Originally Posted by aussiemcgr View Post
    I'll comment the code for you, hopefully it will make more sense now:
    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(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++;
    }
    Now my addFirst() is busted!


    What's wrong now?
     public void addFirst(T data)
        {
          //  Node<T> newnode = new Node<T>(data,head, null);
        // Node<T> newnode;
          //  newnode = head;
            //head = newnode.getPrevious(); // sets the head 
          // newnode = head.next; // puts old head after new head
     
     
     
           // size++;
            if (size == 0)
            {
            	Node<T> newNode = new Node<T>(data,head,tail);
            	head.setPrevious(newNode);
                head = newNode;
            }
           Node<T> newNode = new Node<T>(data,head,null);
            head.setPrevious(newNode);
            head = newNode;
     
            newNode = head;
            head = head.getNext();
     
     
     
                size++; 
        }

  25. #19
    Forum VIP
    Join Date
    Jul 2010
    Posts
    1,707
    Thanks
    25
    Thanked 338 Times in 313 Posts

    Default Re: Generic Doubly Linked List

    I fixed your code (I think) and commented so you would understand it. Tell me if this makes sense.
    public void addFirst(T data)
    {	
    	/* We can create the newNode variable now. If this is the first element,
    	 * the head will be set to null anyway, giving us the correct
    	 * value. Since this is the first Object, we know that 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, we want to set tail to be this Object
    		tail = newNode;
    	}
    	//We want to set head to be newNode
    	head = newNode;
    	//Increment Size
    	size++;
    }
    NOTE TO NEW PEOPLE LOOKING FOR HELP ON FORUM:

    When asking for help, please follow these guidelines to receive better and more prompt help:
    1. Put your code in Java Tags. To do this, put [highlight=java] before your code and [/highlight] after your code.
    2. Give full details of errors and provide us with as much information about the situation as possible.
    3. Give us an example of what the output should look like when done correctly.

    Join the Airline Management Simulation Game to manage your own airline against other users in a virtual recreation of the United States Airline Industry. For more details, visit: http://airlinegame.orgfree.com/

  26. The Following User Says Thank You to aussiemcgr For This Useful Post:

    javapenguin (October 11th, 2010)

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

    Smile Re: Generic Doubly Linked List

    Quote Originally Posted by aussiemcgr View Post
    I fixed your code (I think) and commented so you would understand it. Tell me if this makes sense.
    public void addFirst(T data)
    {	
    	/* We can create the newNode variable now. If this is the first element,
    	 * the head will be set to null anyway, giving us the correct
    	 * value. Since this is the first Object, we know that 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, we want to set tail to be this Object
    		tail = newNode;
    	}
    	//We want to set head to be newNode
    	head = newNode;
    	//Increment Size
    	size++;
    }
    What if the list is of size 1 or greater before you add anything?

    Adding it to size 1 should make head = newNode and tail = oldHead;

    adding to size 2 or greater should make new node head and old head as head.next;

    Also, if head ==null, shouldn't we also set head now so it's also equal to newNode, as the list will be size 1 now after adding?

    Also, does that size increment work only for cases where head is not null, or for any case?

    Wait a minute, you're setting tail to new Node and head to newNode for when head is originally null?

    It will go through the if statement if it's null and then go to the rest of the stuff as well.

    Brilliant!

  28. #21
    Forum VIP
    Join Date
    Jul 2010
    Posts
    1,707
    Thanks
    25
    Thanked 338 Times in 313 Posts

    Default Re: Generic Doubly Linked List

    I believe I forgot a step. Look at the change I made:
    public void addFirst(T data)
    {  
        /* We can create the newNode variable now. If this is the first element,
         * the head will be set to null anyway, giving us the correct
         * value. Since this is the first Object, we know that 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, we want to set tail to be this Object
            tail = newNode;
        }
    [B]if(head!=null)
         head.setPrevious(newNode);[/B]
        //We want to set head to be newNode
        head = newNode;
        //Increment Size
        size++;
    }
    I forgot to set the old head's previous to our new head.

    What if the list is of size 1 or greater before you add anything?

    Adding it to size 1 should make head = newNode and tail = oldHead;
    Provided head and tail were set from the first element, there are no issues. When you add the new element, tail will stay the old head since head will no longer equal null.
    adding to size 2 or greater should make new node head and old head as head.next;
    Setting the old head as head.next is done in our constructor of our new node.
    Also, if head ==null, shouldn't we also set head now so it's also equal to newNode, as the list will be size 1 now after adding?
    Keep in mind that the if statement is not an if/else statement. So the code after the if statement will be executed regardless. That is where we set head to be our new node.
    Also, does that size increment work only for cases where head is not null, or for any case?
    I think my previous response answers this.
    Wait a minute, you're setting tail to new Node and head to newNode for when head is originally null?
    head will ONLY be null when the list is empty. In the event that the list is empty, meaning the object we are inserting is going to be the only object, then the tail should also be set to newNode. When the list has a size of 0, head and tail will be equal to null. When the list has a size of 1, head and tail will be equal to the same object. When the list has a size of anything greater than 1, head and tail will be equal to different objects.
    NOTE TO NEW PEOPLE LOOKING FOR HELP ON FORUM:

    When asking for help, please follow these guidelines to receive better and more prompt help:
    1. Put your code in Java Tags. To do this, put [highlight=java] before your code and [/highlight] after your code.
    2. Give full details of errors and provide us with as much information about the situation as possible.
    3. Give us an example of what the output should look like when done correctly.

    Join the Airline Management Simulation Game to manage your own airline against other users in a virtual recreation of the United States Airline Industry. For more details, visit: http://airlinegame.orgfree.com/

  29. The Following User Says Thank You to aussiemcgr For This Useful Post:

    javapenguin (October 12th, 2010)

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

    Question Re: Generic Doubly Linked List

     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> current,previous2;
     
            current = head; // makes current equal to head
            previous2 = null;
     
            for (int i=0;i<index;i++)
            {
                previous2 = current;
                current = current.getNext();
            }
           // for remove(3)
            // for i = 0;
            // previous2 = head;
            // current = head + 1;
            // for i = 0;
            // previous2 = head + 1;
            // current = head + 2;
            // for i = 1;
            // previous2 = head + 2;
            // current = head + 3;
            // for i = 2
            // previous2 = head + 3;
            // current = head + 4;
            // previous2.next = head + 5;
     
            Node<T> node3 = previous2;
            if (index!=0)
            {
            	  previous2.setNext(current.getNext());
     
            }
     
            else
            {
                head = head.getNext();
            }
            size--;
        }

    It's making some kind of glitch with this method.

    I'm wondering if it's because it's not setting previous2.getPrevious(Node n); where n is the Node at the index before previous2, which would be value head + 2.

    If so, how do I fix that? Do I have to alter the for loop?

    If not, what's wrong then? The else statement?

    Also, my get(int i) method won't work. I can't figure out how to use it on Nodes between head and tail.
    I have to give the whole Node class plus the method itself to explain:
     private class Node<T>
        {
            private T data;
            private Node<T> next;
                   private Node<T> previous;
     
            public Node(T data,Node<T> next, Node<T> previous)
            {
                this.data = data;
                this.next = next;
                           this.previous=previous;
            }
     
            public T getData()
            {
                return data;
            }
     
            public Node<T> getNext()
            {
                return next;
            }
     
    public Node<T> getPrevious()
    {
    return previous;
    }
     
            public void setNext(Node<T> next)
            {
                this.next = next;
            }      
     
    public void setPrevious(Node<T> previous)
    {
    this.previous = previous;
    }
        }

     
    public T get(int i)
        {
        	if (i < 0 || i >= size)
        		return null;
     
        	if (i ==0)
        	{
        			Node<T> thisNode = head;
        			return(head.getData());
        	}
     
     
        	// How do I get it to return the data at i?
     
     
        }
        public T front()
        {
        	if (head == null)
        		return null;
     
        	return(get(0));
        }
     
        public T back()
        {
        	if (tail == null)
        		return null;
     
        	return(get(size - 1));
        }

    Also, I figured out what I'm supposed to do for alternateString(). I'm supposed it set it up so it prints first, last, 2nd, 2nd to last, 3rd, 3rd to last, etc, till it reaches the middle.
    But how do I do that? I could try the get(int i) method, but that only works with data. I can use the toString() code as help to get the brackets, but I'm kind of lost:
    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]�
    */
    }

  31. #23
    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: Generic Doubly Linked List

    Ok, I think I fixed the get() method so it works.

    However, what's wrong with the remove method? Wait, maybe nothing is after all, but what about the alternateString()?

  32. #24
    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: Generic Doubly Linked List

    It seems that my remove() method didn't correct the previous references. I kinda need this class again for another assignment, which is going to be a total nightmare. Also my code for printAlternate() should stop halfway and size -2 logic doesn't work for any value of size he said.

    Also, my removeFirst() in my other class calls removeLast().

    I need to have this class fixed.

    The second class I may not have to worry about, but it would be nice to have that fixed as well.

    package Assignment4;
     
    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: 10/12/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.  
     
     
    public class DoublyLinkedList<T>
    {
        private class Node<T>
        {
            private T data;
            private Node<T> next;
                   private Node<T> previous;
     
            public Node(T data,Node<T> next, Node<T> previous)
            {
                this.data = data;
                this.next = next;
                           this.previous=previous;
            }
     
            public T getData()
            {
                return data;
            }
     
            public Node<T> getNext()
            {
                return next;
            }
     
    public Node<T> getPrevious()
    {
    return previous;
    }
     
            public void setNext(Node<T> next)
            {
                this.next = next;
            }      
     
    public void setPrevious(Node<T> previous)
    {
    this.previous = previous;
    }
        }
     
        private Node<T> head;//head of the linked list
           private Node<T> tail; // tail of linked list
        private int size;
       private ImageIcon icon;
       private Icon icon2;
        public DoublyLinkedList()
        {
            head = null;
                    tail = null;
            size = 0;
            icon = new ImageIcon("doh3.jpg");
        }
     
        // returns a String of all the items in the linked list.  
        public String toString()
        {
            String str = "[";
     
            Node<T> curr;
     
            for (curr=head;curr!=null;curr = curr.getNext())
            {
                str = str + curr.getData();
                if (curr.getNext()!=null)
                    str = str + " ";
            }
            str = str + "]";
            return str;
     
     
        }
     
        // 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.  
        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++;
    }
     
        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--;
        }
     
        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(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++;
        }
     
        public int Size()
        {
        	return(size);
        }
     
        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++;
        }  
     
        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> current,previous2;
     
            current = head; // makes current equal to head
            previous2 = null;
     
            for (int i=0;i<index;i++)
            {
                previous2 = current;
                current = current.getNext();
            }
           // for remove(3)
            // for i = 0;
            // previous2 = head;
            // current = head + 1;
            // for i = 0;
            // previous2 = head + 1;
            // current = head + 2;
            // for i = 1;
            // previous2 = head + 2;
            // current = head + 3;
            // for i = 2
            // previous2 = head + 3;
            // current = head + 4;
            // previous2.next = head + 5;
     
            Node<T> node3 = previous2;
            if (index!=0)
            {
            	  previous2.setNext(current.getNext());
     
            }
     
            else
            {
                head = head.getNext();
            }
            size--;
        }
     
        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?
     
     
        }
     
        // calls get method of first index
        public T front()
        {
        	if (head == null)
        		return null;
     
        	return(get(0));
        }
     
        // calls get Method of last index
        public T back()
        {
        	if (tail == null)
        		return null;
     
        	return(get(size - 1));
        }
     
        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);
    }
    }
    package Assignment4;
     
    import javax.swing.JOptionPane;
     
    // this class basically just sorts the DoublyLinkedList it has internally.  
     
    /**
     * @author pradcoc
     *
     */
    public class SortedDoublyLinkedList<T extends Comparable> {
     
    	private DoublyLinkedList<T> dll;
     
    	public SortedDoublyLinkedList()
    	{
    		dll = new DoublyLinkedList<T>();
    	}
     
     
    	public void add(T data)
    	{
    		for (int penguin = 0; penguin < dll.Size(); penguin++)
    		{
     
    			// adds it when it is "less than" the next value
    			if (data.compareTo(dll.get(penguin)) == -1)
    			{
    				dll.add(penguin, data);
    			}
     
    			// also adds it, because I don't quite know what to do with equal values, when its next value is equal to it
    			else if (data.compareTo(dll.get(penguin)) == 0)
    			{
    				dll.add(penguin, data);
    			}
     
    			else
    			{
    				// if its next value is not the maximum, it does nothing and keeps going
    				if (penguin != dll.Size() -1)
    				{
    					// don't add it
    				}
    				// when it reaches the end it adds it
    				else
    					dll.add(penguin, data);
    			}
    		}
    	}
    	public String toString()
    	{
     
    		return(dll.toString());
    	}
     
    	public void removeLast()
    	{
    		/* String str = "["
    			String str
    		for (int j = 0; j < dll.Size(); j++)
    		{
    			dll.get(j).compareTo(dll.get(j+1));
     
     
    		}
    		*/
    		if (dll.Size() == 0)
    		{
    			JOptionPane.showMessageDialog(null, "Cannot remove from an empty list!", "Invalid removal", JOptionPane.ERROR_MESSAGE);
    			return;
    		}
    		dll.removeLast();
    	}
     
    	public void removeFirst()
    	{
    		dll.removeLast();
    	}
     
    }

    package Assignment4;
     
    // this is my test class
     
    public class Test {
     
    	public static void main(String[] args)
    	{
    		DoublyLinkedList<String> list= new DoublyLinkedList<String>();
    	//	list.add(0, "Mack");
    	//	System.out.println(list.get(0));
    	//	list.addFirst("Bob");
    		System.out.println(list.toString());
    		System.out.println(list.Size());
    	list.addLast("Gordon");
    	list.remove(0);
    	System.out.println(list.toString());
    	System.out.println(list.Size());
    	System.out.println(list.Size());
    	System.out.println(list.toString());
    	list.addFirst("Joe");
    	System.out.println(list.Size());
    		//list.removeFirst();
    		System.out.println(list.toString());
    	list.add(1,"Bob");
    	System.out.println(list.toString());
    	System.out.println(list.Size());
    	list.addFirst("Beth");
    	System.out.println(list.Size());
    	list.add(-1, "Mack2");
    list.get(0);
    System.out.println("Hey: " +list.get(0));
    	System.out.println(list.toString());
    	list.remove(-2);
    	list.remove(1);
    	System.out.println(list.Size());
    	System.out.println(list.toString());
    	list.removeFirst();
    	System.out.println(list.Size());
    	System.out.println(list.toString());
    	list.removeLast();
    	System.out.println(list.Size());
    	System.out.println(list.toString());
    	SortedDoublyLinkedList<String> sdll = new SortedDoublyLinkedList<String>();
    	 sdll.removeFirst();
    	System.out.println(list.toString());
    	sdll.removeFirst();
     
    	}
    }

Similar Threads

  1. Merging Arrays Vs. Linked List.
    By Kumarrrr in forum Collections and Generics
    Replies: 1
    Last Post: March 1st, 2010, 03:20 AM
  2. Simple linked list
    By Koren3 in forum Collections and Generics
    Replies: 10
    Last Post: November 2nd, 2009, 03:33 AM
  3. circular linked list
    By student123xyz in forum Collections and Generics
    Replies: 4
    Last Post: August 19th, 2009, 11:40 AM
  4. ClassCastException in Double Linked List toString
    By Rastabot in forum Collections and Generics
    Replies: 2
    Last Post: April 24th, 2009, 12:48 PM
  5. Recursive function based on Linked list
    By rosh72851 in forum Collections and Generics
    Replies: 1
    Last Post: March 9th, 2009, 07:23 PM