Question

Ex1) Download the code from the theory section, you will find zipped file contains the code of Singly linked list and Doubly linked list, in addition to a class Student.

In Class SignlyLinkedList,

1. There is a method display, what does this method do?

2. In class Test, and in main method, create a singly linked list objet, test the methods of the list.

3. To class Singly linked list, add the following methods:

a- Method get(int n), it returns the elements in the node number n, assume the first node number is 1. You need to check that n is within the range of nodes in the list, otherwise method get returns null.

What is the complexity of your method? Test the method in main.

b- Method insertAfter(int n, E e), its return type is void, it inserts element e in a new node after the node number n, assume the first node number is 1. You need to check that n is within the range of nodes in the list, otherwise through an exception.

What is the complexity of your method?

Test the method in main.

c- Method remove(int n): it removes the node number n, and returns the element in that node, assuming the first node number is 1. You need to check that n is within the range of nodes in the list, otherwise method get returns null.

What is the complexity of your method?

Test the method in main.

d- Method reverse( ): it has void return type. It reverse the order of the elements in the singlylinked list.

What is the complexity of your method?

Test the method in main.

Ex2) In Class DoublyLinkedList

1. There are two methods printForward, printBackward, what do they do?

2. In class Test, and in main method, create a doubly linked list objet, test the methods of the list.

4. To class Doubly linked list, add the following methods:

e- Method get(int n), it returns the elements in the node number n, assume the first node number is 1. You need to check that n is within the range of nodes in the list, otherwise method get returns null.

To make your code more efficient, you should start from the end (header or trailer) that is closer to the target node.

What is the complexity of your method?

Test the method in main.

f- Method insertAfter(int n, E e), its return type is void, it inserts element e in a new node after the node number n, assume the first node number is 1. You need to check that n is within the range of nodes in the list, otherwise through an exception. . To make your code more efficient, you should start from the end (header or trailer) that is closer to the target node.

What is the complexity of your method?

Test the method in main.

g- Method remove(int n): it removes the node number n, and returns the element in that node, assuming the first node number is 1. You need to check that n is within the range of nodes in the list, otherwise method get returns null. To make your code more efficient, you should start from the end (header or trailer) that is closer to the target node.

What is the complexity of your method?

Test the method in main.

Assignment:

To class DoublyLinedList, add method remove(E e) which removes all nodes that has data e. This method has void return type.

doublylinkedlist class:

package doubly;

public class DoublyLinkedList <E>{
   private Node<E> header;
   private Node<E> trailer;
   private int size=0;
   public DoublyLinkedList() {
       header=new Node<>(null,null,null);
       trailer=new Node<>(null,header,null);
       header.setNext(trailer);
   }
   public int size() { return size;}
   public boolean isEmpty() {return size==0;}
   public E first()
   {
   if (isEmpty()) return null;
       return header.getNext().getData();
   }
   public E last()
   {
       if (isEmpty()) return null;
           return trailer.getPrev().getData();
   }
  
   private void addBetween(E e, Node<E> predecessor, Node<E> successor)
   {
       Node<E> newest=new Node<>(e,predecessor,successor);
       predecessor.setNext(newest);
       successor.setPrev(newest);
       size++;
      
   }
   private E remove(Node<E> node)
   {
       Node<E> predecessor=node.getPrev();
       Node<E> successor=node.getNext();
       predecessor.setNext(successor);
       successor.setPrev(predecessor);
       size--;
       return node.getData();
   }
   public void addFirst(E e){
       addBetween(e,header,header.getNext());
   }
   public void addLast(E e){
       addBetween(e,trailer.getPrev(),trailer);
   }
  
   public E removeFirst(){
       if(isEmpty()) return null;
       return remove(header.getNext());
   }
  
   public E removeLast()
   {
   if(isEmpty()) return null;
   return remove(trailer.getPrev());
   }
   public void printForward()
   {
       for (Node<E> tmp=header.getNext();tmp!=trailer;tmp=tmp.getNext())
           System.out.println(tmp.getData());
   }
  
   public void printBackward()
   {
       for (Node<E> tmp=trailer.getPrev();tmp!=header;tmp=tmp.getPrev())
           System.out.println(tmp.getData());
   }
  
  
}

node class:

package doubly;

public class Node <E>{
   private E data;
   private Node<E> prev;
   private Node<E> next;
  
   public Node(E d, Node<E> p,Node<E> n)
   {
   data=d;
   prev=p;
   next=n;
   }
   public E getData() { return data; }
   public Node<E> getNext(){ return next; }
   public Node<E> getPrev(){ return prev; }
   public void setNext(Node<E> n) { next=n;}
   public void setPrev(Node<E> p) { prev=p;}

}

student class:

package doubly;

public class Student {
private int id;
private String name;
public Student(int id, String name) {
   super();
   this.id = id;
   this.name = name;
}
public int getId() {
   return id;
}
public void setId(int id) {
   this.id = id;
}
public String getName() {
   return name;
}
public void setName(String name) {
   this.name = name;
}
@Override
public String toString() {
   return "[id=" + id + ", name=" + name + "]";
}

}

test class:

package doubly;

public class Test {
public static void main(String arg[])
{
   DoublyLinkedList<Student> myList=new DoublyLinkedList<>();
   myList.addFirst(new Student(1,"Ahmed"));
   myList.addFirst(new Student(2,"Khaled"));
   myList.addLast(new Student(3,"Ali"));
   myList.removeLast();
   myList.printForward();
  
  
  
  
}
}

Answer 1

Assignment Solution:

Doublylinkedlist class:

public class DoublyLinkedList <E>{
private Node<E> header;
private Node<E> trailer;
private int size=0;
public DoublyLinkedList() {
header=new Node<>(null,null,null);
trailer=new Node<>(null,header,null);
header.setNext(trailer);
}
public int size() { return size;}
public boolean isEmpty() {return size==0;}
public E first()
{
if (isEmpty()) return null;
return header.getNext().getData();
}
public void remove(Node<E> e)
{
if (isEmpty()) return null;
Node<E> next;
for (Node<E> tmp=header.getNext();tmp!=trailer; )
{

if (tmp.getData() == e.getData())
{

next = tmp.getNext();
  
header = remove(tmp);
  
tmp = next;
}
  
else
tmp = tmp.getNext();
  
}
  

  
}
public E last()
{
if (isEmpty()) return null;
return trailer.getPrev().getData();
}
  
private void addBetween(E e, Node<E> predecessor, Node<E> successor)
{
Node<E> newest=new Node<>(e,predecessor,successor);
predecessor.setNext(newest);
successor.setPrev(newest);
size++;
  
}
private E remove(Node<E> node)
{
Node<E> predecessor=node.getPrev();
Node<E> successor=node.getNext();
predecessor.setNext(successor);
successor.setPrev(predecessor);
size--;
return node.getData();
}
public void addFirst(E e){
addBetween(e,header,header.getNext());
}
public void addLast(E e){
addBetween(e,trailer.getPrev(),trailer);
}
  
public E removeFirst(){
if(isEmpty()) return null;
return remove(header.getNext());
}
  
public E removeLast()
{
if(isEmpty()) return null;
return remove(trailer.getPrev());
}
public void printForward()
{
for (Node<E> tmp=header.getNext();tmp!=trailer;tmp=tmp.getNext())
System.out.println(tmp.getData());
}
  
public void printBackward()
{
for (Node<E> tmp=trailer.getPrev();tmp!=header;tmp=tmp.getPrev())
System.out.println(tmp.getData());
}
  
  
}