Data Structures and Algorithms. Answer needs to be in JAVA Hybrid Linked List /

ID: 3681233 • Letter: D

Question

Data Structures and Algorithms.

Answer needs to be in JAVA

Hybrid Linked List / Separate Chaining Hash Table

Create a hybrid linked list and use random numbers between 10 -99 for input.

Methods - search ()/sort (), set ()/get (), add ()/remove ()

INCLUDE Sort/search algorithms

Analysis of Time for n= 100 n = 1000, n = 10000

1. Hybrid Linked List / Separate Chaining Hash Table Create a hybrid linked list and use random numbers between 10-99 for input.. Methods - search ()/sort (), set ()/get (), add ()/remove () INCLUDE Sort/search algorithms Analysis of Time for n= 100 n = 1000, n = 10000-

Explanation / Answer

Array vs ArrayList in Java

1) First and Major difference between Array and ArrayList in Java is that Array is a fixed length data structure while ArrayList is a variable length Collection class. You can not change length of Array once created in Java but ArrayList re-size itself when gets full depending upon capacity and load factor. Since ArrayList is internally backed by Array in Java, any resize operation in ArrayList will slow down performance as it involves creating new Array and copying content from old array to new array.

2) Another difference between Array and ArrayList in Java is that you can not use Generics along with Array, as Array instance knows about what kind of type it can hold and throws ArrayStoreException, if you try to store type which is not convertible into type of Array. ArrayList allows you to use Generics to ensure type-safety.

3) You can also compare Array vs ArrayList on How to calculate length of Array or size of ArrayList. All kinds of Array provides length variable which denotes length of Array while ArrayList provides size() method to calculate size of ArrayList in Java.

4) One more major difference between ArrayList and Array is that, you can not store primitives in ArrayList, it can only contain Objects. While Array can contain both primitives and Objects in Java. Though Autoboxing of Java 5 may give you an impression of storing primitives in ArrayList, it actually automatically converts primitives to Object.

Methods - search ()/sort (), add ()/remove ()

/* Java program to design a data structure that support folloiwng operations

in Theta(n) time

a) Insert

b) Delete

c) Search

d) getRandom */

import java.util.*;

// class to represent the required data structure

class MyDS

{

ArrayList<Integer> arr; // A resizable array

// A hash where keys are array elements and vlaues are

// indexes in arr[]

HashMap<Integer, Integer> hash;

// Constructor (creates arr[] and hash)

public MyDS()

{

arr = new ArrayList<Integer>();

hash = new HashMap<Integer, Integer>();

}

// A Theta(1) function to add an element to MyDS

// data structure

void add(int x)

{

// If ekement is already present, then noting to do

if (hash.get(x) != null)

return;

// Else put element at the end of arr[]

int s = arr.size();

arr.add(x);

// And put in hash also

hash.put(x, s);

}

// A Theta(1) function to remove an element from MyDS

// data structure

void remove(int x)

{

// Check if element is present

Integer index = hash.get(x);

if (index == null)

return;

// If present, then remove element from hash

hash.remove(x);

// Swap element with last element so that remove from

// arr[] can be done in O(1) time

int size = arr.size();

Integer last = arr.get(size-1);

Collections.swap(arr, index, size-1);

// Remove last element (This is O(1))

arr.remove(size-1);

// Update hash table for new index of last element

hash.put(last, index);

}

// Returns a random element from MyDS

int getRandom()

{

// Find a random index from 0 to size - 1

Random rand = new Random(); // Choose a different seed

int index = rand.nextInt(arr.size());

// Return element at randomly picked index

return arr.get(index);

}

// Returns index of element if element is present, otherwise null

Integer search(int x)

{

return hash.get(x);

}

// Driver class

class Main

{

public static void main (String[] args)

{

MyDS ds = new MyDS();

ds.add(10);

ds.add(20);

ds.add(30);

ds.add(40);

System.out.println(ds.search(30));

ds.remove(20);

ds.add(50);

System.out.println(ds.search(50));

System.out.println(ds.getRandom());

}

Output:

Sort search

Bubble sort, also referred to as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort. Although the algorithm is simple, most of the other sorting algorithms are more efficient for large lists.

Bubble sort has worst-case and average complexity both (n2), where n is the number of items being sorted. There exist many sorting algorithms with substantially better worst-case or average complexity of O(n log n). Even other (n2) sorting algorithms, such as insertion sort, tend to have better performance than bubble sort. Therefore, bubble sort is not a practical sorting algorithm when n is large.Performance of bubble sort over an already-sorted list (best-case) is O(n).

package com.java2novice.algos;

public class MyBubbleSort {

// logic to sort the elements

public static void bubble_srt(int array[]) {

int n = array.length;

int k;

for (int m = n; m >= 0; m--) {

for (int i = 0; i < n - 1; i++) {

k = i + 1;

if (array[i] > array[k]) {

swapNumbers(i, k, array);

}

printNumbers(array);

}

private static void swapNumbers(int i, int j, int[] array) {

int temp;

temp = array[i];

array[i] = array[j];

array[j] = temp;

}

private static void printNumbers(int[] input) {

for (int i = 0; i < input.length; i++) {

System.out.print(input[i] + ", ");

}

System.out.println(" ");

}

public static void main(String[] args) {

int[] input = { 4, 2, 9, 6, 23, 12, 34, 0, 1 };

bubble_srt(input);

}

Output:

2, 4, 6, 9, 12, 23, 0, 1, 34,

2, 4, 6, 9, 12, 0, 1, 23, 34,

2, 4, 6, 9, 0, 1, 12, 23, 34,

2, 4, 6, 0, 1, 9, 12, 23, 34,

2, 4, 0, 1, 6, 9, 12, 23, 34,

2, 0, 1, 4, 6, 9, 12, 23, 34,

0, 1, 2, 4, 6, 9, 12, 23, 34,

Random

import java.util.*;

public class RandGuess

{

public static void main ( String[] args )

{

int upperRange;

int lowerRange;

Random random;

int randomFromUserLimits;

Scanner keyboard = new Scanner(System.in);

System.out.print("Enter upper limit number: ");

upperRange = keyboard.nextInt();

System.out.print("Enter lower limit number: ");

lowerRange = keyboard.nextInt();

random = new Random();

randomFromUserLimits = random.nextInt(upperRange-lowerRange) + lowerRange;

System.out.println("A random number between " + lowerRange + " and " + upperRange + " = " + randomFromUserLimits);

}