Flashcards
Data structures 4.2.1
Cards in this deck (20)
- 1Data StructuresA data structure is simply a format for how data is stored
- 2ArraysA data structure that is built into programming languages is an array.
Arrays are static data structures – once created, they are fixed and can’t easily be expanded - 3ArraysArrays can be one-dimensional or n-dimensional
Arrays are used to store multiple values of the same data type, for example an int array could store multiple integers - 4ArraysWhen an array is declared, it’s size must be specified.
When an array of size 4 is declared, 4 consecutive memory locations are reserved for the data.
The memory locations before and after these reserved blocks will continue to be used - 5ArraysThis is why arrays can’t be resized – the memory needed to expand them will likely be in use
- 6Array advantagesvery quick to access.
- 7Array disadvantagesWhile their access speed is excellent, arrays have some major limitations
Using this array, what happens if we want to insert “horse” after “cow”?
The only way to do it is to move every value below it down one
As the array gets larger, this operation takes longer - 8Array disadvantages
- 9Array disadvantagesIf we want to remove a value from an array, it will leave a gap
Each value below it will need moving up – another slow operation
Once an array is full, the only way to add more data is to create a new, larger array in another memory location and copy each value over – also a slow operation - 10Array SummaryArrays are static data structures
They are fast to access (read, alter values)
They are slow to insert and remove values
They can’t easily be resized - 11ListsAnother data structure that does the same job as an array is a list
From the user perspective, a list is very similar to an array – python uses lists where java uses arrays - 12ListsLists are dynamic data structures, their size isn’t fixed, and new values can easily be appended, expanding the list dynamically
- 13ListsIn python, myList.append(6), will add 6 to the end of the list, making it bigger
- 14ListsLists don’t block out consecutive memory locations
Each list entry contains two parts – the value being stored and a pointer to the memory location of the next value - 15List advantagesThey don’t have a fixed size – a new value can be added in any free memory location, and a new pointer added to the previous value
- 16List advantagesInserting or removing a value just requires the pointer of the previous value to be changed – no copying needed
- 17List disadvantagesBecause the values aren’t stored in consecutive memory locations, the computer can’t jump straight to the correct location, it has to start at the first value, and follow the pointers through the entire list until it gets to the value
- 18List disadvantagesTo get to value 3, it would need to check the pointer of value 0 to find value 1, then use it’s pointer to find value 2, then use it’s pointer to find value 3
- 19List SummaryLists are dynamic data structures
They can easily be expanded or shrunk
Values can be easily inserted or removed
Accessing values is slower than in an array, and gets slower as the list gets larger - 20When to useIf access speed is important, or you know the size won’t change, use a list
If you don’t know how many values will be needed, use a list
Information
- Description
- Flashcards on Data structures 4.2.1, created by Ed Allen on 21/04/2020.
- Created by
- Ed Allen
- Views
- 0
- Rating