Data structures

Data structure

Simple way of representing the data held in a computers memory .There are hundreds of different data structures available to program

 

• One dimensional arrays

• Two dimensional
•  Three dimensional arrays
• Records
•   Tuples
•  Lists
•   Stacks
•  queues

Two types of data structures are static or dynamic

Static - size of the disk doesn’t change, they are easy to program and you always know how much space they will take up

Memory is allocated at compile time and is fixed size

- Memory allocation is fixed so there will be no problem adding or removing data items

- Can be very inefficient as the memory for the data structure has been set regardless of whether it is needed or not when the program is executing

- Easier to program as there is no need to check on data structure size at any point

Dynamic – on the other hand do not have a limited size and can expand or shrink as needed, they tend to be more complex to implement

- Memory is allocated to the data structure as the program executes
- The structure can overflow and exceed its allowed limit or underflow should it become empty.
- Makes the most efficient use of memory as it only uses what it needs
- Harder to program as the software needs to keep track of size and data items at all time

 

Big O notation is how efficiency is measured of data structures

http://www.bigocheatsheet.com

1D – a row of data (e.g. list of names)

2D – 2 rows of data (x and y) e.g. 3x4 grid

3D- cube of data e.g. 3x3x3 grid

 

All have a unique identifier e.g. Names
- All of the same data type
- All elements of the array have an index number starting at position 0.
- To access or change data you simply call the index number of the data you want
- Arrays are static data structures so their size cannot be changed after they are compiled
- To refer to 2D arrays you must use 2 index numbers which correspond to the x and y coordinates of the table
- For 3D again 3 index numbers of the x, y, z coordinates in the table
- Array values are stored in a contiguous way (one after the other) and 2D arrays are allocated in row  order (first row then second etc)
- They can be global or local variables
- It is impossible to remove all elements from an array once it has been created however you can set the elements to NULL (None in Python) instead


Searching for arrays
array values are stored in contiguous memory locations and 2D arrays are allocated in row-major order .


for loop knows how many times it needs to loop
while loop doesn't know how many times to loop

in python none = blank space

Records
a record is used to organise date by an attribute for example to store data for an address book the attributes could be the first_name_second_name
The data in this record is accessed through its name for example
first name.
The data in a record is unordered data structure but indices may be programmed to provide that data ordered on a particular field

Lists and tuples
lists and tuples are pythons versions of arrays and share may similarities but have minor differences

Tuples:
- Similar to records used to group together related values
- Similar to a 1D array
- Tuples cannot be edited once they have been assigned (immutable)
- Commonly used where it is important that data can be accessed and not changed
- Can contain values of different data types
- Items are retrieved again using an index, the same as an array
- Trying to assign a new value to the tuple will produce an error message
student = ('James', 'Smith', '30/01/2000', 'Computer Science') - TUPLE USES ()


 Lists:
- Can contain values of different data types
- Can be edited after they been assigned (mutable)
- Uses an index number to retrieve data - harder to use than attributes in records and less user friendly

A list is a simple structure of data that is cross between tuples and arrays . like tuples , lists can hold a range of data types but like arrays their elements can be edited (mutable)once they have been initiated . in principle a list is an ordered set of data organised by an index , so accessing the data is through an index value for that data.
 [list use square brackets]

when comparing lists and records the ability that records face to identify data by attributes rather than index does make the record structure more user friendly in use while being more complex to initialise.

CRAIGNDAVE FAM



STACKS
Stacks:
- Good for linear data
- LIFO data structure (last in, first out) -  add from the top and remove from the top (pile of pancakes)
- Adding data to a stack is called pushing
- Removing data is called popping
- Stacks are implemented into programs using a variable that points to the top of an array each time data is added or pointers within a computers memory.
- A pointer is used to locate the top of the stack starting at 0 and keep track of the top of the stack
- A stack overflow could happen if you are trying to push data into a full stack or if you try to pop data into an empty stack then an error will occur






IF stack pointer = maximum
         THEN report stack full
ELSE
         Increase stack pointer by +1
         set stack (stack pointer to data)
END IF


IF stack pointer = minimum
         THEN report stack empty
ELSE
        set data too stack (stack pointer)
        decrease stack pointer by -1
END IF



Queues:

 - FIFO (first in, first out) - most recent piece of data is therefore the last to be taken out
- The data within a queue does not physically move forward in the queue, instead two pointers are used to denote the front (data removed) and back (data added) of the queue.
 -the pointers move in memory location not the data
-queues unlike stacks are a circular data structure







- data can be pushed and popped like stacks , (the start and end pointer moves)
- the structure will allow the pointers to loop round as its circular meaning the end point can look like its before the start
-
 Q2 A stack contains the values 3, 4, 5, with 3 being the first value stored and 5 the last. Show how the stack changes after the following commands: POP, PUSH 7, POP, PUSH 8, PUSH 9.

start	pop	push 7	pop	push 8	push(9) 9
5		7		8	8
4	4	4	4	4	4
3	3	3	3	3	3

 
A -----------------------------------------


Q3  A queue contains the values 3, 4, 5, with 3 being 3 being the first value stored and 5 the last, Show how the queue changes after the following commands: POP, PUSH 7, POP, PUSH 8, PUSH 9.

A

--

3	4	5			start
	4	5			pop
	4	5	7		push 7
		5	7		pop
		5	7	8	push 8
		5	7	8	9 (push 9)