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

Answering first four parts of Ex 2 as you have not mentioned Singley Linked List Class.

1. Print forwards : It prints data inside all the nodes from head to tail.

eg DLL is 1 <-> 2<->3<->4<->5 , it will print

1 2 3 4 5 in different lines.

Print Backwards : It prints data from tail to head,ie, in reverse order of DLL.

eg DLL is 1<-> 2<->3<->4<->5 , it will print

5 4 3 2 1 in different lines.

2. Class test already mentioned and object has been created . You can test the methods.

4 e). creating method get(int n)

E get(int n )

{

int sizeOfList = size();

if(n > size)

return null;

if(n<=size/2)//this is to check to start from head or tail , if this is true we start from head

{

Node<E> tmp=header;

n=n-1;

while(n--)

{

tmp = tmp.getNext(); //this is to reach the position of the node.

}

return tmp.getData();

}

else // this is when node lies in second half and we start from end

{

m = sizeOfList - n; //we needd to m steps from behind to reach the position

Node<E> tmp1=trailer;

while(m--)

{

tmp = tmp.getPrev();

}

return tmp.getData();

}

Complexity will be O(n) as in both cases at max we need to move n/2 number of nodes.

f) Method insertAfter(int n, E e)

bit similar to above problem , we need to move to the node number n and then add one node. While we add one node we will need to fix its next and prev pointers.

void insertAfter(int n, E e)

{

int sizeOfList = size();

if(n > size)

throw Exception;

if(n<=size/2)//this is to check to start from head or tail , if this is true we start from head

{

Node<E> tmp=header;

n=n-1;

while(n--)

{

tmp = tmp.getNext(); //this is to reach the position of the node.

}

Node<E> pred = tmp; // this will be the predecessor

Node<E> succ = tmp.getNext(); // this will be the successor

//Created new node will be added between above node using addBetween function

addBetween(e, pred,succ);

}

else // this is when node lies in second half and we start from end

{

m = sizeOfList - n; //we needd to m steps from behind to reach the position

Node<E> tmp1=trailer;

while(m--)

{

tmp = tmp.getPrev();

}

//please note how the way of fetching predecessor and successor changes while moving from back

Node<E> pred = tmp.getPrev(); // this will be the predecessor

Node<E> succ = tmp; // this will be the successor

//Created new node will be added between above node using addBetween function

addBetween(e, pred,succ);

}

}