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

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 2

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 3

@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

Answer 4

what is itemtype