Hands-on with Linear data structures with Python
Data Structure is a particular way of storing and organizing data in a computer so that it can be used efficiently. They can be broadly classified as primitive, composite/abstract/non-primitive data structures. Primitive structures are the basic units of storage like boolean, integer, float, double. These are not that significant when compared to other types. In this post we will discuss about linear data structures and how to implement them in python (with built-in data structures in python).
Non-primitive data structure
The Non-primitive data structure cannot be directly controlled by computer commands, we need to define and implement the operations supported by them. Depending on language you use, we have some DS come as built-in (like arrays in most of programming language). We can further group DS into:
- Linear data structure
- Non-linear data structure
Non-linear data structure
Data items are not organized in a linear manner and can be associated with any other data element. For example, tree and graph.
Linear data structure
Data items are arranged in an orderly manner where the elements are attached adjacently.. For example, array, linked list, queue, stack.
Arrays & Linked-list
In python both array and list data structure are available by default i.e. they come in as built-in. Below section will describe how we can implement other data structures with the built-in ones.
Stack
Definition:
Stack is a non-primitive and linear data structure. It works on the principle of LIFO (Last In First Out). That is, the element that is added recently is removed first, and the element that is added first is removed at the end. Operations supported:
- Push()
- Pop()
Implementation:
Lets use ‘list’ data structure to implement stack.
Step 1: Create a list called stack.
>> stack = ["a","b","c","d"]>> stack
[‘a’, ‘b’, ‘c’, ‘d’]
Step 2: push() — Insertion to a Stack
we can use append() to add new elements to the stack as below. Here the last element being added is “economics”.
>> stack.append("1")>> stack.append("2")>> stack.append("3")>> stack
>> [‘a’,’b’, ‘c’, ‘c’, ‘1’, ‘2’, ‘3’]
Step 3: pop() — Deletion from a Stack
We can remove the element last added by using pop() method of list as below.
>> stack.pop()
‘3’>> stack.pop()
‘2’
We see that our stack follows the principle of LIFO (as mentioned above). Let’s check our stack after removing the last two elements.
>> stack
[‘a’, ‘b’, ‘c’, ‘d’, ‘1’]Queue
Definition:
Queue is a non-primitive and linear data structure. It works on the principle of FIFO (First In First Out). That is, the element that is added first is removed first, and the element that is added last is removed last. Operations supported:
- enqueue()
- dequeue()
Implementation:
Let’s use ‘list’ data structure to implement stack.
Step 1: Create a list called queue. To use list as a queue, we use collections.deque. It was designed to have faster appends and pops from both ends of a list. Now, we create a queue by using deque()on a list.
>> from collections import deque
>> queue = deque([“a”, “b”, “c”, “d”])
>> queue
deque([‘a’, ‘b’, ‘c’, ‘d’])Step 2: enqueue() — Insertion to a Queue
We can use append() to add an element at the end of the queue.
>> queue.append(“1”)
>> queue.append(“2”)
>> queue
deque([‘a’, ‘b’, ‘c’, ‘d’, ‘1’, ‘2’])Step 3: dequeue() — Deletion from a Queue
We can use popleft() to remove the element at the beginning of the queue.
>> queue.popleft()
‘a’
>> queue.popleft()
‘b’We see that our queue follows the principle of FIFO (as mentioned above). Let’s check our queue after removing the first two elements.
>> queue
deque([‘c’, ‘d’, ‘1’, ‘2’])