CompSci - Data Structures Flashcards
commit suicie later
Purpose of data structures
MOE
Manipulation
Organisation
Efficiency
Array definition
Collection of elements that are identified by unique indicies and stored in consecutive memory locations
Linked list
A web of nodes, each with its memory address, its data and a pointer to the next address.
SImple to add new items
Linear access
Stack definition
FILO or LIFO structure
Simple
Inflexible
Queue definition
FIFO or LILO structure
Simple
Inflexible
Binary trees
Web of nodes connected by branches and two child nodes for each individual node.
Mirrors hierachical relations
Limited child nodes
Adding / Removing nodes from linked lists
To add, change the pointer of the previous node to the address of the new node + change the pointer of the new node to the address of the next node
To remove, change the pointer of the previous node to the address of the next node.
Simple and doubly linked lists
Simple linked lists only have the pointers to the next node’s address and their data
address + data + pointer>
Doubly linked lists have the previous and next nodes’ addresses and their data
<pointer + address + data + pointer>
Stack and queue removing and inserting
For stacks, pushing and popping
For queues, enqueuing and dequeuing
Stack uses
Store actions in a program
Store function return addresses
Queue uses
Data buffer
Printing queue
Circular queue
Fixed size queue that has connected front and rear elements
Binary tree traversal
Pre-order: Rlr
Copying
In-order: lRr
In order output
Post-order: lrR
Delete
Balancing binary trees
If the difference between the heights of the left and right subtrees is > 1, the tree is unbalanced.
Fixed length
each field/record has a fixed length
Easy to search and calculate memory size
Potential redundant space
