Arrays
- array: list data structure in which elements are stored in adjacent memory addresses
- arrays support direcrt access since it’s possible to mathematically calculate the address of a particular element
- you have to declare how big your array should be before you can use it
- it’s difficult to insert values into the middle of an array because elements need to be shifted along
- array elements are accessed using subscript notation eg
NUM[2] = 98
- their structure lends itself to processing using loops
Linked Lists
- constructing a linked list
- types of linked list
- sketching linked list insertion
- linked list methods
Arrays vs Linked Lists
- arrays
- support direct access
- static so you have to declare how many elements you want before you use it
- if you declare too many and don’t use them, you waste memory
- if you don’t declare enough then you have to create an entire new array and copy elements across
- adding and deleting elements from middle of array is problematic since existing elements need to be shifted
- linked lists
- only support sequential access since they only have a pointer to the head node
- dynamic meaning you don’t need to declare size
- never waste memory ebcause only contian nodes that have data in
- easy to insert and delete from middle of linked list
Stacks
- stack: special type of list in which you can only add and remove items from one end