Feasibility of LinkedList vs. Array for sorted vs. unsorted data?

Question

Comparing LinkedLists and Arrays while also comparing their differences with sorted and unsorted data

• Adding
• Removing
• Retrieving
• Sorting
• Overall speed
• Overall memory usage

Actual questions

Discuss the feasibility of implementing an unsorted data set as a linked list rather than an array. What would the tradeoffs be in terms of insertion, removal, retrieval, computer memory, and speed of the application?

Discuss the feasibility of implementing a sorted data set as a linked list rather than an array. What would the tradeoffs be in terms of insertion, removal, retrieval, computer memory, and speed of the application?

Based on your answers to the previous questions, summarize the costs and benefits of using linked lists in an application.

My answers/input:

LinkedLists have to allocate memory everytime a new Node is added, useful when adding many Nodes and size keeps changing but generally slower when adding few elements

Arrays allocated memory at the beggining of the program run, resizing list slow (adding many elements slow if have to resize)

Retrieval is faster in array due to indexing

Adding/removing faster in LinkedList due to pointers

Answer 1

On unsorted vs. sorted. I'll do one, then you really do need to do your homework

Stackoverflow markup really needs tables to do this one. You want to say how "expensive" the operation is for the unsorted/array, sorted/array, unsorted/linked-list, sorted/linked-list

One final point: "speed of the application" is a hint to consider more than just the speed of the individual operations.

* Adding

Unsorted: Array adding is O(1) unless resizing needed - just add it to the end. You might want to discuss a resizing strategy that minimises the overhead (hint: don't just increase the size by one)

Sorted: Array adding is O(n) - finding the place to add it is O(log(n)), but you need to move half the elements up (on average) to make romm for the new one

Unsorted: Linked list is O(1) - add it to the start or end of the list.

Sorted: Linked list is O(n) - although you can again add the element in O(1), you need to scan through half the list on average to find the place to put it.

So, over to you for the rest. Post an answer, and we'll critique it, but to get the most from your (presumably) expensive educatiom, you really need to do some work on this :)

* Removing
* Retrieving
* Sorting
* Overall speed
* Overall memory usage

Answer 2

Not sure what class this is for, but for a CS program, you will have to do better than "is slow" and "is fast". Try to quantify that, in terms of number-of-operations-needed. You should be familiar with a machinery typically used for such quantification -use that machinery.

Answer 3

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;
}

//Output of the code

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.

Answer 4

@Paul: Thanks

• Removing

Unsorted & sorted: Array removing is O(n) - have to move all element over to fill 'hole'

Unsorted & sorted: Linked list is O(1) - Change pointers as needed