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

Thread: Help with a doubly linked circular list

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

    Default Help with a doubly linked circular list

    I'm taking data structures and my professor has assigned to us the task of creating a doubly linked circular list with only 1 pointer. Here's the instructions he assigned us:

    I have posted the base files for the first homework assignment under Content/HW1.

    In addition to the file IList.java there is an updated version of LList.java. I have also posted a test program ListTest.java and sample output from this program ListTest.txt.

    Your assignment is to write the file (and submit it to Dropbox: HW1) DLList.java. This file will be a separate class (not inherited) to implement a double-linked, circular list. There should only be a single pointer this.head into the list. The last element of the list will point to the first element and the first will additionally point to the last (i.e., a circular list). All methods defined by the interface IList must be implemented as well as the toString() method.

    The test program will compare the performance of a Singly-Linked and a Doubly-Linked list as defined in LList.java and DLList.java. Note that you should probably write a main() method for the DLList class to unit test the class definition. You might find it interesting to study the test program which defines a technique for instrumenting the performance testing protocol with a minimum of extra methods.
    So basically from what I understand there should only be 1 pointer that defines your position in the list. I'm not too sure how to implement it, as I was going to use 2 pointers to accomplish this. I think once I figure out some sort of plan as how to figure this out I will be able to move forward better. Here's some code I had been working on, it's not perfect by any means but it's at least something to reference off of.

    public class DLList<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 DLList()
    	{	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>.
     
     
    	public int size()
    	{	return this.count;	}
     
     
    	public void clear()
    	{
    		this.head = null;
    		this.count = 0;
    	}
     
     
    	public T get(int index)
    	{
    		T result = null;
    		if (0 <= index && index < this.count)
    			result = this.getNodeAt(index).data;
    		return result;
    	}
     
     
    	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;
    	}
     
     
    	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;
    	}
     
     
    	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;
    	}
     
     
    	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;
    	}
     
     
    	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;
    	}
     
     
    	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()) {
    				DLList<T> that = (DLList<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 DLList<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 DLList<String>();
    		IList<String> lb = new DLList<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));
    	}
    }

    Thanks for the help, it is all appreciated. I understand how list and linked lists work, so I'm not a complete idiot when it comes to this


  2. #2
    Grand Poobah
    Join Date
    Mar 2011
    Posts
    1,545
    My Mood
    Grumpy
    Thanks
    0
    Thanked 167 Times in 158 Posts

    Default Re: Help with a doubly linked circular list

    Quote Originally Posted by TeamRival View Post
    So basically from what I understand there should only be 1 pointer that defines your position in the list.
    No. As the instructions say your only pointer is to the head of the list. Which has already been done in the code posted.

Similar Threads

  1. Sorting a doubly linked list
    By snufkin in forum What's Wrong With My Code?
    Replies: 1
    Last Post: December 26th, 2010, 12:01 PM
  2. Generic Doubly Linked List
    By javapenguin in forum What's Wrong With My Code?
    Replies: 23
    Last Post: October 23rd, 2010, 03:13 PM
  3. Sorted Doubly linked List
    By student in forum What's Wrong With My Code?
    Replies: 2
    Last Post: October 15th, 2010, 09:52 PM
  4. [SOLVED] Update on Doubly Linked List
    By javapenguin in forum What's Wrong With My Code?
    Replies: 2
    Last Post: October 11th, 2010, 07:19 PM
  5. circular linked list
    By student123xyz in forum Collections and Generics
    Replies: 4
    Last Post: August 19th, 2009, 10:40 AM