Data Structures

Data Structures

1. Array

   • An array is and indexed sequence of items of the same type
   • Characteristics of an Array
     • Arrays are usually fixed in size
     • Every item is immediately accessible
     • Items can be read using the index number
     • Items can be added using the index number
     • Sorting an array can be complex
   • Static data structures
     • Characteristics of Static data structures
       • Size fixed at compile-time
       • Can waste storage space if the number of data items stored is less than amount allocated for
       • Normally stores data in consecutive memory locations
       • Sorting slow as involves moving data in cells

2. Queue

   • A list of jobs waiting to be processed
   • Characteristics of a queue
     • FIFO structure
     • It grows and shrinks
     • The front and back of the queue are visible
     • Two operation are possible enqueue and dequeue
   • Common applications of a queue
     • Back
       • Data comms e.g. buffering, streams
     • Front
       • Operating systems: task scheduling, print queues, buffers
       • Simulation software

3. List

   • A list is a flexible collection of items
   • Characteristics of a list
     • It grows and shrinks
     • It has first item, next items and last item.
     • Items can be unordered or ordered
     • Items can be added to or removed from lists
     • Lists can be searched and sorted
   • Common applications of a list
     • Near the start application collections such as playlists, pohoto collections, contact lists and call lists
     • Further into the list operating systems priority lists and process lists
     • Further into the list there is application software - lists of objects

4. Stack

   • A stack is used for storing requests that need to be handled
   • Characteristics of a stack
     • LIFO structure
     • Grows and shrinks
     • Only the top is visible at any time
     • Two operations are possible push and pop
   • Common applications of a stack
     • Top
       • Function handling in programming
       • Data comms, e.g the TCP/IP protocol stack
     • Middle
       • Parsing computer language syntax
       • Depth first searching
     • Bottom
       • Recursion
       • Backtracking problems e.g. mazes, games