Abstract Data Types

An Abstract Data Type: A data type whose properties are specified independently of any particular programming language

To view a List as an ADT a set of operations need to be performed on that list:

• Start a new list
• Insert and element
• Find an element
• Delete an element
• Add an element
• Get length of list
• Output entire list

A linear list stores its elements in adjacent locations. A linear list is a one dimensional array. And is a Static Data Structure

Advantages of a Linear List:

• It is very easy to program
• If elements are stored in order then a fast efficient Binary Search can take place

Disadvantages of a Linear List:

• Memory locations may be wasted due to arrays being static and not all parts used
• Inserting and element into an ordered list means elements have to be moved, not efficient
• And the same for deleting an element, involves moving things around

A Linked List uses pointers, a start pointer and then a value within the node pointing to the next location eventually leaving a Null Pointer which doesn't point to anything indicating the end of the list.

Advantages of a Linked List:

• Its easy to add and remove items as all that is requires is to change the pointer value

Disadvantages of a Linked List:

• Memory Leakage can occur, this is when too much memory is allocated it can lead to no memory left in the 'Heap' as memory locations that are no longer required are not released.