We started off by having a brief introduction to data structures and algorithms in our first article, lets now have a more in depth look into each of these:
Note: I’ll be using python through these series of articles.
Deep dive into data structures:
In our first article, Introduction to data structures and algorithims, we began by defining what data structures are, now let's have a more detailed understanding of them.
The term data structure is made up of two words, “Data” and “Structures”. Data itself means collection of some information e.g some users information. Structure in simple words can be described as organizing. Combining the two, data structures can be described as organizing a bunch of data in such a way that it can be used efficiently with respect to time and memory.
Before having a deeper look into the classic and fundamental data structures, let’s first distinguish the difference between data structures and data types:
Data type: this is a classification that defines which type of value a variable has and which type of mathematical, relational or logical operations can be applied to it without an error. Examples: float, strings, integers e.t.c
Data structures: as we have said, data structures are collection of different forms and types of data that has a set of specific operations that can be performed. It can be described as a collection of data types. Examples: stacks, queues, linked lists, binary tree e.t.c
Now let’s have a deeper look into the classic and fundamental data structures:
A. Array:
A data structure that stores data types by allocating memory slots. It is the simplest way to store information in a computer.
All elements stored in an array have to be of the same data type.
Arrays are usually used in numerical computation tasks or as a supporting data structure to implement other data structures e.g stacks, lists, queues.
Implementing array data structure in python:
In order to use arrays in python you’ll have to import a library like NumPy library.
Python has a numeric implementation of arrays with the array module
It helps users specify the python data type that the array holds at initiation.
Python array comes in with built in functions like:
append(item): for adding items to the end of the array.
count(item): for counting the number of occurrences of an item within an array.
insert(item, index): to insert item at position index.
remove(item): for deleting the item.
You can check out more methods over here.
There are more specialized implementations of arrays in python:
bytes objects: this is an immutable sequence of single bytes.
bytearray(): this is a mutable arrays of single bytes.
str objects: immutable arrays of unicode characters declared as single quotes, double quotes or tripple quotes.
tuple objects: an immutable sequence for storing multilpe items in a single variable.
B. Stack(LIFO):
This is a container of objects where item insertion and deletion are carried out according to last in first out (LIFO) principle.
The insert and deletion operations are normally called push() and pop() respectively.
A practical example of where stack is used in an application is: the “undo” button in a text editor checks the last inserted command, and removes it from the stack.
Some other functions associated with stack are:
empty(): returns whether a stack is empty
size(): returns the size of the stack
top() / peek(): returns a reference to the topmost element of the stack.
Implementing stack data structure in python:
Stacks in python can be implemented using the following ways:
- Lists
- Collections.deque
- Queue.LifoQueue
1. Lists:
Pythons built in lists can be used as a stack.
append() is used to put elements on top of the stack while pop() is used to remove the elements in the LIFO order.
One of the shortcomings of using list as stack is speed issues as the list grows. If the stack grows bigger than the block of memory that currently holds it, then python needs to do some memory allocations. This can cause some append() calls taking more time than others.
2. collections.deque:
Python stack can also be implemented using the deques class from the collections module.
This is preferred from the list in the cases where we need quicker append and pop operations from both ends of the container.
The same methods, append() and pop(), used in lists are also used in deque.
3. Queue.LifoQueue:
Queue module in python has a LIFO queue which works as a stack.
Data is inserted using the put() function and removed using the get() function.
There are a number of functions available in this module, they can be found here.
C. Queue (FIFO):
They are collection of items that hold elements. They collect elements according to the “First in First out” concept. The first element to be added is the first to be deleted.
The two main operations are; enqueue(): adding item to the back of the queue and dequeue(): remove item at the front of the queue.
Implementing Queue data structure in python:
Queues in python can be implemented using the following methods:
- Lists
- collections.deque
- queue.Queue
1. Lists:
You can implement the FIFO principle using slicing. This is well explained in the python documentation.
Instead of using enqueue() and dequeue(), the append() and pop() functions are used. Lists are slow in this since in order to add or delete the item it will require you to shift all the other elements by one.
2. collections.deque:
Queue in python can also be implemented using the deque class from the collections module.
Instead of enqueue() and dequeue(), append() and popleft() functions are used.
Deques are preferred over lists when we need a quicker add and remove operations from both ends of the container.
3. queue.Queue:
Queue is a built-in module of python used to implement the queue.
queue.maxsize(maxsize) initializes a variable to a maximum size of maxsize.
To add items you use the put() function and to remove or get an item you use the get() function.
D. Map:
This is a data structure, (also referred to as hash tables, lookup tables, hashmaps or associative arrays), which is a collection of named items.
It is efficient in item insertion, lookup and deletion. But it requires more space than other data structures, since it is implemented as a key-value table.
Maps have the following operations:
- set(key, value) - adds a key-value mapping to the map.
- delete(key) - removes a key and its associated value.
- get(key) - retrieves the value associated with the given key.
Implementing map data structure in python:
Maps in python can be implemented by using dictionaries.
Dictionaries are used to store values in key value pairs. Python has a built in function dict() that can be used to create dictionaries.
Values in the dictionary can be accessed using the key values, built in functions and loops.
For the built in functions we have:
- get() - enables you to access the items
- keys() - this returns a list of all the keys in the dictionary
- values() - this will return a list of all values in the dictionary
You can check more on the access methods over here.
Values in the dictionary can be changed using the following method:
- Update() - updates the dictionary with items of the given argument.
More on how to change the values an implement the update() function can be found here.
The update() method can also be used to add an item to the dictionary. More on how to add an item can be found here.
Items can be removed using the pop() function. There are other methods on how to remove an item that can be checked here.
E. Graph:
Graph is a type of data structure that arranges data as multiple nodes. The nodes are connected together using edges. They are used to model pairwise relations between objects.
They are used to model networks that naturally occur in real life. They are used in social networks such as Facebook and LinkedIn.
Implementing graph data structures in python:
The first way is by use of a dictionary. The keys in the dictionary used are the nodes of our graph and the corresponding values are the lists with each node.
For more on how to implement a graph using dictionaries in python, you can check out here.
We can also use the NetworkX Library. This library allows you to easily add or remove nodes and edges. It also comes with a lot of out-of-the-box methods such as: finding the shortest path between the nodes, measures of associativity and centrality within the graph.
You can check out more on NetworkX library here.
D. Set:
This is a data structure in python with an unordered and unindexed collection of elements. Each element in a set is unique and the set does not allow any duplication of elements.
Sets can be used to perform mathematical set operations like union, intersection, symmetric difference e.t.c
Sets are usually used for validating data, finding the difference between the two data sets, joining unique data sets together and more.
Implementing set data structure in python:
There are two main methods for implementing sets in python:
Using the set function available in python.
Typing the list of various elements using the curly “{}” braces.
Sets have the following operations:
add() function: this function adds an element to the set.
update() function: this function is used to add multiple elements to the set. Items from another set can also be added using this function.
remove() and discard() functions: they are used to remove an item from a set.
Wrapping up:
As we finalize ,let's have some recap, in this article we’ve learned about:
1. The 6 fundamental data structures
2. How to implement the various data structures in python
I'll be giving a thorough explanation on algorithms in the next article. Stay tuned!
Top comments (0)