- What is the Difference Between Data Type and Data Structure?
Data type is one of the forms of a variable to which the value can be assigned of a given type only. Data structure is a collection of data of different data types.
Data types don't involve time complexity while data structures involve the concept of time complexity.
- Python data types
Numeric data types: int, float, complex String data types: str Sequence types: list, tuple, range Binary types: bytes, bytearray, memoryview Mapping data type: dict Boolean type: bool Set data types: set, frozenset
The simplest data structure, which is a contiguous block of memory.
- Time complexities of working with arrays
Retrieving and updating A[i] takes O(1) time. To delete the element at index i from an array of length n is O(n - i) time compl.
Array problems often have simple brute-force solutions that use O(n) space, but there are subtler solutions that <use the array itself> to <reduce space> complexity to O(1).
Filling an array from the front is slow, so see if it's possible to <write values from the back> [2 <ref-label>
].
Instead of deleting an entry (which requires moving all entries to its left), consider <overwriting> it.
The key property of a list is that it is dynamically-resized.
L = [1] + [0] * 10 # [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
list(range(100))
List comprehension.
len(A), A.append(x), A.remove(x), A.insert(i, x)
where i is index# check if value is present (O(n))
a in A
# difference between
B = A, B = list(A)
# deep and shallow copy
copy.copy(A)
and copy.deepcopy(A)
A.reverse()
(in-place), reversed(A)
(returns an iterator)A.sort()
(in-place), sorted(A)
(returns a copy)del A[i]
, del A[i:j]
# binary search for sorted lists
bisect.bisect(A, 6)
, bisect.bisect_left(A, 6)
, bisect.bisect_right(A, 6)
s.extend(t)
appends t to s (items in t to the end of list s)s[:0] = t prepends (adds items in t to the beginning of s)
s = [1, 2]
t = [3, 4]
s.extend(t)
print(s) #[1, 2, 3, 4]
# last three items [
2 <ref-label>
]A[-3:], or some items from the end A[-3:-1]
# step
A[1:5:2] from 1 to 5, every 2nd item
A[5:1:-2] the same in reverse order (from item 5 to 1, every 2nd but counting from the end)
B = A[:] shallow copy of A into B
# rotate a list (like for the Caesar's cipher we rotate the alphabet to make a mask)
A[k:] + A[:k]
# Exclude an item
>>> L= [1,2,3,4] #e.g. to exclude item with i=1 >>> L[:1]+L[1+1:] [1, 3, 4]
Occurs when an arithmetic operation attempts to create a numeric value that is outside of the range that can be represented with a given number of digits (either higher than the maximum or lower than the minimum representable value).
Because of a possibility of integer overflow, we might sometimes use an array to represent an integer (i.e. [1,2,3,4] instead of 1234) when doing arithmetic.
Also known as "bignum" or simply "long arithmetic" is a set of data structures and algorithms which allows to process much greater numbers than can be fit in standard data types.