Feasibility of LinkedList versus Array for sorted or unsorted data?
Comparing LinkedLists and Arrays, and Comparing Their Differences to Sorted and Unsorted Data
- Adding
- Deleting
- Retrieving
- Sorting
- Overall speed
- Shared memory usage
Topical issues
Discuss the possibility of implementing an unsorted dataset as a linked list rather than an array. What would be the tradeoffs in terms of insertion, deletion, extraction, computer memory, and application speed?
Discuss the possibility of implementing the sorted dataset as a linked list rather than an array. What are the tradeoffs in terms of insert, delete, eject, computer memory, and application speed?
Based on your answers to the previous questions, summarize the costs and benefits of using linked lists in your application.
My answers / input:
LinkedLists have to allocate memory every time a new Node is added, useful when adding many nodes and the size keeps changing, but overall slower when adding multiple elements
Arrays allocate memory at the beginning of the program start, resizing the list is slow (adding many elements is slow if resizing is required)
Fetching is faster in an array due to indexing
Add / remove faster in LinkedList due to pointers
source to share
Unsorted or sorted. I'll do it, then you really need to do your homework.
Stackoverflow markup really needs tables for this. You mean how "expensive" is the operation for unsorted / array, sorted / array, unsorted / linked list, sorted / linked list
One final point: "application speed" is a hint at not just the speed of individual operations.
* Adding
Unsorted: Adding an array is O (1), if no resizing is required - just add it to the end. Maybe you should discuss a sizing strategy that minimizes the overhead (hint: don't just increase the size by one)
Sorted: Adding an array is O (n) - finding a place to add is O (log (n)), but you need to move half of the items up (on average) to create a romm for the new one.
Unsorted: Linked List - O (1) - Add it to the beginning or end of the list.
Sorted: A linked list is O (n) - although you can add the item again in O (1), you need to go through half of the list on average to find a place to put it.
So, to you for the rest. Post a response and we'll criticize it, but to get the most out of your (supposedly) expensive education, you really need to do a little bit of work on it :)
* Removing
* Retrieving
* Sorting
* Overall speed
* Overall memory usage
source to share
Here is a C++ code that illustrates that sorting the data miraculously makes the code faster than the unsorted version. Let’s try out a sample C++ program to understand the problem statement better.
// CPP program to demonstrate processing // time of sorted and unsorted array
#include <iostream>
#include <algorithm>
#include <ctime>
using namespace std;
const int N = 100001;
int main()
{
int arr[N];
// Assign random values to array
for (int i=0; i<N; i++)
arr[i] = rand()%N;
// for loop for unsorted array
int count = 0;
double start = clock();
for (int i=0; i<N; i++)
if (arr[i] < N/2)
count++;
double end = clock();
cout << "Time for unsorted array :: "
<< ((end - start)/CLOCKS_PER_SEC)
<< endl;
sort(arr, arr+N);
// for loop for sorted array
count = 0;
start = clock();
for (int i=0; i<N; i++)
if (arr[i] < N/2)
count++;
end = clock();
cout << "Time for sorted array :: "
<< ((end - start)/CLOCKS_PER_SEC)
<< endl;
return 0;
}
// Code output
Output :
Execution 1:
Time for an unsorted array: 0.00108
Time for a sorted array: 0.00053
Execution 2:
Time for an unsorted array: 0.001101
Time for a sorted array: 0.000593
Execution 3:
Time for an unsorted array: 0.0011
Time for a sorted array: 0.000418
Observe that time taken for processing a sorted array is less as compared to an unsorted array. The reason for this optimization for a sorted array is branch prediction.
source to share