#426 In the implementation of Singly linked

In the implementation of Singly linked - Computer Science

ChemistryExplain daily providing Q&A content “#426 In the implementation of Singly linked" in Computer science, Ba computer science, Berkeley computer science, Computer science associate degree jobs

Get the Free Online Chemistry Q&A Questions And Answers with explain. To crack any examinations and Interview tests these Chemistry Questions And Answers are very useful. Here we have uploaded the Free Online Chemistry Questions. Here we are also given the all chemistry topic.

 ChemistryExplain team has covered all Topics related to inorganic, organic, physical chemistry, and others So, Prepare these Chemistry Questions and Answers with Explanation Pdf.

For More Chegg Questions

• Inorganic Chemistry
• Organic Chemistry
• Physical Chemistry

Free Chegg Question

 Q1) In the implementation of Singly linked list we had an integer variable called size that keeps track of how many elements in the list. Also, we have a reference “tail” that points to the last node in the list. You are asked to re-implement the concept of singly linked list without using variable size, and without using reference "tail”

a) What are the methods of the main operation of singly linked list that need to be changed? Rewrite them according to this change (only the methods that need to be changed). b) Will that affect the performance of any one of the main operations( size, isEmpty, first, last, addFirst, addLast, removeFirst, removeLast)? Explain.

Q2) Using a single queue (linkedQueue), re-implement the concept of Stack ADT, what is the complexity of the method push, pop, top, isEmpty, and size. You should not use any extra data structure.

Free Chegg AnswerFor More Chemistry Notes and Helpful Content Subscribe Our YouTube Chanel - Chemistry Explain  

Free Chegg Answer

Question 1:

a)

The method that need to be changed are int size(), void addLast(int data), Node last()

class Node {

int data;

Node next;

// Constructor

Node(int d) {

data = d;

next = null;

}

}

class LinkedList {

Node head; // head of list

// Method to insert a new node at the end

public void addLast( int data) {

// Create a new node with given data

Node new_node = new Node(data);

new_node.next = null;

// If the Linked List is empty,

// then make the new node as head

if ( this.head == null) {

this.head = new_node;

}

else {

// Else traverse till the last node

// and insert the new_node there

Node last = this.head;

while (last.next != null) {

last = last.next;

}

// Insert the new_node at last node

last.next = new_node;

}

}

// Method to get the size of the list

public int size() {

int size = 0;

Node temp = this.head;

while (temp != null) {

size++;

temp = temp.next;

}

return size;

}

// method to get the last element of the list

public Node last(){

  

Node temp = this.head;

while( temp.next != null){

temp = temp.next;

}

return temp;

}   

}

b) Yes, It will affect the following operations:

1. size:

If we had the size variable in the list class then we can return the size value in O(1) time. But since we have no size variable we have to traverse the complete list and have to count the size of the list and return it. This operation takes O(n) time (where n is the number if node in the list) as we have to traverse the complete LinkedList once.

2. addLast:

If we had the tail node then we can add the new node directly to the tail of the list in O(1) time complexity. But as we are not having the tail reference we have to traverse the complete LinkedList to get to the tail of the LinkedList and add the node there. This operation takes O(n) time (where n is the number if node in the list) as we have to traverse the complete LinkedList once.

Question 2:

import java.util.*;

class Stack {

// Two inbuilt queues

Queue<Integer> q1 = new LinkedList<Integer>();

Queue<Integer> q2 = new LinkedList<Integer>();

// To maintain current number of

// elements

int curr_size;

Stack()

{

curr_size = 0;

}

void push(int x)

{

curr_size++;

// Push x first in empty q2

q2.add(x);

// Push all the remaining

// elements in q1 to q2.

while (!q1.isEmpty()) {

q2.add(q1.peek());

q1.remove();

}

// swap the names of two queues

Queue<Integer> q = q1;

q1 = q2;

q2 = q;

}

void pop()

{

// if no elements are there in q1

if (q1.isEmpty())

return;

q1.remove();

curr_size--;

}

int top()

{

if (q1.isEmpty())

return -1;

return q1.peek();

}

int size() {

return curr_size;

}

}