Question

In java

Write a method public void printReverse() that prints the elements of a doubly linked list in reverse.

Write a method public void delete5FromTheEnd() which deletes the 5^th element from end of the list. Note that if you reach the end then you have to reverse the direction of counting.

In the main() method of the test class, create a randomly generated Doubly-Linked list of 10 Integers. Next, call the delete5FromTheEnd() method and print the lists iteratively until the list becomes empty. Make sure to print the list after each deletion.

For example, your list initially could be:

[ 3 1 2 5 8 7 ].

After deleting 5^th element from the end:

[ 3 1 2 5 8 7 ] => [ 3 2 5 8 7 ].

After deleting 5^th element again;

[ 3 2 5 8 7] => [ 2 5 8 7].

After deleting 5^th element again (counting in the reverse direction, then moving forward),

[ 2 5 8 7] => [ 2 8 7 ]

[2 8 7] => [2 8]

…

//**************************** DLL.java *******************************
// generic doubly linked list class

public class DLL<T> {
private DLLNode<T> head, tail;
public DLL() {
head = tail = null;
}
public boolean isEmpty() {
return head == null;
}
public void setToNull() {
head = tail = null;
}
public T firstEl() {
if (head != null)
return head.info;
else return null;
}
public void addToHead(T el) {
if (head != null) {
head = new DLLNode<T>(el,head,null);
head.next.prev = head;
}
else head = tail = new DLLNode<T>(el);
}
public void addToTail(T el) {
if (tail != null) {
tail = new DLLNode<T>(el,null,tail);
tail.prev.next = tail;
}
else head = tail = new DLLNode<T>(el);
}
public T deleteFromHead() {
if (isEmpty())
return null;
T el = head.info;
if (head == tail) // if only one node on the list;
head = tail = null;
else { // if more than one node in the list;
head = head.next;
head.prev = null;
}
return el;
}
public T deleteFromTail() {
if (isEmpty())
return null;
T el = tail.info;
if (head == tail) // if only one node on the list;
head = tail = null;
else { // if more than one node in the list;
tail = tail.prev;
tail.next = null;
}
return el;
}
public void printAll() {
for (DLLNode<T> tmp = head; tmp != null; tmp = tmp.next)
System.out.print(tmp.info + " ");
}
public T find(T el) {
DLLNode<T> tmp;
for (tmp = head; tmp != null && !tmp.info.equals(el); tmp = tmp.next);
if (tmp == null)
return null;
else return tmp.info;
}
}

//**************************** DLLNode.java *******************************
// node of generic doubly linked list class

public class DLLNode<T> {
public T info;
public DLLNode<T> next, prev;
public DLLNode() {
next = null; prev = null;
}
public DLLNode(T el) {
info = el; next = null; prev = null;
}
public DLLNode(T el, DLLNode<T> n, DLLNode<T> p) {
info = el; next = n; prev = p;
}
}

************************DLLTest.java*********************************

public class DLLTest {
   public static void main(String[] args) {
       DLL<String> test = new DLL<String>();
       for(int i = 0; i < 5; i++)
           test.addToTail("a" + i);
       test.printAll();
   }
}

Answer 1

As it is written in the problem I have written both the public void printReverse() and public void delete5FromTheEnd() in the DLL class. Also, I created a linked list with random integer using Random class and integer range between 0 to 100. After that, I repeatedly called delete5FromTheEnd() until the list becomes empty.

In the below code I have bold all text that has been added by me in your given code.

Code:-

// generic doubly linked list class
public class DLL<T>
{
private DLLNode<T> head, tail;
public DLL()
{
head = tail = null;
}
public boolean isEmpty()
{
return head == null;
}
public void setToNull()
{
head = tail = null;
}
public T firstEl()
{
if (head != null)
return head.info;
else return null;
}
public void addToHead(T el)
{
if (head != null)
{
head = new DLLNode<T>(el,head,null);
head.next.prev = head;
}
else head = tail = new DLLNode<T>(el);
}
public void addToTail(T el)
{
if (tail != null)
{
tail = new DLLNode<T>(el,null,tail);
tail.prev.next = tail;
}
else head = tail = new DLLNode<T>(el);
}
public T deleteFromHead()
{
if (isEmpty())
return null;
T el = head.info;
if (head == tail) // if only one node on the list;
head = tail = null;
else
{ // if more than one node in the list;
head = head.next;
head.prev = null;
}
return el;
}
public T deleteFromTail()
{
if (isEmpty())
return null;
T el = tail.info;
if (head == tail) // if only one node on the list;
head = tail = null;
else
{ // if more than one node in the list;
tail = tail.prev;
tail.next = null;
}
return el;
}
public void printAll()
{
for (DLLNode<T> tmp = head; tmp != null; tmp = tmp.next)
System.out.print(tmp.info + " ");
}
public T find(T el)
{
DLLNode<T> tmp;
for (tmp = head; tmp != null && !tmp.info.equals(el); tmp = tmp.next);
if (tmp == null)
return null;
else return tmp.info;
}
public void printReverse()
{
DLLNode<T> temp=tail;
for (; temp!=null;temp=temp.prev)
System.out.print(temp.info + " ");
}
  
//Function created to delete 5th node from the last
public void delete5FromTheEnd()
{
//if no element in the list than nothing to delete
if(head==null || tail==null)
return;
  
//if linked list have only one element than setting head and tail to null after removing that element
if(head.equals(tail))
{
head=null;
tail=null;
return;
}
  
//storing end of the list so that we can start from counting from last
DLLNode<T> temp=tail;

//side store the direction in which we are moving it will start in rev
//and it changes when we reach first element to forward
String side="rev";
  
//counter to find out the 5th element of the list
int counter=1;
  
//loop runs until find out 5th element
while(counter!=5)
{
//counter increases for each node
counter=counter+1;
if(temp.equals(head))
{
//if we reach first element than we change direction of moving to forward
side="for";
}
else if(temp.equals(tail))
{
//if we reach last element than we change direction of moving to reverse
side="rev";
}
  
  
//if side is equal to rev we move backwards else move forwards
if(side.equals("rev"))
{
temp=temp.prev;
}
else
{
temp=temp.next;
}
}
  
//deleting the node by changing the value of the pointers
if(temp.equals(head))
{
deleteFromHead();
}
else if(temp.equals(tail))
{
deleteFromTail();
}
else
{
(temp.prev).next=temp.next;
(temp.next).prev=temp.prev;
}
}
}

**************************** DLLNode.java *******************************
// node of generic doubly linked list class
public class DLLNode<T>
{
public T info;
public DLLNode<T> next, prev;
public DLLNode()
{
next = null; prev = null;
}
public DLLNode(T el)
{
info = el; next = null; prev = null;
}
public DLLNode(T el, DLLNode<T> n, DLLNode<T> p)
{
info = el; next = n; prev = p;
}
}

********************************DLLTest.java******************************

import java.util.Random;
public class DLLTest
{
public static void main(String[] args)
{
//creating instance of random class
Random random=new Random();
  
//creating doubly linked list of integers
DLL<Integer> test = new DLL<Integer>();

//inserting 10 random generated integers in range 0 to 100
for(int i = 0; i < 10; i++)
test.addToTail(random.nextInt(100));
//printing linked list
System.out.println("Linked List:- ");
test.printAll();
System.out.println("");
System.out.println("Printing Linked list in reverse:- ");
test.printReverse();

System.out.println("");
System.out.println("Deleting 5th Element Until List become empty:-");
test.printAll();
System.out.println("");
while(!test.isEmpty())
{
test.delete5FromTheEnd();
test.printAll();
System.out.println("");
}
}
}

Output:-