Please follow the instruction in the bottom. * Week 2 lab - exercise 1: * * a si
ID: 3873571 • Letter: P
Question
Please follow the instruction in the bottom.
* Week 2 lab - exercise 1: *
* a simple LinkedList class *
*******************************/
/**
* Class implementing a linked list.
*/
public class LinkedList
{
private Node first; //dummy header node
/**
* Initializes the list to empty creating a dummy header node.
*/
public LinkedList()
{
first = new Node();
}
/**
* Determines whether the list is empty
*
* return true if the list is empty, false otherwise
*/
public boolean isEmpty()
{
return (first.getNext() == null);
}
/**
* Prints the list elements.
*/
public void display()
{
Node current = first.getNext();
while (current != null)
{
System.out.print(current.getInfo() + " ");
current = current.getNext();
}
System.out.println();
}
/**
* Adds the element x to the beginning of the list.
*
* param x element to be added to the list
*/
public void add(int x)
{
Node p = new Node();
p.setInfo(x);
p.setNext(first.getNext());
first.setNext(p);
}
/**
* Deletes an item from the list. Only the first occurrence of the item in
* the list will be removed.
*
* param x element to be removed.
*/
public void remove(int x)
{
Node old = first.getNext(),
p = first;
//Finding the reference to the node before the one to be deleted
boolean found = false;
while (old != null && !found)
{
if (old.getInfo() == x)
{
found = true;
} else
{
p = old;
old = p.getNext();
}
}
//if x is in the list, remove it.
if (found)
{
p.setNext(old.getNext());
}
}
}
/******************************
* Week 2 lab - exercise 1: *
* a simple LinkedList class *
*******************************/
public class Main
{
public static void main(String args[])
{
LinkedList intList = new LinkedList();
System.out.print("List of numbers before list creation: ");
for (int i =0; i < 10; i++)
{
int info = (int)(Math.random()*10);
System.out.print(info + " ");
intList.add(info);
}
System.out.print(" List of numbers after list creation: ");
intList.display();
}
}
/******************************
* Week 2 lab - exercise 1: *
* a simple LinkedList class *
*******************************/
/**
* Linked list node.
*/
public class Node
{
private int info; //element stored in this node
private Node next; //link to next node
/**
* Initializes this node setting info to 0 and next to null
*/
public Node()
{
info = 0;
next = null;
}
/**
* Sets the value for this node
*
* param i the desired value for this node
*/
public void setInfo(int i)
{
info = i;
}
/**
* Sets the link to the next node
*
* param l node reference
*/
public void setNext(Node l)
{
next = l;
}
/**
* Returns the value in this node
*
* return the value in this node
*/
public int getInfo()
{
return info;
}
/**
* Returns the link to the next node
*
* return link to the next node
*/
public Node getNext()
{
return next;
}
}
In Exercise 2, modify the code in Exercise 1 so that each list entry references both the entry after and the entry before (to do this Node class will need to both next and previous links, in addition to info). With this in place you can
Write methods that Add entries to the list from either front or end of list; and then
Make for loops that will print out your list from either beginning to end OR end to beginning of the list
as tests of doubly-linked list action.
Explanation / Answer
PROGRAM CODE:
Node.java
package linkedlist;
/******************************
* Week 2 lab - exercise 1: *
* a simple LinkedList class *
*******************************/
/**
* Linked list node.
*/
public class Node
{
private int info; //element stored in this node
private Node next; //link to next node
private Node prev;
/**
* Initializes this node setting info to 0 and next to null
*/
public Node()
{
info = 0;
next = null;
prev = null;
}
/**
* Sets the value for this node
*
* param i the desired value for this node
*/
public void setInfo(int i)
{
info = i;
}
/**
* Sets the link to the next node
*
* param l node reference
*/
public void setNext(Node l)
{
next = l;
}
/**
* Sets the link to the previous node
*
* param l node reference
*/
public void setPrevious(Node l)
{
prev = l;
}
/**
* Returns the value in this node
*
* return the value in this node
*/
public int getInfo()
{
return info;
}
/**
* Returns the link to the next node
*
* return link to the next node
*/
public Node getNext()
{
return next;
}
/**
* Returns the link to the prev node
*
* return link to the prev node
*/
public Node getPrevious()
{
return prev;
}
}
LinkedList.java
package linkedlist;
/* Week 2 lab - exercise 1: *
* a simple LinkedList class *
*******************************/
/**
* Class implementing a linked list.
*/
public class LinkedList
{
/**
* first node to store the beginning of the list
* last node to store the end of the list
*/
private Node first;
private Node last;
/**
* Initializes the list to empty creating a dummy header node.
*/
public LinkedList()
{
first = null;
last = null;
}
/**
* Determines whether the list is empty
*
* return true if the list is empty, false otherwise
*/
public boolean isEmpty()
{
return (first == null);
}
/**
* Prints the list elements.
*/
public void display()
{
Node current = first;
while (current != null)
{
System.out.print(current.getInfo() + " ");
current = current.getNext();
}
System.out.println();
}
/**
* Prints the list elements in the reverse order
*/
public void reverseDisplay()
{
Node current = last;
while (current != null)
{
System.out.print(current.getInfo() + " ");
current = current.getPrevious();
}
System.out.println();
}
/**
* Adds the element x to the beginning of the list.
*
* param x element to be added to the list
*/
public void addToFront(int x)
{
Node p = new Node();
p.setInfo(x);
if(isEmpty())
{
first = p;
last = p;
}
else
{
p.setNext(first);
first.setPrevious(p);
first = p;
}
}
/**
* Adds the element x to the end of the list.
*
* param x element to be added to the list
*/
public void addToBack(int x)
{
Node p = new Node();
p.setInfo(x);
if(isEmpty())
{
first = p;
last = p;
}
else
{
last.setNext(p);
p.setPrevious(last);
last = p;
}
}
/**
* Deletes an item from the list. Only the first occurrence of the item in
* the list will be removed.
*
* param x element to be removed.
*/
public void remove(int x)
{
Node old = first.getNext(),
p = first;
//Finding the reference to the node before the one to be deleted
boolean found = false;
while (old != null && !found)
{
if (old.getInfo() == x)
{
found = true;
} else
{
p = old;
old = p.getNext();
}
}
//if x is in the list, remove it.
if (found)
{
p.setNext(old.getNext());
}
}
}
Main.java
package linkedlist;
/******************************
* Week 2 lab - exercise 1: *
* a simple LinkedList class *
*******************************/
public class Main
{
public static void main(String args[])
{
LinkedList intList = new LinkedList();
System.out.print("List of numbers before list creation: ");
for (int i =0; i < 10; i++)
{
int info = (int)(Math.random()*10);
System.out.print(info + " ");
intList.addToFront(info);
}
System.out.print(" List of numbers after list creation (adding to front): ");
intList.display();
System.out.print("List of numbers after list creation (in reverse): ");
intList.reverseDisplay();
LinkedList intList2 = new LinkedList();
System.out.print(" Another List of numbers before list creation: ");
for (int i =0; i < 10; i++)
{
int info = (int)(Math.random()*10);
System.out.print(info + " ");
intList2.addToBack(info);
}
System.out.print(" List of numbers after list creation (adding to back): ");
intList2.display();
System.out.print("List of numbers after list creation (in reverse): ");
intList2.reverseDisplay();
}
}
OUTPUT:
List of numbers before list creation: 5 2 0 2 1 1 5 9 2 4
List of numbers after list creation (adding to front): 4 2 9 5 1 1 2 0 2 5
List of numbers after list creation (in reverse): 5 2 0 2 1 1 5 9 2 4
Another List of numbers before list creation: 6 0 7 3 0 2 8 1 9 8
List of numbers after list creation (adding to back): 6 0 7 3 0 2 8 1 9 8
List of numbers after list creation (in reverse): 8 9 1 8 2 0 3 7 0 6