I need to write a method to clearList method that recovers all memory but I\'m n
ID: 3632600 • Letter: I
Question
I need to write a method to clearList method that recovers all memory but I'm not sure how to write it, if someone could write it and explain how they did it you would be a Lifesaver! :)
Here is my class:
public class OrderedLinkedList extends LinkedListClass
{
protected LinkedListNode first; //variable to point to the first node
protected LinkedListNode last; //variable to point to the last node
protected int count; //variable to store the number of nodes
//in the list
//default constructor
public OrderedLinkedList()
{
super();
}
//copy constructor
public OrderedLinkedList(OrderedLinkedList otherList)
{
super(otherList);
}
//Method to determine whether searchItem is in the list
public boolean search(DataElement searchItem)
{
LinkedListNode current; //variable to traverse the list
boolean found;
current = first; //set current to point to the first node in the list
found = false; //set found to false
while(current != null && !found) //search the list
if(current.info.equals(searchItem)) //item is found
found = true;
else
current = current.link; //make the current point to
//the next node
if(found)
found = current.info.equals(searchItem);
return found;
}
public void insertNode(DataElement insertItem)
{
LinkedListNode current; //variable to traverse the list
LinkedListNode trailCurrent; //variable just before current
LinkedListNode newNode; //variable to create a node
boolean found;
newNode = new LinkedListNode(); //create the node
newNode.info = insertItem.getCopy(); //store newItem in the node
newNode.link = null; //set the link field of the node to null
if(first == null) //Case 1
{
first = newNode;
count++;
}
else
{
trailCurrent = first;
current = first;
found = false;
while(current != null && !found) //search the list
if(current.info.compareTo(insertItem) >= 0)
found = true;
else
{
trailCurrent = current;
}
if(current == first) //Case 2
{
newNode.link = first;
first = newNode;
count++;
}
else //Case 3
{
trailCurrent.link = newNode;
newNode.link = current;
count++;
}
}
}
public void deleteNode(DataElement deleteItem)
{
LinkedListNode current; //variable to traverse the list
LinkedListNode trailCurrent; //variable just before current
boolean found;
if(first == null) //Case 1; list is empty.
System.err.println("Cannot delete from an empty list.");
else
{
if(first.info.equals(deleteItem)) //Case 2; the first node is the
//node to be deleted
{
first = first.link;
count--;
}
else //search the list for the node with the given info
{
found = false;
trailCurrent = first; //set trailCurrent to point to
//the first node
current = first.link; //set current to point to the
//second node
while(current != null && !found)
{
if(current.info.compareTo(deleteItem) >= 0)
found = true;
else
{
trailCurrent = current;
current = current.link;
}
}
if(current == null) //Case 4; the list is not empty, but the
//item to be delete is not in the list
System.out.println("Item to be deleted is "
+ " not in the list.");
else
if(current.info.equals(deleteItem)) //item to be deleted
//is in the list
{
if(first == current) //Case 2
{
first = first.link;
count--;
}
else //Case 3; the item to be deleted is
//somewhere in the list
{
trailCurrent.link = current.link;
count--;
}
}
else //Case 4
System.out.println("Item to be deleted is "
+ " not in the list.");
}
}
}
}
Explanation / Answer
public void clear() {
Entry<E> e = header.next;
while (e != header) {
Entry<E> next = e.next;
e.next = e.previous = null;
e.element = null;
e = next;
}
header.next = header.previous = header;
size = 0;
modCount++;
}
public class LinkedList
{
// reference to the head node.
private Node head;
private int listCount;
// LinkedList constructor
public LinkedList()
{
// this is an empty list, so the reference to the head node
// is set to a new node with no data
head = new Node(null);
listCount = 0;
}
public void add(Object data)
// post: appends the specified element to the end of this list.
{
Node temp = new Node(data);
Node current = head;
// starting at the head node, crawl to the end of the list
while(current.getNext() != null)
{
current = current.getNext();
}
// the last node's "next" reference set to our new node
current.setNext(temp);
listCount++;// increment the number of elements variable
}
public void add(Object data, int index)
// post: inserts the specified element at the specified position in this list.
{
Node temp = new Node(data);
Node current = head;
// crawl to the requested index or the last element in the list,
// whichever comes first
for(int i = 1; i < index && current.getNext() != null; i++)
{
current = current.getNext();
}
// set the new node's next-node reference to this node's next-node reference
temp.setNext(current.getNext());
// now set this node's next-node reference to the new node
current.setNext(temp);
listCount++;// increment the number of elements variable
}
public Object get(int index)
// post: returns the element at the specified position in this list.
{
// index must be 1 or higher
if(index <= 0)
return null;
Node current = head.getNext();
for(int i = 1; i < index; i++)
{
if(current.getNext() == null)
return null;
current = current.getNext();
}
return current.getData();
}
public boolean remove(int index)
// post: removes the element at the specified position in this list.
{
// if the index is out of range, exit
if(index < 1 || index > size())
return false;
Node current = head;
for(int i = 1; i < index; i++)
{
if(current.getNext() == null)
return false;
current = current.getNext();
}
current.setNext(current.getNext().getNext());
listCount--; // decrement the number of elements variable
return true;
}
public int size()
// post: returns the number of elements in this list.
{
return listCount;
}
public String toString()
{
Node current = head.getNext();
String output = "";
while(current != null)
{
output += "[" + current.getData().toString() + "]";
current = current.getNext();
}
return output;
}
private class Node
{
// reference to the next node in the chain,
// or null if there isn't one.
Node next;
// data carried by this node.
// could be of any type you need.
Object data;
// Node constructor
public Node(Object _data)
{
next = null;
data = _data;
}
// another Node constructor if we want to
// specify the node to point to.
public Node(Object _data, Node _next)
{
next = _next;
data = _data;
}
// these methods should be self-explanatory
public Object getData()
{
return data;
}
public void setData(Object _data)
{
data = _data;
}
public Node getNext()
{
return next;
}
public void setNext(Node _next)
{
next = _next;
}
}
}
public class SinglyLinkedList {
…
public void removeFirst() {
if (head == null)
return;
else {
if (head == tail) {
head = null;
tail = null;
} else {
head = head.next;
}
}
}
public void removeLast() {
if (tail == null)
return;
else {
if (head == tail) {
head = null;
tail = null;
} else {
SinglyLinkedListNode previousToTail = head;
while (previousToTail.next != tail)
previousToTail = previousToTail.next;
tail = previousToTail;
tail.next = null;
}
}
}
public void removeNext(SinglyLinkedListNode previous) {
if (previous == null)
removeFirst();
else if (previous.next == tail) {
tail = previous;
tail.next = null;
} else if (previous == tail)
return;
else {
previous.next = previous.next.next;
}
}
}