Simple Data Structures

Remember the data structures we discussed earlier:

Linked List:  a data structure in which given an access path to one node it is possible to obtain access to a unique successor node, eg:

LL6

Stack: a linked list in which insertion and deletion are restricted to one end, usually the front.

Queue: a linked list in which insertion is restricted to one end and deletion to the other end.

Tree: a hierarchical data structure in which each node other than the root is  the descendant of a parent node and can have one or more child nodes.

All data structures share several fundamental characteristics:

  1. a data structure is a (possibly empty) set of nodes, each of which contains the same collection of named attributes.  The structure has a name which contains the details necessary for operating on it and distinguishes it from all other structures.
  2. there is a unique access path to every node in the structure and a test function which indicates whether or not a given access path points to a node of the structure.
  3. the access path of every node can be obtained either from the name of the structure or from the access path of at least one other node or from one of its attribute values. The methods of obtaining an access path are known as access primitives.
  4. there is a method of creating and destroying the structure and of inserting and deleting nodes.

In order to implement a data structure, decisions require to be made in a number of areas:

  1. storage medium for nodes, eg: paper, cards, magnetic storage, main memory etc.
  2. a method of representing attribute values, eg: binary (for integers), ASCII or Unicode (for characters).
  3. a method of obtaining space for nodes and a unique access path to each node.
  4. an implementation of the access primitives and the create, destroyinsert and delete primitives. eg: card index file:
  • storage medium is cards;
  • data is represented by alphabetic and numeric characters;
  • space is obtained by having a supply of blank cards;
  • to access a card, open drawer and search through cards in sequence, flipping each card in turn. If there are marker cards present (eg:       alphabetical) it is possible to obtain immediate access to the following card.  The access path is unique as there is a different position for every card in the box.