Advanced Data Structures

Collections in python
Collections

• The collection Module in Python provides different types of

containers. A Container is an object that is used to store different
objects and provide a way to access the contained objects and iterate
over them.
• Built in collection
• Collection from collection module
Built in Containers

Tuple List Dictionary

Collections-Container

Counters OrderedDict DefaultDict ChainMap

NamedTuple DeQue UserDict UserList

UserString
counters
• A counter is a sub-class of the dictionary. It is used to keep the count
of the elements in an iterable in the form of an unordered dictionary
where the key represents the element in the iterable and value
represents the count of that element in the iterable
Counter
• The counter object can be initialized using the counter() function and
this function can be called in one of the following ways:

• With a sequence of items

• With a dictionary containing keys and counts
• With keyword arguments mapping string names to counts
• Counter Example
OrderedDict

• An OrderedDict is also a sub-class of dictionary but unlike

dictionary(until python version 3.7), it remembers the order in which
the keys were inserted.
Ordered Dict
Points to Remember
• Key value Change: If the value of a certain key is changed, the
position of the key remains unchanged in OrderedDict.

• Deletion and Re-Inserting: Deleting and re-inserting the same key will
push it to the back as OrderedDict, however, maintains the order of
insertion.
DefaultDict

• A DefaultDict is also a sub-class to dictionary. It is used to provide

some default values for the key that does not exist and never raises a
KeyError.
Defaultdict
defaultdcit
Chain map
• A ChainMap encapsulates many dictionaries into a single unit and
returns a list of dictionaries.
Chain map
namedtuple()

• The Python namedtuple() function returns a tuple-like object with

names for each position in the tuple. It was used to eliminate the
problem of remembering the index of each field of a tuple object in
ordinary tuples.
• 1. _make(): This function is used to return a namedtuple() from the
iterable passed as argument.

• 2. _asdict(): This function returns the OrderedDict() as constructed

from the mapped values of namedtuple().
Named tuple
• A NamedTuple returns a tuple object with names for each position
which the ordinary tuples lack
Named tuple
Functions –named tuple
• Access by index: The attribute values of namedtuple() are ordered
and can be accessed using the index number unlike dictionaries which
are not accessible by index.
• Access by keyname: Access by keyname is also allowed as in
dictionaries.
• using getattr(): This is yet another way to access the value by giving
namedtuple and key value as its argument.
Conversion Operations

• _make() :- This function is used to return a namedtuple() from the

iterable passed as argument.
• _asdict() :- This function returns the OrderedDict() as constructed
from the mapped values of namedtuple().
• using “**” (double star) operator :- This function is used to convert a
dictionary into the namedtuple().
conversion
Additional
Operation
 • Deque (Doubly Ended Queue) in
Python is implemented using the
module “collections“. Deque is
preferred over a list in the cases
where we need quicker append and
pop operations from both the ends
Deque of the container
Types of Restricted Deque Input

• Input Restricted Deque: Input is limited at one end while deletion is

permitted at both ends.
• Output Restricted Deque: output is limited at one end but insertion is
permitted at both ends.
Opreations
• append():- This
function is used to
insert the value in its
argument to the right
end of the deque.
• appendleft():- This
function is used to
insert the value in its
argument to the left
end of the deque.
Popping Items
• pop():- This function is
used to delete an
argument from the
right end of the deque.
• popleft():- This
function is used to
delete an argument
from the left end of
the deque.
Opreations
• index(ele, beg, end):- This
function returns the first index of
the value mentioned in
arguments, starting searching
from beg till end index.
• insert(i, a) :- This function inserts
the value mentioned in
arguments(a) at index(i) specified
in arguments.
• remove():- This function removes
the first occurrence of the value
mentioned in arguments.
• count():- This function counts the
number of occurrences of value
mentioned in arguments.
Deque
• len(dequeue):- Return the current size of the dequeue.
• Deque[0] :- We can access the front element of the deque using
indexing with de[0].
• Deque[-1] :- We can access the back element of the deque using
indexing with de[-1].
opreations
• extend(iterable):- This function is used to add multiple values at the
right end of the deque. The argument passed is iterable.
• extendleft(iterable):- This function is used to add multiple values at
the left end of the deque. The argument passed is iterable. Order is
reversed as a result of left appends.
• reverse():- This function is used to reverse the order of deque
elements.
• rotate():- This function rotates the deque by the number specified in
arguments. If the number specified is negative, rotation occurs to the
left. Else rotation is to right.
UserList
• Python supports a List like a container called UserList present in the
collections module. This class acts as a wrapper class around the List
objects. This class is useful when one wants to create a list of their
own with some modified functionality or with some new
functionality. It can be considered as a way of adding new behaviors
for the list. This class takes a list instance as an argument and
simulates a list that is kept in a regular list. The list is accessible by the
data attribute of the this class.
userlist
userdict
• Python supports a dictionary like a container called UserDict present
in the collections module. This class acts as a wrapper class around
the dictionary objects. This class is useful when one wants to create a
dictionary of their own with some modified functionality or with
some new functionality. It can be considered as a way of adding new
behaviors to the dictionary. This class takes a dictionary instance as an
argument and simulates a dictionary that is kept in a regular
dictionary. The dictionary is accessible by the data attribute of this
class.
User string
• Python supports a String like a container called UserString present in
the collections module. This class acts as a wrapper class around the
string objects. This class is useful when one wants to create a string of
their own with some modified functionality or with some new
functionality. It can be considered as a way of adding new behaviors
for the string. This class takes any argument that can be converted to
string and simulates a string whose content is kept in a regular string.
The string is accessible by the data attribute of this class.