I am trying to follow the template provided here to create a doubly linked list in java. This homework is based on this lecture. Can someone please review my implementation?
No change to this part of the code
/* DListNode.java */
/**
* A DListNode is a node in a DList (doubly-linked list).
*/
public class DListNode {
/**
* item references the item stored in the current node.
* prev references the previous node in the DList.
* next references the next node in the DList.
*
* DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS.
*/
public Object item;
protected DListNode prev;
protected DListNode next;
/**
* DListNode() constructor.
* @param i the item to store in the node.
* @param p the node previous to this node.
* @param n the node following this node.
*/
DListNode(Object i, DListNode p, DListNode n) {
item = i;
prev = p;
next = n;
}
}
This is the code that I updated
/* DList.java */
/**
* A DList is a mutable doubly-linked list ADT. Its implementation is
* circularly-linked and employs a sentinel (dummy) node at the head
* of the list.
*
* DO NOT CHANGE ANY METHOD PROTOTYPES IN THIS FILE.
*/
public class DList {
/**
* head references the sentinel node.
* size is the number of items in the list. (The sentinel node does not
* store an item.)
*
* DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS.
*/
protected DListNode head;
protected int size;
private DListNode sentinel;
/* DList invariants:
* 1) head != null.
* 2) For any DListNode x in a DList, x.next != null.
* 3) For any DListNode x in a DList, x.prev != null.
* 4) For any DListNode x in a DList, if x.next == y, then y.prev == x.
* 5) For any DListNode x in a DList, if x.prev == y, then y.next == x.
* 6) size is the number of DListNodes, NOT COUNTING the sentinel,
* that can be accessed from the sentinel (head) by a sequence of
* "next" references.
*/
/**
* newNode() calls the DListNode constructor. Use this class to allocate
* new DListNodes rather than calling the DListNode constructor directly.
* That way, only this method needs to be overridden if a subclass of DList
* wants to use a different kind of node.
* @param item the item to store in the node.
* @param prev the node previous to this node.
* @param next the node following this node.
*/
protected DListNode newNode(Object item, DListNode prev, DListNode next) {
return new DListNode(item, prev, next);
}
/**
* DList() constructor for an empty DList.
*/
public DList() {
// Your solution here.
sentinel=newNode(null,null,null);
sentinel.prev=sentinel;
sentinel.next=sentinel;
head=sentinel;
}
/**
* isEmpty() returns true if this DList is empty, false otherwise.
* @return true if this DList is empty, false otherwise.
* Performance: runs in O(1) time.
*/
public boolean isEmpty() {
return size == 0;
}
/**
* length() returns the length of this DList.
* @return the length of this DList.
* Performance: runs in O(1) time.
*/
public int length() {
return size;
}
/**
* insertFront() inserts an item at the front of this DList.
* @param item is the item to be inserted.
* Performance: runs in O(1) time.
*/
public void insertFront(Object item) {
// Your solution here.
sentinel.next=newNode(item,sentinel,sentinel.next);
if(sentinel.prev==sentinel)
{
sentinel.prev=sentinel.next;
}
size++;
}
/**
* insertBack() inserts an item at the back of this DList.
* @param item is the item to be inserted.
* Performance: runs in O(1) time.
*/
public void insertBack(Object item) {
// Your solution here.
sentinel.prev=newNode(item,sentinel.prev,sentinel);
if(sentinel.next==sentinel)
{
sentinel.next=sentinel.prev;
}
size++;
}
/**
* front() returns the node at the front of this DList. If the DList is
* empty, return null.
*
* Do NOT return the sentinel under any circumstances!
*
* @return the node at the front of this DList.
* Performance: runs in O(1) time.
*/
public DListNode front() {
// Your solution here.
if(size>0)
{
return sentinel.next;
}
else
{
return null;
}
}
/**
* back() returns the node at the back of this DList. If the DList is
* empty, return null.
*
* Do NOT return the sentinel under any circumstances!
*
* @return the node at the back of this DList.
* Performance: runs in O(1) time.
*/
public DListNode back() {
// Your solution here.
if(size>0)
{
return sentinel.prev;
}
else
{
return null;
}
}
/**
* next() returns the node following "node" in this DList. If "node" is
* null, or "node" is the last node in this DList, return null.
*
* Do NOT return the sentinel under any circumstances!
*
* @param node the node whose successor is sought.
* @return the node following "node".
* Performance: runs in O(1) time.
*/
public DListNode next(DListNode node) {
if(node==null || node.next==sentinel)
{
return null;
}
else
{
return node.next;
}
}
/**
* prev() returns the node prior to "node" in this DList. If "node" is
* null, or "node" is the first node in this DList, return null.
*
* Do NOT return the sentinel under any circumstances!
*
* @param node the node whose predecessor is sought.
* @return the node prior to "node".
* Performance: runs in O(1) time.
*/
public DListNode prev(DListNode node) {
if(node==null || node.prev==sentinel)
{
return null;
}
else
{
return node.prev;
}
}
/**
* insertAfter() inserts an item in this DList immediately following "node".
* If "node" is null, do nothing.
* @param item the item to be inserted.
* @param node the node to insert the item after.
* Performance: runs in O(1) time.
*/
public void insertAfter(Object item, DListNode node) {
// Your solution here.
if(node!=null);
{
node.next=newNode(item,node,node.next);
size++;
}
}
/**
* insertBefore() inserts an item in this DList immediately before "node".
* If "node" is null, do nothing.
* @param item the item to be inserted.
* @param node the node to insert the item before.
* Performance: runs in O(1) time.
*/
public void insertBefore(Object item, DListNode node) {
// Your solution here.
if(node!=null);
{
node.prev=newNode(item,node.prev,node);
size++;
}
}
/**
* remove() removes "node" from this DList. If "node" is null, do nothing.
* Performance: runs in O(1) time.
*/
public void remove(DListNode node) {
// Your solution here.
if(node!=null);
{
node.prev.next=node.next;
node.next.prev=node.prev;
size--;
}
}
/**
* toString() returns a String representation of this DList.
*
* DO NOT CHANGE THIS METHOD.
*
* @return a String representation of this DList.
* Performance: runs in O(n) time, where n is the length of the list.
*/
public String toString() {
String result = "[ ";
DListNode current = head.next;
while (current != head) {
result = result + current.item + " ";
current = current.next;
}
return result + "]";
}
}
generics
are? If yes, then try to update yourDListNode
andDList
classes to use generics there. It improves type safety. – Tom Nov 24 '14 at 22:26