Question

PLEASE DONT FORGET TO SOLVE THE ASSIGNMENT QUESTION MOST IMP:

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.

doubly package:

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();
  
  
  
  
}
}

singly package:

node class:

package Singly;

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

}

SinglyLinkedList class:

package Singly;

public class SinglyLinkedList <E>{
   private Node<E> head=null;
   private Node<E> tail=null;
   private int size=0;
   public SinglyLinkedList() { }
   public int size() { return size;}
   public boolean isEmpty() {return size==0;}
   public E first()
   {
   if (isEmpty()) return null;
       return head.getData();
   }
   public E last()
   {
       if (isEmpty()) return null;
           return tail.getData();
   }
   public void addFirst(E e)
   {
   head=new Node<>(e,head);
   if(size==0)
       tail=head;
   size++;

   }
   public void addLast(E e)
   {
   Node<E> newest=new Node<>(e,null);
   if(isEmpty())
       head=newest;
   else
       tail.setNext(newest);

   tail=newest;
   size++;
   }

   public E removeFirst()
   {
       if(isEmpty()) return null;
       E answer=head.getData();
       head=head.getNext();
       size--;
       if (size==0)
           tail=null;
       return answer;
   }
   public E removeLast()
   {
   if(isEmpty()) return null;
   E answer=tail.getData();
   if (head==tail)
       head=tail=null;
   else
   {
   Node<E> tmp=head;
   while (tmp.getNext()!=tail)
       tmp=tmp.getNext();
   tmp.setNext(null);
   tail=tmp;
   }
   size--;
   return answer;
   }
public void display() {
   for (Node<E> tmp=head;tmp!=null;tmp=tmp.getNext())
       System.out.println(tmp.getData());
}
}

Student class:

package Singly;

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 Singly;

public class Test {
public static void main(String arg[])
{
   SinglyLinkedList<Student> myList=new SinglyLinkedList<>();
   myList.addFirst(new Student(1,"Ahmed"));
   myList.addFirst(new Student(2,"Khaled"));
   myList.addLast(new Student(3,"Ali"));
   Student x=myList.removeLast();
  
   myList.display();
   System.out.println(myList.size());
  
}
}

Answer 1

Ex1) ::->
Answer 1:
display method prints the all the nodes(data) present in the list to the console. The steps are :
   Define a tmp node which initially points to the head of the list.
   Traverse through the list till tmp points to null.
   Display each node by making tmp to point to node next to it in each iteration.
Answer 2:
SinglyLinkedList<Student> myList=new SinglyLinkedList<>();
myList.addFirst(new Student(1,"Ahmed"));
myList.addFirst(new Student(2,"Khaled"));
myList.addLast(new Student(3,"Ali"));
Student x=myList.removeLast();
myList.display();
System.out.println(myList.size());
Answer 3.a.:
   Time complexity : o(n)
   SinglyLinkedList.java : Add below method
   public E get(int n) {
       if (n < 1 || n > size())
           return null;
       Node<E> tmp = head;
       int count = 1;
       while (tmp != null) {
           if (count == n)
               return tmp.getData();
           count++;
           tmp = tmp.getNext();
       }
       return null;
   }
   Test.java: Add below statement
   System.out.println(myList.get(2));
Answer 3.b.:
   Time complexity : o(n)
   SinglyLinkedList.java : Add below method
   public void insertAfter(int n, E e) throws Exception {
       if (n < 0 || n > size) {
           System.out.println("Valid Position range : 0 to " + size);
           throw new Exception();
       }
       Node<E> newest = new Node<>(e, null);
       if (n == 0) {
           addFirst(newest.getData());
       } else if (n == size) {
           addLast(newest.getData());
       } else {
           Node<E> current = head;
           Node<E> previous = null;
           int i = 1;
           while (i <= n) {
               previous = current;
               current = current.getNext();
               if (current == null) {
                   break;
               }
               i++;
           }
           newest.setNext(current);
           previous.setNext(newest);
           size ++;
       }
   }
   Test.java: Add below statement
   myList.insertAfter(2, new Student(4,"Stud-4"));
   myList.display();
Answer 3.c.:
   Time complexity : o(n)
   SinglyLinkedList.java : Add below method
   public E remove(int n) {
       if (n < 1 || n > size)
           return null;
       if (n == 1) {
           return removeFirst();
       } else if ( n == size) {
           return removeLast();
       }
       Node<E> current = head;
       Node<E> previous = null;
       for (int i = 1; current != null && i < n ; i++) {
           previous = current;
           current = current.getNext();
       }
       //Node<E> answer = temp.getNext();
       previous.setNext(current.getNext());
       size--;
       return current.getData();
   }
   Test.java: Add below statement
   System.out.println(myList.remove(2));
   myList.display();
