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

Thread: Update on 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

    Angry Update on Doubly Linked List

    Well, it seems nobody is around. And the forum was down yesterday, and I need help, and I'm clarifying some things.

    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,tail);
         //   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;
            }
     
            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;
            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]”
    */
    }
    }

    package Assignment4;
     
    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());
    		list.addLast("Go Away!");
    		System.out.println(list.toString());
     
    	}
    }

    OUTPUT FROM TEST:
    PHP Code:
    [Bob]
    [
    Go AwayBob
    I want [Bob]

    [Bob Go Away!]

    Why the reversal?

    My code is a disaster!!!


  2. #2
    Forum VIP
    Join Date
    Jul 2010
    Posts
    1,629
    Thanks
    25
    Thanked 322 Times in 300 Posts

    Default Re: Update on Doubly Linked List

    When you add the first object, that first object should be both head and tail. What is happening is: since when you call addLast in your second statement tail is null, then it uses the addFirst method.

    In your addFirst method, you should also check to see if the new element is the only element. If it is, than that element should be set to head AND tail. There is no need to do this in your addLast method, as if there are no elements, it will use the addFirst method and solve this problem for us anyway.
    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

    Angry Re: Update on Doubly Linked List

    Quote Originally Posted by aussiemcgr View Post
    When you add the first object, that first object should be both head and tail. What is happening is: since when you call addLast in your second statement tail is null, then it uses the addFirst method.

    In your addFirst method, you should also check to see if the new element is the only element. If it is, than that element should be set to head AND tail. There is no need to do this in your addLast method, as if there are no elements, it will use the addFirst method and solve this problem for us anyway.
    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, 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++; 
        }
     
        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;
            }
     
            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;
            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]”
    */
    }

    Why won't it work?

Similar Threads

  1. Generic Doubly Linked List
    By javapenguin in forum What's Wrong With My Code?
    Replies: 23
    Last Post: October 23rd, 2010, 03:13 PM
  2. Simple linked list
    By Koren3 in forum Collections and Generics
    Replies: 10
    Last Post: November 2nd, 2009, 02:33 AM
  3. circular linked list
    By student123xyz in forum Collections and Generics
    Replies: 4
    Last Post: August 19th, 2009, 10:40 AM
  4. ClassCastException in Double Linked List toString
    By Rastabot in forum Collections and Generics
    Replies: 2
    Last Post: April 24th, 2009, 11:48 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