Question

For all code assignments there should be exhaustive test code which takes it input from stdin. Your code should be reasonably efficient - it should not have big-Oh larger than what would be expected from good implementation

Q1. Implement a double linked list with a sentinel element. The API should have four methods (no more) to: i) A method to create a new list instantiated with some type of elements (data stored in the list) defined at the time the list is created ii) A method to insert an element at the beginning of the list iii) A method to insert an element at the end of the list and a method to remove and return the first element in the list iv) A method to remove and return the last element of the list and You should calculate the Big-Oh complexities for insertion and removal of elements.

-----------------------------------------------------------------------------------------

Kindly answer all 4 sub parts. Program: Java, no prebuild libiary.

Answer 1

Please find all the explanation to the code within the code itself as comments.

Please note that because the constraint of the problem was to create no more than 4 methods, we have combined the operations performed by the third part, "A method to insert an element at the end of the list and a method to remove and return the first element in the list" into a single function. But, we have also cleanly separated the code for the two operations, so, if you want them to be two different functions, you may create two functions like this:

1. insertAtEnd (): This function will insert the argument provided at the end of the list.

2. removeAndReturnFromBeginning (): This function will remove the Node from the beginning of the list and returns the reference to it.

TAKING INPUT:

Taking the data for our DoublyLinkedList can be of different types.

1. We may use to code to take the input from the user within our DoublyLinkedList () constructor like this:

    public DoublyLinkedList () {
                        
                // set head and tail to null initially
                head = null;
                tail = null;

                // we will create a Scanner object 
                // to take the input from the user
                Scanner scanner = new Scanner (System.in);

                // we will take the input from the user
                String input = scanner.next ();

                int data = 0;

                // create a new Node reference
                Node newNode = null;

                // we will take the input from the user 
                // until we encounter "exit"
                while (input.equals("exit") == false) {
                                
                        // convert the string to integer
                        data = Integer.parseInt (input);
                        
                        // create a new Node
                        newNode = new Node (data);

                        // if the head Node is null, that means
                        // our list is empty
                        if (head == null) {
                                // as there is only one Node 
                                // in our list for now, 

                                // both head and tail point to that
                                head = newNode;
                                tail = newNode;
                        }

                        // but, if our list is not empty
                        else {

                                // we will concatenate the 
                                // incoming node at the end

                                // set newNode as the next of current tail
                                tail.next = newNode;
                                // set the previous of newNode to current tail
                                newNode.previous = tail;

                                // because, newNode is now the last element
                                // update tail reference
                                tail = newNode;
                        }

                        // take input from the user
                        input = scanner.next();
                }
        }

2. Or we can provide a list to our constructor function using which it will on its own fill-up the DoublyLinkedList. Like this:

    public DoublyLinkedList (int [] input) {
                        
                // set head and tail to null initially
                head = null;
                tail = null;

                int i = 0;

                // create a new Node reference
                Node newNode = null;

                // we will take the input from the user 
                // until we encounter "exit"
                while (i < input.length) {
                                
                        // create a new Node
                        newNode = new Node (input[i]);

                        // if the head Node is null, that means
                        // our list is empty
                        if (head == null) {
                                // as there is only one Node 
                                // in our list for now, 

                                // both head and tail point to that
                                head = newNode;
                                tail = newNode;
                        }

                        // but, if our list is not empty
                        else {

                                // we will concatenate the 
                                // incoming node at the end

                                // set newNode as the next of current tail
                                tail.next = newNode;
                                // set the previous of newNode to current tail
                                newNode.previous = tail;

                                // because, newNode is now the last element
                                // update tail reference
                                tail = newNode;
                        }

                        // increment the iterator
                        i += 1;
                }
        }

Because in questions, we are given to use the list form, we will use that in our code.

As it was not specified in the problem statement to put the test code into the same file, we have created two files, DoublyLinkedList.java and TestCode.java to keep things organized. ( If you want the test code into the same file, then, just copy and paste the main function from the file TestCode.java to DoublyLinkedList.java within the class DoublyLinkedList. )

Here is the full code:

DoublyLinkedList

import java.util.*;

// we will create a class
// for the nodes in our DoublyLinkedList
class Node {
                
        // the attribute, which will 
        // hold the data 
        public int data;

        // reference to next node to point to 
        // the node next to it in the list
        public Node next;

        // reference to previous node to point to
        // the node previous to it in the list
        public Node previous;

        public Node (int data) {
                this.data = data;
                this.next = null;
                this.previous = null;
        }
}

public class DoublyLinkedList {

        // we will have a reference to 
        // the head Node in our class 
        private Node head;

        // we will have a reference to
        // the tail Node in our class
        private Node tail;
                
        // as we require a method to create a new list 
        // instantiated with some type of elements 
        // defined at the time the list is created and 
        // for that, we can use a constructor of  class

        // you may change this into something like 
        // createDoublyLinkedList() function rather than a 
        // constructor, if that's required
         
        public DoublyLinkedList (int [] input) {
                        
                // set head and tail to null initially
                head = null;
                tail = null;

                int i = 0;

                // create a new Node reference
                Node newNode = null;

                // we will take the input from the user 
                // until we encounter "exit"
                while (i < input.length) {
                                
                        // create a new Node
                        newNode = new Node (input[i]);

                        // if the head Node is null, that means
                        // our list is empty
                        if (head == null) {
                                // as there is only one Node 
                                // in our list for now, 

                                // both head and tail point to that
                                head = newNode;
                                tail = newNode;
                        }

                        // but, if our list is not empty
                        else {

                                // we will concatenate the 
                                // incoming node at the end

                                // set newNode as the next of current tail
                                tail.next = newNode;
                                // set the previous of newNode to current tail
                                newNode.previous = tail;

                                // because, newNode is now the last element
                                // update tail reference
                                tail = newNode;
                        }

                        // increment the iterator
                        i += 1;
                }
        }