Answer 3.d.:
   Time complexity : o(n)
   SinglyLinkedList.java : Add below method
   public void reverse() {
       if (head == null || head.getNext() == null) {
           return ;
       }
       tail = head;
       Node<E> prev = null;
Node<E> current = head;
Node<E> next = null;
while (current != null) {
next = current.getNext();
current.setNext(prev);
prev = current;
current = next;
}
head = prev;
   }
   Test.java: Add below statement
   myList.reverse();
   myList.display();
  
  

Ex2) :
Ans 1. :
   printForward method : Traverses the List from head to tail and print data
   printBackward method : Traverses the List from tail to head and print data
Ans 2. :
   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();

Ans 4.e. :
   Time complexity : o(n/2)
   DoublyLinkedList.java : Add below method
   public E get(int n) {
       if (n < 1 || n > size)
           return null;
       int mid = size / 2;
       if (n <= mid+1) {
           System.out.println("head");
           Node<E> tmp = header;
           int count = 1;
           while (tmp != null) {
               if (count == n)
                   return tmp.getNext().getData();
               count++;
               tmp = tmp.getNext();
           }
       } else {
           System.out.println("trail");
           Node<E> tmp = trailer;
           int count = size;
           while (tmp != null) {
               if (count == n)
                   return tmp.getPrev().getData();
               count--;
               tmp = tmp.getPrev();
           }
       }
       return null;
   }
  
   Test.java: Add below statement
   System.out.println(myList.get(2));
  
Ans 4.f. :
   Time complexity : o(n/2)
   DoublyLinkedList.java : Add below method
   public void insertAfter(int n, E e) throws Exception {
       if (n < 0 || n > size) {
           System.out.println("Valid Position range : 0 to " + size);
           throw new Exception();
       }
       //Node<E> newest = new Node<>(e, null, null);
       if (n == 0) {
           addFirst(e);
       } else if (n == size) {
           addLast(e);
       } else {
           int mid = size / 2;
           if (n <= mid+1) {
               System.out.println("head");
               Node<E> current = header.getNext();
               Node<E> previous = null;
               int i = 1;
               while (i <= n) {
                   previous = current;
                   current = current.getNext();
                   if (current == null) {
                       break;
                   }
                   i++;
               }
               /*newest.setPrev(previous);
               newest.setNext(current);              
               previous.setNext(newest);
               size++;*/
               /*predecessor.setNext(newest);
               successor.setPrev(newest);*/
               addBetween(e, previous, previous.getNext());
           } else {
               System.out.println("trail");
               Node<E> current = trailer.getPrev();
               Node<E> previous = null;
               int i = size;
               while (i >= n) {
                   previous = current;
                   current = current.getPrev();
                   if (current == null) {
                       break;
                   }
                   i--;
               }
               addBetween(e, previous, previous.getNext());              
           }          
          
       }
   }
  
   Test.java: Add below statement
   try {
           myList.insertAfter(4,new Student(7, "Stud-6"));
           myList.printForward();
       } catch (Exception e) {
           e.printStackTrace();
       }
      
Ans 4.g. :
   Time complexity : o(n/2)
   DoublyLinkedList.java : Add below method
   public E remove(int n) {
       if (n < 1 || n > size)
           return null;
       if (n == 0) {
           return removeFirst();
       } else if (n == size) {
           return removeLast();
       } else {
           int mid = size / 2;
           if (n <= mid + 1) {
               System.out.println("head");
               Node<E> current = header.getNext();
               Node<E> previous = null;
               int i = 1;
               while (i <= n) {
                   previous = current;
                   current = current.getNext();
                   if (current == null) {
                       break;
                   }
                   i++;
               }
               previous.getPrev().setNext(current);
               size--;
               return previous.getData();
           } else {
               System.out.println("trail");
               Node<E> current = trailer.getPrev();
               Node<E> previous = null;
               int i = size;
               while (i >= n) {
                   previous = current;
                   current = current.getPrev();
                   if (current == null) {
                       break;
                   }
                   i--;
               }
               current.setNext(previous.getNext());
               size--;
               return previous.getData();
           }
       }
   }  
   Test.java: Add below statement
   System.out.println("Removed Data : " + myList.remove(2));
   myList.printForward();
  
