Abstract Data Types Intro

(Notes below)


Advantages and Disadvantages of Selected Data Structures

Many details to follow, but let's start, in a revolutionary way, by just looking at the main advantages and disadvantages of three data structures, the Java array, and two ADTs, the linked list and the binary search tree.


Advantage - Can easily be binary searched (if sorted)
Disadvantage - It is static in size (i.e. cannot change its size after being made).
So it wastes memory if not all elements are used.

Linked List:

Advantage - It is a dynamic data structure (i.e. it can grow or shrink after being made).
So it does not waste memory.
Disadvantage - It can not be searched in a binary way; access is only available from one end of it in a sequential way.

Binary Search Tree:

Advantages: It is a dynamic data structure, like the linked list, and so does not waste memory.
It can be searched in a binary way, just like a sorted array.
Disadvantage - It's a little tricky to program, particularly deletion of nodes.

Hash Table:

Advantage: Direct access to an element via a hash calculation.
Disadvantag: Like an array, it is not a dynamic data structure, and so it can be wasteful of memory if not full.