Thread: 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.

So, whats wrong?

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.

Originally Posted by aussiemcgr

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

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

Originally Posted by aussiemcgr

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]”
*/
}
}

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.

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.

Originally Posted by aussiemcgr

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?

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.

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.

Originally Posted by aussiemcgr

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?

Originally Posted by javapenguin

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

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

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.