Thread: Sorted Doubly linked List

I required to create a sorted doubly linked list for my homework. Inside the SortedStringList, I need to implement a method called insert(). I have some problem in doing so. I don't what is going wrong to my code below:

public class SortedStringList {
 
   private static class Node {
    public String value;
    public Node previous, next;
 
    public Node(String v, Node p, Node n) {
        value = v;
        previous = p;
        next = n;
    }
}
 
private Node first;
private Node last;
 
public SortedStringList(){
    this.first = null;
    this.last = null;
}
 
public void insert(String s){
    Node newnode = new Node(s,this.first,this.last);
    if(first == null){
        first = newnode;
    }
 else
     if(first.value.compareTo(s) >= 0){
         newnode.next = first;
         newnode.previous = null;
         first = newnode;
         last = first;
     }
 else
     {
        Node current = first;
        newnode.previous = first;
 
        while(current.value.compareTo(s)<=0 ){
            if(current.next == null){
                current.next = newnode;
                first = current;
                last = newnode.next;
 
            }
            first.previous = current;
            current = current.next;
        }
            first.previous.next = newnode;
            newnode.next = current;
            current = first;
 }
 
 
 
}
}

Can somebody please give me some idea?

Cross posted
Sorted Doubly linked List - Java Forums

Any more?

db

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

That's one I made for a class. Should be similar to yours.

Maybe not exact though.