1) In this lab, you will write generic DoublyLinkedListE> class. DoublyLinkedLis

Question

1) In this lab, you will write generic DoublyLinkedListE> class. DoublyLinkedList will contain DoublyNode objects which is given for you in piazza. The class will contain the methods below -head:Node -tail:Node -size:int Il head node of the list (or null if empty) II last node of the list (or null if empty) Il number of nodes in the list DoublyLinkedList) II constructs an initially empty list +size):int tisEmpty0:boolean ITests whether the linked list is empty +first(0:E +last):E +addFirst (E)void lIAdds an element to the front of the list. +addLast(E):void lIAdds an element to the end of the list +removeFirst):E I/Removes and returns the first element of the list +removeLast)E I/Removes and returns the last element of the list. +equals(Object):boolean Ilyou will overwrite Object class' equals method and you will check if two SinglyLinkedList object is equal or not /Returns the number of elements in the linked list /Returns (but does not remove) the first element of the list /Returns (but does not remove) the last element of the list +toString0:String /Produces a string representation of the contents of the list. +addBetween(E, DoublyNode, DoublyNode E>)void lAdds an element to the linked list in between the given nodes.The given predecessor and successor should be neighboring each other prior to the call. +remove(DoublyNode E>E I/Removes the given node from the list and returns its element +toString):String Produces a string representation of the contents of the list 2) Test all the methods in main class 3)Sort a DoublyLinkedList object. If E is String, sort elements according to alphabetical order. If E is Integer sort increasing order. (Hint: use Comparable interface.)

Explanation / Answer

import java.util.Scanner;

class Node
{
protected int data;
protected Node next, prev;

public Node() // constructor
{
next = null;
prev = null;
data = 0;
}
  
public Node(int d, Node n, Node p) // constructor
{
data = d;
next = n;
prev = p;
}
  
public void setLinkNext(Node n) // function to set link to next node.
{
next = n;
}
  
public void setLinkPrev(Node p) // Function to set link to previous node.
{
prev = p;
}   
  
public Node getLinkNext() // Funtion to get link to next node.
{
return next;
}
  
public Node getLinkPrev() // Function to get link to previous node.
{
return prev;
}
  
public void setData(int d) // Function to set data to node.
{
data = d;
}
  
public int getData() // Function to get data from node.
{
return data;
}
}

class linkedList // defining the class linked list in which we will apply all our functions.
{
protected Node start;
protected Node end ;
public int size;

public linkedList() // Constructor
{
start = null;
end = null;
size = 0;
}
public boolean isEmpty() // Function to check if list is empty.
{
return start == null;
}
public int getSize() // Function to get size of list.
{
return size;
}
public void insertAtStart(int val) // Function to insert element at begining.
{
Node nptr = new Node(val, null, null);   
if(start == null)
{
start = nptr;
end = start;
}
else
{
start.setLinkPrev(nptr);
nptr.setLinkNext(start);
start = nptr;
}
size++;
}
public void insertAtEnd(int val)
{
Node nptr = new Node(val, null, null);   
if(start == null)
{
start = nptr;
end = start;
}
else
{
nptr.setLinkPrev(end);
end.setLinkNext(nptr);
end = nptr;
}
size++;
}
public void insertAtPos(int val , int pos)
{
Node nptr = new Node(val, null, null);   
if (pos == 1)
{
insertAtStart(val);
return;
}   
Node ptr = start;
for (int i = 2; i <= size; i++)
{
if (i == pos)
{
Node tmp = ptr.getLinkNext();
ptr.setLinkNext(nptr);
nptr.setLinkPrev(ptr);
nptr.setLinkNext(tmp);
tmp.setLinkPrev(nptr);
}
ptr = ptr.getLinkNext();   
}
size++ ;
}
public void deleteAtPos(int pos)
{   
if (pos == 1)
{
if (size == 1)
{
start = null;
end = null;
size = 0;
return;
}
start = start.getLinkNext();
start.setLinkPrev(null);
size--;
return ;
}
if (pos == size)
{
end = end.getLinkPrev();
end.setLinkNext(null);
size-- ;
}
Node ptr = start.getLinkNext();
for (int i = 2; i <= size; i++)
{
if (i == pos)
{
Node p = ptr.getLinkPrev();
Node n = ptr.getLinkNext();

p.setLinkNext(n);
n.setLinkPrev(p);
size-- ;
return;
}
ptr = ptr.getLinkNext();
}   
}   
public void display() // Function to display status of list.
{
System.out.print(" Doubly Linked List = ");
if (size == 0)
{
System.out.print("empty ");
return;
}
if (start.getLinkNext() == null)
{
System.out.println(start.getData() );
return;
}
Node ptr = start;
System.out.print(start.getData()+ " <-> ");
ptr = start.getLinkNext();
while (ptr.getLinkNext() != null)
{
System.out.print(ptr.getData()+ " <-> ");
ptr = ptr.getLinkNext();
}
System.out.print(ptr.getData()+ " ");
}
}

public class DoublyLinkedList // Doubly linkedList class.
{   
public static void main(String[] args)
{   
Scanner scan = new Scanner(System.in);
linkedList list = new linkedList(); // creating object of linked list.
System.out.println("Doubly Linked List Test ");   
char ch;
do
{
System.out.println(" Doubly Linked List Operations ");
System.out.println("1. insert at begining");
System.out.println("2. insert at end");
System.out.println("3. insert at position");
System.out.println("4. delete at position");
System.out.println("5. check empty");
System.out.println("6. get size");

int choice = scan.nextInt();   
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
list.insertAtStart( scan.nextInt() );
break;   
case 2 :
System.out.println("Enter integer element to insert");
list.insertAtEnd( scan.nextInt() );
break;
case 3 :
System.out.println("Enter integer element to insert");
int num = scan.nextInt() ;
System.out.println("Enter position");
int pos = scan.nextInt() ;
if (pos < 1 || pos > list.getSize() )
System.out.println("Invalid position ");
else
list.insertAtPos(num, pos);
break;   
case 4 :
System.out.println("Enter position");
int p = scan.nextInt() ;
if (p < 1 || p > list.getSize() )
System.out.println("Invalid position ");
else
list.deleteAtPos(p);
break;
case 5 :
System.out.println("Empty status = "+ list.isEmpty());
break;   
case 6 :
System.out.println("Size = "+ list.getSize() +" ");
break;
default :
System.out.println("Wrong Entry ");
break;
}   
/* Display List */
list.display();
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);   

} while (ch == 'Y'|| ch == 'y');
}
}

Run the above code, it includes all the criteria that you mentioned. you can run this code on any java compiler.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.