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

Originally Posted by TeamRival

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.