What are linear data structures?
A linear data structure has data elements connected to each other so that elements are arranged in a sequential manner and each element is connected to the element in front of it and behind it. This way, the structure can be traversed in a single run.
Linear data structures can be implemented easily as computer memory is also arranged in a linear manner.
There are four types of linear data structures:
Array
An array is a collection of the same data types stored at contiguous memory locations. Arrays can be used in Python with the array module.
Below are various operations that can be done on arrays:
| Method | Description |
|---|---|
array(data type, value list) |
Used to create an array with data type and value list specified in its arguments. |
append() |
Used to add the value mentioned in its arguments at the end of the array. |
insert(i, x) |
Used to add the value(x) at ‘i’ position. |
pop() |
Removes the element at the position mentioned in its argument and returns it. |
remove() |
Used to remove the first occurrence of the value mentioned in its arguments. |
index() |
Returns the index of the first occurrence of value mentioned in its arguments. |
reverse() |
Reverses the array. |
import arrayarr=array.array('i',[1,2,3])print(arr)
Linked list
A linked list is a linear data structure in which elements are linked using pointers. It consists of nodes where each node contains a data field and a reference(link) to the next node in the list.
#Crearting a Nodeclass Node:def _init_(self,data):self.data=dataself.ref=None# Creating Linked Listclass LinkedList:def _init_(self):self.head=None# printing or traversal Operationdef Traversal(self):if self.head is None:# self.head==Noneprint("Linked List is Empty!!!")else:h=self.headwhile h is not None:print(h.data,"----->")h=h.ref
Stack
A stack is a linear data structure that stores data elements in a Last-In/First-Out (LIFO) or First-In/Last-Out (FILO) order. Here, a new element is added at one end and an element is removed from that end only. Stack in Python can be implemented in following ways:
-
list
-
collections.deque
-
queue.LifoQueue
The insert and delete operations are often called push and pop.
# Stack implementation using Liststack=[]def push():if len(stack)==size: # check wether the stack is full or notprint("Stack is Full!!!!")else:element=input("Enter the element:")stack.append(element)print(stack)def pop_element():if not stack:# or if len(stack)==0print("Stack is Empty!!!")else:e=stack.pop()print("element removed!!:",e)print(stack)def display():print(stack)size=int(input("Enter the size of Stack:"))while True:print("Select the Operation:\n 1.Push \n 2.Pop \n 3. Display \n 4. Quit")ch=int(input())if ch==1:push()elif ch==2:pop_element()elif ch==3:display()elif ch==4:breakelse:print("Invalid Option!!!")
Queue
A queue is a linear data structure that stores data elements in First-In/First Out(FIFO) manner, i.e., the element that’s inserted first will be removed first. Queue in Python can be implemented by the following ways:
- list
- collections.deque
- queue.Queue
# implementing Queue using List :from collections import dequeq=deque()q.append(10)q.append(100)q.append(1000)q.append(10000)print("Initial Queue is:",q)print(q.popleft())print(q.popleft())print("After Removing elements:",q)
