Thread: 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 Away! Bob] 


I want [Bob]

[Bob Go Away!]

Why the reversal?

My code is a disaster!!!

Originally Posted by aussiemcgr

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?