Consider a method called insertElement(string element, int position) in an array-based list data structure. The purpose...
Consider a method called insertElement(string element, int position) in an array-based list data structure. The purpose of this method is to insert an element (of type string) in the array at the given position within the array. This methods works fine for small array-based lists, but is very inefficient for large lists. Briefly explain why the same function is more efficient when implemented using a singly linked list.
Homework Answers
void insertElement(String element, int position)
In an array based list structure, the above method to insert an elemetn at a position is very inefficient, because we need to shift all the elements from the position position+1 to right. When the array size is large, no. of shiftings increase linearly and takes a lot of time. It's time complexity for a single insertion is given by O(N)
This same method, when using linked list becomes highly efficinet,
because, inorder to insert a new element, we need to add a new
element at the position and adjust links which takes constant time
O(1) irrespective of the size of the list. When using linked list
based lists, inserting and deleting an element becomes trivial.
Add Answer to:
Consider a method called insertElement(string element, int
position) in an array-based list data structure. The purpose...
A method called linearSearch(), which takes as parameters an array of int followed by three values...
A method called linearSearch(), which takes as parameters an array of int followed by three values of type int, and returns a value of type int. The first int parameter represents a key, the second int parameter represents a starting position, and the third int parameter represents an end position. If the key occurs in the array between the start position (inclusive) and the end position (exclusive), the method returns the position of the first occurrence of the key in...
Implement an application based on a singly linked list that maintains a list of the top...
Implement an application based on a singly linked list that maintains a list of the top five performers in a video game. An entry on the list consists of a name and a score (you can make this into a blueprint class if you like), and the list must be maintained in descending order of scores. Here is an example of such a list when it only has three elements. Spike120 Whiz105 G-man 99 Use a class based on singly...
Q1)(20p)Write a static member function called removeLongestRepeatingSegment that takes a String a...
Q1)(20p)Write a static member function called
removeLongestRepeatingSegment that takes a String argument. The
method will return a new String by removing the logest segment that
contains consequtively repeating characters.
public static void main(String []args){
String s=”1111222223333311111111444455552222”;
String res= removeLongestRepeatingSegment(s); will return
“11112222233333444455552222”
}
public static String removeLongestRepeatingSegment(String
s){
---------------
Q2)15p)Given a list of objects stored (in ascending order) in a
sorted linked list, implement member method which performs search
as efficiently as possible for an object based on a key....
package week_3; /** Write a method called countUppercase that takes a String array argument. You can...
package week_3; /** Write a method called countUppercase that takes a String array argument. You can assume that every element in the array is a one-letter String, for example String[] test = { "a", "B", "c", "D", "e"}; This method will count the number of uppercase letters from the set A through Z in the array, and return that number. So for the example array above, your method will return 2. You will need to use some Java library methods....
Static methods can be called directly from the name of the class that contains the method. Static methods are usually created to do utility operations. For example: public class Test{ public static i...
Static methods can be called directly from the name of the class that contains the method. Static methods are usually created to do utility operations. For example: public class Test{ public static int timesTwo(int value){ return value * value; } } public class TestDriver{ public static void main(String[] args){ int var = Test.timesTwo(5); System.out.println(var); } } For your final exercise, create a class called ManyLinkedLists. It will contain a static method called createLinkedList(). That method takes an argument that is...
Complete an Array-Based implementation of the ADT List including a main method and show that the...
Complete an Array-Based implementation of the ADT List including a main method and show that the ADT List works. Draw a class diagram of the ADT List __________________________________________ public interface IntegerListInterface{ public boolean isEmpty(); //Determines whether a list is empty. //Precondition: None. //Postcondition: Returns true if the list is empty, //otherwise returns false. //Throws: None. public int size(); // Determines the length of a list. // Precondition: None. // Postcondition: Returns the number of items in this IntegerList. //Throws: None....
JAVA Lab Create a class called ArrayBasedStack. Declare the following variables: • data: references an array...
JAVA Lab Create a class called ArrayBasedStack. Declare the following variables: • data: references an array storing elements in the list • topOfStack: an int value representing the location of the stack top in the array • INITIAL_CAPACITY: the default capacity of the stack public class ArrayBasedStack <E> { private E[] data; private int topOfStack; private static final int INITIAL_CAPACITY = 5; } Add a constructor that will initialize the stack with a user-defined initial capacity. The top of the...
List of Candles Create a class called CandleNode which has fields for the data (a Candle)...
List of Candles Create a class called CandleNode which has fields for the data (a Candle) and next (CandleNode) instance variables. Include a one-argument constructor which takes a Candle as a parameter. (For hints, see the PowerPoint on "Static vs. Dynamic Structures”.) public CandleNode (Candle c) { . . } The instance variables should have protected access. There will not be any get and set methods for the two instance variables. Create an abstract linked list class called CandleList. This...
Write a method called printReverse() that takes a string and uses recursion to print the contents...
Write a method called printReverse() that
takes a string and uses recursion to print the contents of the
string in reverse order. The string itself should
not be reversed; it must be left in its
original form.
The method has the following header:
void printReverse(String s, int i)
where s is a reference to the string, and i is an integer
parameter that you may use as you see fit. You do not need
to code up this method as...
I need help with the Implementation of an Ordered List (Template Files) public interface Ordered...
I need help with the Implementation of an Ordered List (Template Files) public interface OrderedStructure { public abstract int size(); public abstract boolean add( Comparable obj ) throws IllegalArgumentException; public abstract Object get( int pos ) throws IndexOutOfBoundsException; public abstract void remove( int pos ) throws IndexOutOfBoundsException; public abstract void merge( OrderedList other ); } import java.util.NoSuchElementException; public class OrderedList implements OrderedStructure { // Implementation of the doubly linked nodes (nested-class) private static class Node { private Comparable value; private...
Q1)(20p)Write a static member function called
removeLongestRepeatingSegment that takes a String argument. The
method will return a new String by removing the logest segment that
contains consequtively repeating characters.
public static void main(String []args){
String s=”1111222223333311111111444455552222”;
String res= removeLongestRepeatingSegment(s); will return
“11112222233333444455552222”
}
public static String removeLongestRepeatingSegment(String
s){
---------------
Q2)15p)Given a list of objects stored (in ascending order) in a
sorted linked list, implement member method which performs search
as efficiently as possible for an object based on a key....
Write a method called printReverse() that
takes a string and uses recursion to print the contents of the
string in reverse order. The string itself should
not be reversed; it must be left in its
original form.
The method has the following header:
void printReverse(String s, int i)
where s is a reference to the string, and i is an integer
parameter that you may use as you see fit. You do not need
to code up this method as...
Most questions answered within 3 hours.
-
) Assume that in the market for widgets, demand is highly
elastic compared to supply. If...
asked 1 minute from now -
Why is a personal interview the most important step in the sales
selection process? What are...
asked 8 minutes ago -
In Python rOverlap (x1, y1, w1, h1, x2, y2, w2, h2) A rectangle
is axis-aligned if...
asked 8 minutes ago -
If we observe in a protein solution that DNA is causing a
mixture 260/280 ratio ~0.9,...
asked 18 minutes ago -
Explain the steps involved in making cDNA from mRNA, and how you
would create a cDNA...
asked 19 minutes ago -
A beta (β) particle is described by which of the following?
Select the correct answer below:...
asked 22 minutes ago -
A new machine costs $150,000, lasts 10 years, has an annual
O&M cost of $50,000, and...
asked 25 minutes ago -
A newspaper in a large Midwestern city reported that the
National Association of Realtors said that...
asked 27 minutes ago -
1. Develop a use case diagram for the bank case study described
in Chapter 1. 2....
asked 37 minutes ago -
The phylum Protista has often been referred to as a junk drawer
of classification. Explain what...
asked 43 minutes ago -
The average amount of money spent for lunch per person in the
college cafeteria is $7.09...
asked 45 minutes ago -
You follow the lab procedure and at the end of Part 4C, you used
an average...
asked 1 hour ago