Python Data Structures

Python Data Structures

What is a Data Structure?

Data structure is a way of defining, storing & retrieving of data in a structural & systematic way. A data structure may contain different type of data items.

What are linear and non linear data Structures?

• Linear: A data structure is said to be linear if its elements form a sequence or a linear list. Examples: Array. Linked List, Stacks and Queues.

• Non-Linear: A data structure is said to be non-linear if traversal of nodes is nonlinear in nature. i.e, These are the data structures in which there is no sequential linking of data elements. Any pair or group of data elements can be linked to each other and can be accessed without a strict sequence. Example: Graph and Trees.

Linear Data Structures

• Array: It is a sequential arrangement of data elements paired with the index of the data element.

• Linked List: Each data element contains a link to another element along with the data present in it.

• Stack: It is a data structure which follows only to specific order of operation. LIFO(last in First Out) or FILO(First in Last Out).

• Queue: It is similar to Stack but the order of operation is only FIFO(First In First Out).

• Matrix: It is two dimensional data structure in which the data element is referred by a pair of indices.

QUIZ - 1

Lab Experiment - 1

Quiz - 1

Non-Linear Data Structures

• Binary Tree: It is a data structure where each data element can be connected to maximum two other data elements and it starts with a root node.

• Heap: It is a special case of Tree data structure where the data in the parent node is either strictly greater than/ equal to the child nodes or strictly less than it’s child nodes.

• Hash Table: It is a data structure which is made of arrays associated with each other using a hash function. It retrieves values

  using keys rather than index from a data element.

• Graph: It is an arrangement of vertices and nodes where some of the nodes are connected to each other through link.

Quiz - 2

Lab Experiment - 2

Quiz - 2

Python Specific Data Structures

These data structures are specific to python language and they give greater flexibility in storing different types of data and faster processing in python environment.

• List: It is similar to array with the exception that the data elements can be of different data types. You can have both numeric and string data in a python list.

• Tuple: Tuples are similar to lists but they are immutable which means the values in a tuple cannot be modified they can only be read.

• Dictionary: The dictionary contains Key-value pairs as its data elements.

Stack

A stack is a linear data structure that stores items in a Last-In-First-Out (LIFO) or First-In-Last-Out (FILO) manner.

In stack, a new element is added at one end and an element is removed from that end only.

The insert and delete operations are often called push and pop.

Basic Operations of Stack

• empty() – Returns whether the stack is empty.

• size() – Returns the size of the stack.

• top() – Returns a reference to the top most element of the stack.

• push(g) – Adds the element ‘g’ at the top of the stack.

• pop() – Deletes the top most element of the stack.

Implementation of Stack

• Using Array

• Using Linked List

Implementation of Stack using Array

Python’s built-in data structure array can be used as a stack.

Instead of push(), append() is used to add elements to the top of stack while pop() removes the element in LIFO order.

Implementation of Stack using Linked List

A stack can be easily implemented through the linked list. In stack Implementation, a stack contains a top pointer. which is “head” of the stack where pushing and popping items happens at the head of the list. first node have null in link field and second node link have first node address in link field and so on and last node address in “top” pointer.

Quiz - 3

Lab Experiment -3

Quiz - 3