Abstract Data Structures

From TRCCompSci - AQA Computer Science
Jump to: navigation, search

An abstract data structure is one that is not defined by how it is implemented, it is instead defined by its functions.

What does this mean

An abstract data structure could be implemented in many different ways, but each having the same functionality.

The basic example is a Linked List, it could be created using:

  1. A struct to create each entry, with a data value and a pointer to the next value. You could then make this into an array.
  2. You could write a class for a node (ie data value & pointer) and write a class for a Linked List

However a Linked List will allow you to add and remove items from the list, and provide other functions such as counting the number of items in the list.

These functions are what make it a list and not how it is implemented.

We will cover

Linked Lists - Lists

Stacks

Queues

Graphs

Trees

Dictionaries

Hashing

Vectors