Doubly Linked Lists For this assignment you will implement a list class using do
ID: 3691349 • Letter: D
Question
Doubly Linked Lists
For this assignment you will implement a list class using doubly linked lists. Doubly linked lists are constructed from nodes that have two links: one links to the node following in the list (just as in singly linked lists); the other links to the node before it in the list.
Here are some references (among very many available) that you might find helpful:
Double linked list in Wikipedia
DLList: A Doubly-Linked List
This version uses the base node, called ‘dummy’
Slides covering double linked lists
However, please be aware that there are different ways to organize a doubly linked list. Make sure that you use the one specified here
Requirements
Start with the project archive assign06-doubly-linked-lists.zip. This contains a partial implementation of doubly linked lists. Your job is to complete the implementation of various methods in the list class DList:
int size()
Object get(int i)
Object set(int i, Object value)
void add(int index, Object element)
Object remove(int index)
The project file DList.java contains the skeletons of these methods with comments that explain what they should do. These methods are patterned after the ones from the Java collection framework.
To assist you, various methods are already provided, fully implemented:
boolean equals(Object obj)
boolean hasProperStructure()
String toString()
Implementation
The Node class should be familiar looking Node.java.
The DList class contains one instance variable, a Node named base.
public class DList {
private Node base;
The base node is used to anchor the nodes that make up the list. The base node is not counted as part of the list. Here is how the links work for the base node:
The next field of the base references the first node of the list
The previous field of the base references the last node of the list
The next of the last node in the list references base
The previous of the first node in the list references base
Looking at the first two points, the Node references in base indicate the head and the tail of the list (similarly to the simple list illustrated in class). The last two points create what is called a circularly linked list. That is, if you keep following next pointers you will go around and around the list. Similarly, following previous pointers will take you around the list again and again.
None of the links will be null in this implementation. The base node serves the same purpose. By having the base node, the code is simplified because there are fewer special cases to worry about. For example, removing the last element in a singly linked list is particularly difficult. But, in a doubly linked list, it is no more difficult than removing any other element.
The picture to the right shows a doubly linked list with three elements. The base node is shown in a different color from the ‘real’ nodes to make it easier to distinguish.
The next picture shows a list with one element. Since that one element is both first and last in the list, both references from base point to the single element. Likewise, both links from that element point towards base.
Finally, an empty list must be set up carefully so that the algorithms work properly. The ‘trick’ is that both links in base point to itself. The picture at right illustrates this.
Testing
Some unit tests are provided with the project. They are not complete, but will get you started. Please check this page from time to time, new tests will be provided at the top of this page. A date will be given so you can check if you have the most recent version of the tests.
public class Node {
private Node previous, next;
private Object data;
public Node(Object data) {
this.data = data;
}
public Node() {
}
public Node(Object data, Node previous, Node next) {
this.previous = previous;
this.next = next;
this.data = data;
}
public Node getPrevious() {
return previous;
}
public void setPrevious(Node previous) {
this.previous = previous;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
}
public class DList {
Explanation / Answer
TestDList.java
public class TestDList
{
public static void main(String[] args)
{
DList list = new DList();
System.out.println("Size: " + list.size());
list.add(0,42);
System.out.println("Size: " + list.size());
printList(list);
list.add(0,21);
list.add(0,12.5);
System.out.println("Size: " + list.size());
printList(list);
list.remove(0);
System.out.println("Size: " + list.size());
printList(list);
list.set(0,0);
list.set(1,1);
printList(list);
System.out.println(list.toString());
for(int i = 2; i<10; ++i)
{
list.add(list.size(),i);
}
System.out.println(list.toString());
}
private static void printList(DList list)
{
for(int i=0; i<list.size(); ++i)
{
System.out.print(list.get(i) + " ");
}
System.out.println();
}
}
DList.java
public class DList
{
private Node base;
public DList()
{
base = new Node();
base.setNext(base);
base.setPrevious(base);
}
/**
* Return the number of elements in the list.
*/
public int size()
{
int count = 0;
Node n = base.getNext();
while(n != base)
{
++count;
n = n.getNext();
}
return count;
}
/**
* Return the element at index i.
* If i is out of bounds (less than 0 or greater than or
* equal to size()) throw an IndexOutOfBounds exception.
*/
public Object get(int i)
{
if(i < 0 || i >= size())
{
throw new IndexOutOfBoundsException();
}
else
{
Node n = base.getNext();
while(i > 0)
{
n = n.getNext();
--i;
}
return n.getData();
}
}
/**
* Change the value at index i to 'value'.
* Return the old value stored at index i.
* If i is out of bounds (less than 0 or greater than or
* equal to size()) throw an IndexOutOfBounds exception.
*
*/
public Object set(int i, Object value)
{
if(i < 0 || i >= size())
{
throw new IndexOutOfBoundsException();
}
else
{
Node n = base.getNext();
while(i > 0)
{
n = n.getNext();
--i;
}
Object old = n.getData();
n.setData(value);
return old;
}
}
/**
* Insert the new element so that it ends up as index 'index'.
* If i is out of bounds (less than 0 or greater than
* size()) throw an IndexOutOfBounds exception.
*
* Note that index is allowed to be equal to size(). This just
* means the new element will go at the end of the list.
*/
public void add(int index, Object element)
{
if(index < 0 || index > size())
{
throw new IndexOutOfBoundsException();
}
else
{
Node newElem = new Node(element);
Node n = base.getNext();
while(index > 0)
{
n = n.getNext();
--index;
}
n.getPrevious().setNext(newElem);
newElem.setPrevious(n.getPrevious());
n.setPrevious(newElem);
newElem.setNext(n);
}
}
/**
* Remove the element at index i and return the element value.
*
* If i is out of bounds (less than 0 or greater than or
* equal to size()) throw an IndexOutOfBounds exception.
*
* @param index
* @return
*/
public Object remove(int index)
{
if(index < 0 || index >= size())
{
throw new IndexOutOfBoundsException();
}
else
{
Node n = base.getNext();
while(index > 0)
{
n = n.getNext();
--index;
}
n.getPrevious().setNext(n.getNext());
n.getNext().setPrevious(n.getPrevious());
return n.getData();
}
}
@Override
public boolean equals(Object obj)
{
if(obj == null)
// if obj is null, then it cannot be equal since 'this' is not null
return false;
else if(!(obj instanceof DList))
// if obj is not a DList, then it cannot be equal to 'this'
return false;
else
{
// cast since we know obj is a DList
DList dl = (DList)obj;
// prepare to compare nodes
Node p = this.base;
Node q = dl.base;
// stop if either list is exhausted
while(p != this.base && q != dl.base)
{
// compare the data
if(!p.getData().equals(q.getData()))
// if data in current node not equal, the lists are not equal
// return false;
return false;
else
{
// data in current nodes is equal, so keep looking
p = p.getNext();
q = q.getNext();
}
}
// All nodes checked are equal, otherwise we would have returned false already
// Now just make sure both lists have been completely examined
return p == this.base && q == dl.base;
}
}
public boolean hasProperStructure()
{
Node p = base;
do
{
if(p.getNext().getPrevious() != p || p.getPrevious().getNext() != p)
return false;
p = p.getNext();
} while(p != base);
return true;
}
@Override
public String toString()
{
StringBuilder sb = new StringBuilder("[");
Node p = base.getNext();
while(p != base)
{
sb.append(p.getData());
if(p.getNext() != base)
sb.append(",");
p = p.getNext(); // Line forgotten in original code
}
sb.append("]");
return sb.toString();
}
}
Node.java
public class Node
{
private Node previous, next;
private Object data;
public Node()
{
}
public Node(Object data)
{
this.data = data;
}
public Node(Object data, Node previous, Node next)
{
this.previous = previous;
this.next = next;
this.data = data;
}
public Node getPrevious()
{
return previous;
}
public void setPrevious(Node previous)
{
this.previous = previous;
}
public Node getNext()
{
return next;
}
public void setNext(Node next)
{
this.next = next;
}
public Object getData()
{
return data;
}
public void setData(Object data)
{
this.data = data;
}
}
sample output
Size: 0
Size: 1
42
Size: 3
12.5 21 42
Size: 2
21 42
0 1
[0,1]
[0,1,2,3,4,5,6,7,8,9]
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.