A. Assume you have List containing a million elements of type String. Would you
ID: 3870562 • Letter: A
Question
A. Assume you have List containing a million elements of type String. Would you generally expect the following operations be faster with an array-based implementation, or faster with a linked-list-based implementation (with only a head pointer, no other instance variables)? Assume the array-based implementation’s backing array is large enough to hold the new element (no enlarge() needed).
1) calling size()
2) adding an element to the end of the list (add(Marc))
3) adding an element to the front of the list (add("Marc", 0))
B. Write a public int indexOf(String s) method that searches a StringLinkedList for the first occurrence of a value .equal to s, and returns its index. Return -1 if the value is not found. For this question, write the method assuming that it’s part of the StringLinkedList started in lecture.
public class StringLinkedList implements StringListInterface {
StringNode head;
int size;
public StringLinkedList() {
head = null;
size = 0;
}
@Override
public int size() {
return size;
}
@Override
public void add(String s) {
if(head == null) {
head = new StringNode(s);
}
StringNode current = head;
while(current.getNext() != null) {
current = current.getNext();
}
current.setNext(new StringNode(s));
}
@Override
public void add(int index, String s) throws IndexOutOfBoundsException {
if(index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
size++;
StringNode node = new StringNode(s);
// inserting at head
if(index == 0) {
node.setNext(head);;
head = node;
return;
}
// or elsewhere
// fine the node before the place we want to insert "node-before"
StringNode nodeBefore = head;
for(int j = 0; j < index-1; j++) {
nodeBefore = nodeBefore.getNext();
}
// set the next node of the new node to the successor of the node-before
node.setNext(nodeBefore.getNext());
// set the next ref of the noe-before to the new node
nodeBefore.setNext(node);
}
@Override
public String get(int index) throws IndexOutOfBoundsException {
if(index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
int i = 0;
StringNode current = head;
while(true) {
if(i == index) {
return head.getValue();
}
current = current.getNext();
i++;
}
}
@Override
public String remove(int index) throws IndexOutOfBoundsException {
// TODO Auto-generated method stub
return null;
}
}
==========================================================================================
public class StringNode {
String contents;
StringNode next;
public StringNode(String s) {
contents = s;
}
public String getValue() {
return contents;
}
public void setNode(StringNode n) {
next = n;
}
public StringNode getNext() {
return next;
}
public void setNext(StringNode stringNode) {
// TODO Auto-generated method stub
}
}
============================================================================================
public interface StringListInterface {
int size();
void add(String s);
void add(int index, String s) throws IndexOutOfBoundsException;
String get(int index) throws IndexOutOfBoundsException;
String remove(int index) throws IndexOutOfBoundsException;
}
Explanation / Answer
First, Let me write a indexOf method for your class.
--------------------------------------------------------------------------------------------------------------------------------------------
public interface StringListInterface { //Add indexOf() method in StringListInterface
int size();
void add(String s);
void add(int index, String s) throws IndexOutOfBoundsException;
String get(int index) throws IndexOutOfBoundsException;
String remove(int index) throws IndexOutOfBoundsException;
int indexOf(String s) throws IndexOutOfBoundsException;
}
//Define indexOf() in StringLinkedList class.
public class StringLinkedList implements StringListInterface {
StringNode head;
int size;
public StringLinkedList() {
head = null;
size = 0;
}
//Returns index of the first occurence of given string in the linked list. If not found, -1 will be returned
@override
public int indexOf(String s)
{
int index = 0;
StringNode current = head;
while(current != null){ //to search for the given node, we begin from head till it is found
if(current.contents.equals(s)) //or you can even use (current.getValue() == s)
{
return index; //index will be returned if String is found
}
index++;
current = current.next;
}
return -1; //outside while loop. If string is not found, -1 is returned.
}
}
-----------------------------------------------------------------------------------------------------------------------
1. calling size() in Array-based implementation will be much faster compare to Linked list Implementation. To find the size of list, we need to traverse the entire list and count the elements in it. Traversing the array is much simpler and faster than Linked list. because, array uses contigous memory locations. But traversing Linkedlist is bit slower, memory is non-contigous, to go to next element, you need to refer address of next element stored in the node.
So, any operation which involves traversing elements from beginning till end, ArrayList will be a better choice.
2. adding an element to the end of list is faster in ArrayList compared to Linkedlist.
The arraylist is backed by an array to store the data. When you want to insert an element into it, you need to internally take the backup using backing-up array and once you insert a new element, entire array should be reallocated. But, as you are inserting an element at the end of the list, there are no elements to the right of the last node, which needs reallocation. So, its better to use Array-based implementation for a list for all operations which you perform at the end of the list.
The linked list is not suitable for operations at the end of the list, as you need to traverse from the begging till the end (Traversal itself is slower in LinkedList).
3. Adding an element to the front of the list is faster in LinkedList compared to ArrayList.
As i have already told, In Arraylist, when you are inserting an element, you need to backup the array and reallocate it once you have inserted new element. So, when you are inserting an element at the front, there will be millions of item to the right, which needs to reallocated. So, Using Linkedlist instead of ArrayList is a better choice.
The linkedlist will insert a new element, and makes bit change in its references. No much overload.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.