Data Structure 7 Flashcards
singly-linked list
a data structure for implementing a list ADT, where each node has data and a pointer to the next node
doubly-linked list
a data structure for implementing a list ADT, where each node has data, a pointer to the next node, and a pointer to the previous node. The list structure typically points to the first node and the last node
hash table
a data structure that stores unordered items by mapping (or hashing) each item to a location in an array (or vector)
binary tree
each node has up to two children, known as a left child and a right child.
all(list)
True if every element in list is True (!= 0), or if the list is empty.
any(list)
True if any element in the list is True.
max(list)
Get the maximum element in the list.
min(list)
Get the minimum element in the list.
sum(list)
Get the sum of all elements in the list.
list nesting
a list inside another list
Ex: my_list = [[5, 13], [50, 75, 100]]
my_list[start:end]
Get a list from start to end (minus 1).
Code:my_list = [5, 10, 20]print(my_list[0:2])
Output: [5, 10]
my_list[start:end:stride]
Get a list of every stride element from start to end (minus 1).
Code: my_list = [5, 10, 20, 40, 80]print(my_list[0:5:3])
Output: [5, 40]
my_list[start:]
my_list[start:]
my_list[:end]
Get a list from beginning of list to end (minus 1).
Code: my_list = [5, 10, 20, 40, 80]print(my_list[:4])
Output: [5, 10, 20, 40]
my_list[:]
Get a copy of the list.
list comprehension
A Python construct for creating a list in terms of conditions on other lists
new_list = [expression for name in iterable]
dictionary
another type of container object that is different from sequences like strings, tuples, and lists. References to objects as key-value pairs - each key in the dictionary is associated with a value
dict method
a function provided by the dict type that operates on a specific dict object.
List
an ADT for holding ordered data.
Ex: Array, linked list
Stack
an ADT in which items are only inserted on or removed from the top of a stack.
Ex: Linked List
Queue
an ADT in which items are inserted at the end of the queue and removed from the front of the queue.
Ex: Linked List
Deque
an ADT in which items can be inserted and removed at both the front and back.
Ex: Linked list
Bag
an ADT for storing items in which the order does not matter and duplicate items are allowed.
Ex: Array, Linked List
Set
an ADT for a collection of distinct items.
Ex: Binary search tree, hash table
Priority queue
a queue where each item has a priority, and items with higher priority are closer to the front of the queue than items with lower priority.
Ex: Heap
Dictionary (Map)
an ADT that associates (or maps) keys with values.
Ex: Hash table, binary search tree
algorithm
sequence of steps to solve a computational problem or perform a calculation
