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

Thread: need help with Doubly-Linked list programing in java

  1. #1
    Junior Member
    Join Date
    Mar 2011
    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default need help with Doubly-Linked list programing in java

    the code that i m working with is singly-link list and i have to implement it to the double-link list. I know all constructers will be sama but i got stock on implementation.. this is the code ...

    public class LList<T>
    	implements IList<T>
    {
    //	Define private inner class Node.
     
    	private class Node
    	{
    		T data;
    		Node next;
     
    		Node(T data, Node next)
    		{
    			this.data = data;
    			this.next = next;
    		}
     
    		Node(T data)
    		{	this(data, null);	}
    	}
     
    //	Declare instance fields/variables.
     
    	private Node head;
    	private int count;
     
    //	Define default constructor.
     
    	public LList()
    	{	this.clear();	}
     
    //	Define private helper methods.
     
    	/*
    	 *	Precondition: 0 <= index < this.count.
    	 */
    	private Node getNodeAt(int index)
    	{
    		Node curr = this.head;
    		for (int i = 0; i < index; i++)
    			curr = curr.next;
    		return curr;
    	}
     
    //	Define methods declared in interface IList<T>.
     
    	@Override
    	public int size()
    	{	return this.count;	}
     
    	@Override
    	public void clear()
    	{
    		this.head = null;
    		this.count = 0;
    	}
     
    	@Override
    	public T get(int index)
    	{
    		T result = null;
    		if (0 <= index && index < this.count)
    			result = this.getNodeAt(index).data;
    		return result;
    	}
     
    	@Override
    	public T set(int index, T data)
    	{
    		T result = null;
    		if (0 <= index && index < this.count) {
    			Node curr = this.getNodeAt(index);
    			result = curr.data;
    			curr.data = data;
    		}
    		return result;
    	}
     
    	@Override
    	public boolean add(T data)
    	{
    		Node newNode = new Node(data);
    		if (this.count == 0)
    			this.head = newNode;
    		else {
    			Node prev = this.getNodeAt(this.count - 1);
    			prev.next = newNode;
    		}
    		this.count++;
    		return true;
    	}
     
    	@Override
    	public boolean add(int index, T data)
    	{
    		boolean result = false;
    		if (0 <= index && index <= this.count) {
    			if (index == 0) {
    				Node newNode = new Node(data, this.head);
    				this.head = newNode;
    			}
    			else {
    				Node prev = this.getNodeAt(index - 1);
    				Node next = prev.next;
    				Node newNode = new Node(data, next);
    				prev.next = newNode;
    			}
    			this.count++;
    			result = true;
    		}
    		return result;
    	}
     
    	@Override
    	public T remove(int index)
    	{
    		T result = null;
    		if (0 <= index && index < this.count) {
    			Node curr = null;
    			if (index == 0) {
    				curr = this.head;
    				this.head = curr.next;
    			}
    			else {
    				Node prev = this.getNodeAt(index - 1);
    				curr = prev.next;
    				prev.next = curr.next;
    			}
    			this.count--;
    			result = curr.data;
    		}
    		return result;
    	}
     
    	@Override
    	public int indexOf(T that)
    	{
    		int result = -1;
    		Node curr = this.head;
    		for (int i = 0; result == -1 && i < this.count; i++) {
    			if (that.equals(curr.data)) result = i;
    			curr = curr.next;
    		}
    		return result;
    	}
     
    	@Override
    	public boolean contains(T that)
    	{
    		return this.indexOf(that) >= 0;
    	}
     
    //	Override methods defined in Object.
     
    	@Override
    	public String toString()
    	{
    		StringBuilder sb = new StringBuilder("[");
    		Node curr = this.head;
    		for (int i = 0; i < this.count; i++) {
    			if (i > 0) sb.append(", ");
    			sb.append(curr.data);
    			curr = curr.next;
    		}
    		sb.append(']');
    		return sb.toString();
    	}
     
    	@Override
    	@SuppressWarnings("unchecked")
    	public boolean equals(Object other)
    	{
    		boolean result = false;
    		if (other != null) {
    			if (this.getClass() == other.getClass()) {
    				LList<T> that = (LList<T>)other;
    				if (this.size() == that.size()) {
    					Node thisCurr = this.head;
    					Node thatCurr = that.head;
    					for (int i = 0; i < this.count; i++) {
    						if ( ! thisCurr.data.equals(thatCurr.data)) break;
    						thisCurr = thisCurr.next;
    						thatCurr = thatCurr.next;
    					}
    					if (thisCurr == null) result = true;
    				}
    			}
    		}
    		return result;
    	}
     
    //	Define main() method to unit test this class.
     
    	public static void main(String[] args)
    	{
    		IList<String> list = new LList<String>();
    		String s;
    		int i;
     
    		System.out.printf("%d: %s%n", list.size(), list);
    		list.add("Hello");
    		System.out.printf("%d: %s%n", list.size(), list);
    		list.add("World");
    		System.out.printf("%d: %s%n", list.size(), list);
    		list.add(0, "Well");
    		System.out.printf("%d: %s%n", list.size(), list);
    		list.add(2, "New");
    		System.out.printf("%d: %s%n", list.size(), list);
    		list.add(list.size(), ".");
    		System.out.printf("%d: %s%n", list.size(), list);
    		s = list.get(2);
    		System.out.printf("retrieved at %d: %s%n", 2, s);
    		s = list.set(2, "new");
    		System.out.printf("replaced at %d: %s%n", 2, s);
    		System.out.printf("%d: %s%n", list.size(), list);
    		s = list.get(5);
    		System.out.printf("retrieved at %d: %s%n", 5, s);
     
    		i = list.indexOf("new");
    		System.out.printf("String /%s/ found at: %d%n", "new", i);
    		i = list.indexOf("old");
    		System.out.printf("String /%s/ found at: %d%n", "old", i);
     
    		s = list.remove(0);
    		System.out.printf("removed at %d: %s%n", 0, s);
    		System.out.printf("%d: %s%n", list.size(), list);
    		s = list.remove(list.size() - 1);
    		System.out.printf("removed at %d: %s%n", list.size(), s);
    		System.out.printf("%d: %s%n", list.size(), list);
    		s = list.remove(0);
    		System.out.printf("removed at %d: %s%n", 0, s);
    		System.out.printf("%d: %s%n", list.size(), list);
    		s = list.remove(0);
    		System.out.printf("removed at %d: %s%n", 0, s);
    		System.out.printf("%d: %s%n", list.size(), list);
    		s = list.remove(0);
    		System.out.printf("removed at %d: %s%n", 0, s);
    		System.out.printf("%d: %s%n", list.size(), list);
     
    		IList<String> la = new LList<String>();
    		IList<String> lb = new LList<String>();
    		for (char c = 'a'; c <= 'e'; c++) {
    			s = String.format("%c", c);
    			la.add(s);
    			lb.add(s);
    		}
    		System.out.println();
    		System.out.printf("%d: %s%n", la.size(), la);
    		System.out.printf("%d: %s%n", lb.size(), lb);
    		System.out.printf("la.equals(lb): %b%n", la.equals(lb));
    		lb.set(3, "D");
    		System.out.printf("%d: %s%n", lb.size(), lb);
    		System.out.printf("la.equals(lb): %b%n", la.equals(lb));
    	}
    }
    Last edited by helloworld922; March 5th, 2011 at 01:17 AM.


  2. #2
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: need help with Doubly-Linked list programing in java

    Where are you getting stuck? The more specific your question is, the better the responses will be.

  3. #3
    Junior Member
    Join Date
    Aug 2011
    Posts
    7
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: need help with Doubly-Linked list programing in java

    The Only difference between doubly and singly linked list is that Doubly linked list requires two pointers ie:Next and Previous.You need to Modify the Node Class to Include Previous Pointer and also the necessary modifications in the code should be made for back linking to the previous node.

  4. #4
    Junior Member
    Join Date
    Jan 2011
    Posts
    4
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: need help with Doubly-Linked list programing in java

    Also to add to the Node Next and Node Previous, its usually a good idea to have a Root Node, where previous points back to itself, to avoid falling off the end of the list. Also, depending on the application, whenever you create a new node on the end, you want to point it back to root. Because you can work backwards, its generally a good idea to have ALL of the points going somewhere to avoid errors

Similar Threads

  1. Help with a doubly linked circular list
    By TeamRival in forum What's Wrong With My Code?
    Replies: 1
    Last Post: March 3rd, 2011, 10:59 PM
  2. Generic Doubly Linked List
    By javapenguin in forum What's Wrong With My Code?
    Replies: 23
    Last Post: October 23rd, 2010, 04:13 PM
  3. [SOLVED] Update on Doubly Linked List
    By javapenguin in forum What's Wrong With My Code?
    Replies: 2
    Last Post: October 11th, 2010, 08:19 PM
  4. ClassCastException in Double Linked List toString
    By Rastabot in forum Collections and Generics
    Replies: 2
    Last Post: April 24th, 2009, 12:48 PM

Tags for this Thread