Ans Assignment:
   public void remove(E e) {
       Node<E> current = header.getNext();
       Node<E> next;
       int n = 1;
       int i = 0;
       while (current != null) {
           if (current.getData() != null && current.getData().equals(e)) {
               next = current.getNext();
               current = next;
               remove(n-i);
               i++;              
           } else {
               current = current.getNext();
           }
           n++;
       }
   }
-------------------------------------------------------------------
Package doubly files
---------------------------------------------------------------------
DoublyLinkedList.java

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());
   }

   public E get(int n) {
       if (n < 1 || n > size)
           return null;
       int mid = size / 2;
       if (n <= mid + 1) {
           System.out.println("head");
           Node<E> tmp = header;
           int count = 1;
           while (tmp != null) {
               if (count == n)
                   return tmp.getNext().getData();
               count++;
               tmp = tmp.getNext();
           }
       } else {
           System.out.println("trail");
           Node<E> tmp = trailer;
           int count = size;
           while (tmp != null) {
               if (count == n)
                   return tmp.getPrev().getData();
               count--;
               tmp = tmp.getPrev();
           }
       }
       return null;
   }

   public void insertAfter(int n, E e) throws Exception {
       if (n < 0 || n > size) {
           System.out.println("Valid Position range : 0 to " + size);
           throw new Exception();
       }
       if (n == 0) {
           addFirst(e);
       } else if (n == size) {
           addLast(e);
       } else {
           int mid = size / 2;
           if (n <= mid + 1) {
               System.out.println("head");
               Node<E> current = header.getNext();
               Node<E> previous = null;
               int i = 1;
               while (i <= n) {
                   previous = current;
                   current = current.getNext();
                   if (current == null) {
                       break;
                   }
                   i++;
               }
               addBetween(e, previous, previous.getNext());
           } else {
               System.out.println("trail");
               Node<E> current = trailer.getPrev();
               Node<E> previous = null;
               int i = size;
               while (i >= n) {
                   previous = current;
                   current = current.getPrev();
                   if (current == null) {
                       break;
                   }
                   i--;
               }
               addBetween(e, previous, previous.getNext());
           }
       }
   }

   public E remove(int n) {
       if (n < 1 || n > size)
           return null;
       if (n == 0) {
           return removeFirst();
       } else if (n == size) {
           return removeLast();
       } else {
           int mid = size / 2;
           if (n <= mid + 1) {
               System.out.println("head");
               Node<E> current = header.getNext();
               Node<E> previous = null;
               int i = 1;
               while (i <= n) {
                   previous = current;
                   current = current.getNext();
                   if (current == null) {
                       break;
                   }
                   i++;
               }
               previous.getPrev().setNext(current);
               size--;
               return previous.getData();
           } else {
               System.out.println("trail");
               Node<E> current = trailer.getPrev();
               Node<E> previous = null;
               int i = size;
               while (i >= n) {
                   previous = current;
                   current = current.getPrev();
                   if (current == null) {
                       break;
                   }
                   i--;
               }
               current.setNext(previous.getNext());
               size--;
               return previous.getData();
           }
       }
   }

   public void remove(E e) {
       Node<E> current = header.getNext();
       Node<E> next;
       int n = 1;
       int i = 0;
       while (current != null) {
           if (current.getData() != null && current.getData().equals(e)) {
               next = current.getNext();
               current = next;
               remove(n-i);
               i++;              
           } else {
               current = current.getNext();
           }
           n++;
       }
   }

}

Test.java
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.addLast(new Student(4, "Stud-4"));
       myList.addLast(new Student(5, "Stud-5"));
       myList.addLast(new Student(6, "Stud-6"));
       myList.addLast(new Student(4, "Stud-4"));
       //myList.removeLast();
       myList.printForward();
       System.out.println(myList.size());
       try {
           myList.insertAfter(4,new Student(7, "Stud-7"));
           myList.printForward();
       } catch (Exception e) {
           e.printStackTrace();
       }
      
       /*System.out.println("Removed Data : " + myList.remove(2));
       myList.printForward();*/
      
       System.out.println("Removed Data : ");
       myList.remove(new Student(4, "Stud-4"));
       myList.printForward();
   }
}

Node.java
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 void setData(E d) { data=d; }
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.java

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 + "]";
}

@Override
public boolean equals(Object o) {
if (o == this) {
return true;
}
if (!(o instanceof Student)) {
return false;
}
Student s = (Student) o;
return Integer.compare(id, s.id) == 0 &&
       name.compareTo(s.name) == 0 ;
}

}