        // this method to insert an element at the beginning of the list
        public void insertAtBeginning (int data) {
                        
                // we will create a new Node with the given data 
                Node newNode = new Node (data);

                // because this node must be the head now

                // we will set the next of this node to the current head
                newNode.next = head;
                // we will set the previous of head to the new Node
                head.previous = newNode;

                // update the head reference to the new Node
                head = newNode;
        }

        // this method is used: 
        // 1. to insert an element at the end of the list 
        // 2. to remove and return the first element in the list

        public Node insertAtEndAndRemoveFromBeginning (int insertionData) {
                        
                // INSERTION AT THE END

                // because we have the reference to the tail of our list
                // we can use it to insert our data at the end

                // create a new node
                Node newNode = new Node (insertionData);

                // set newNode as the next of current tail
                tail.next = newNode;
                // set the previous of newNode to current tail
                newNode.previous = tail;

                // because, newNode is now the last element
                // update tail reference
                tail = newNode;


                // REMOVINT AND RETURN FROM THE BEGINNING

                // essentially, we want to remove and return the current head from the list
                // save the current head into a Node reference
                Node toReturn = head;

                // in order to remove the head node
                // make the Node next to head as new head
                head = head.next;

                // the previous of the new head would be null
                head.previous = null;

                // return the reference to the removed Node
                return toReturn;
        }

        // A method to remove and return the last element of the list
        public Node removeAndReturnLast () {
                        
                // to remove the last element from the list
                // we would need to manipulate some references related to second last Node

                // therefore, we will save the reference to the second last Node
                Node secondLast = tail.previous;

                // we will save the reference to the tail Node 
                // in order later return it
                Node toReturn = tail;

                // after removing the last Node, secondLast Node will be the new last Node
                // therefore, we will set the next of secondLast Node as null
                secondLast.next = null;

                // return the reference to the removed node
                return toReturn;
        }
}

TestCode

As specified in the problem statement, we have written an exhaustive test code, covering all the functions and analyzing the contents of the list before and after they have been called.

import java.util.*;

public class TestCode {

        // print function to look at the data after manipulation
        public static void print (DoublyLinkedList dll) {
                        
                Node ptr = dll.head;

                System.out.println ();
                while (ptr != null) {
                        System.out.print (ptr.data + " ");
                        ptr = ptr.next;
                }
                System.out.println ();
        }
                
        public static void main (String [] args) {
                        
                // create a Scanner object for taking input
                Scanner scanner = new Scanner (System.in);

                System.out.println ("\nEnter the size of the array: ");
                // get the size of array from the user
                int n = scanner.nextInt ();

                // create an array of size n
                int [] arr = new int[n];

                System.out.println ("\nEnter the elements of the array: ");
                // fill in the array with user inputs
                for (int i = 0; i < n; ++i) {
                        arr[i] = scanner.nextInt ();
                }

                DoublyLinkedList dll = new DoublyLinkedList (arr);

                System.out.println ("\nEnter the value you want to insert at the beginning: ");
                int data = scanner.nextInt ();

                System.out.println ("\nPrinting before insertAtBeginning ()");
                print (dll);

                dll.insertAtBeginning (data);

                System.out.println ("\nPrinting after insertAtBeginning ()");
                print (dll);


                System.out.println ("\nEnter the value you want to insert at end: ");
                data = scanner.nextInt();

                System.out.println ("\nPrinting before insertAtBeginning ()");
                print (dll);

                Node node = dll.insertAtEndAndRemoveFromBeginning (data);
                System.out.println ("\nPrinting the data of the node removed from beginning: " + node.data);

                System.out.println ("\nPrinting after insertAtEndAndRemoveFromBeginning ()");
                print (dll);

                System.out.println ("\nPrinting before insertAtBeginning ()");
                print (dll);

                node = dll.removeAndReturnLast ();
                System.out.println ("\nPrinting the data of the node removed from beginning: " + node.data);

                System.out.println ("\nPrinting after removeAndReturnLast ()");
                print (dll);
        }
}

Please refer to the screenshots of the code at the end for understanding indentation.

TIME COMPLEXITY OF INSERTIONS AND DELETIONS

Let's analyze the time complexities of our insertion and deletion algorithms.

1. insertAtBeginning(): In this, we have manipulated only the first node, the head node of the linked lists. In total, we have 4 assignment statements in this function and all of them are of constant time, therefore, the time complexity of this function is:

2. insertAtEndAndRemoveFromBeginning(): In this, we have used both the head and the tail for deletion and insertion respectively. In here as well, all the operations were only assignments, there were no loops or anything. There were some if-else conditional statements as well, and they are also of constant time. Therefore, the time complexity of this function is:

3. removeAndReturnLast(): In this, we first found the reference to the second last node by using the previous reference of the last node, and this was, indeed, a constant time operation. Like in the previous two functions, we have manipulated some references to delete the last element. Therefore, the time complexity of this function is also:

Please note that all the insertions and deletions at the beginning were possible in O(1), because, we have access to the head node, while, all the insertions and deletions at the end were possible in O(1), because, we have access to the previous node.

Let's look at an input-output for the above code: