Data Structure in 1 minute
Work In Progress
The Fast Lane to Data Structure using Python
Designing any system optimally data structure plays a key role. In the fast phase era we bring Data structure in a minute where we will briefly try to summarize different topics in data structure. We will be implementing data structure using
Data Structures
*(DS)
Linear DS
Data structure in which data elements are arranged sequentially or linearly, allowing straightforwad access to data elements , is called a linear data structure.
These structures are used when we need to organize and access data sequentially or linearly, ensuring straightforward and efficient traversal.
Non Linear DS
Non-linear data structures organize and store data elements in a manner where each element can connect to multiple elements, forming more complex relationships than the sequential arrangement of linear data structures.
These structures are particularly useful for representing hierarchical data and are often used in databases, file systems, and other applications that require complex data organization. Here are some key non-linear data structures:
Static Data Structure
Dynamic Data Structure
TREE
Graph
In the amusement park, static data structures are like the roller coaster rides. These rides are built with fixed tracks and seats. Once constructed, they don't change.
Fixed Size: Just like a roller coaster has a fixed number of seats and a fixed track, a static data structure has a fixed size. An array, for example, is a static data structure. When you create it, you decide how many seats (elements) it will have, and you can't change that later.
Predictable Structure: Every ride on the roller coaster follows the same path. Similarly, static data structures have a predictable structure and layout. You know exactly where each element is located.
Now, think of the Ferris wheel as the dynamic data structure. This ride can be more flexible in how it operates.
Variable Size: The Ferris wheel can add more cars (elements) if there are more visitors, or remove some cars if there are fewer people. Dynamic data structures, like linked lists, stacks, and queues, can grow and shrink in size during their lifetime.
Flexible Structure: The Ferris wheel can rearrange its cars, stop to let people on and off, and adjust its operations based on the current situation. Dynamic data structures are adaptable and can change their structure as needed.
A tree is a non-linear data structure consisting of nodes connected by edges. Each tree has a root node, and each node can have zero or more child nodes. Trees are used in various applications such as file systems, database indexing, and artificial intelligence for decision-making.
Important Terms in Trees:
Root: The topmost node in a tree.
Parent: A node that has one or more child nodes.
Child: A node that has a parent node.
Leaf: A node that has no children.
Subtree: A tree consisting of a node and its descendants.
Depth: The length of the path from the root to a node.
Height: The length of the longest path from a node to a leaf.
Finally, let's check out the adventure map of the amusement park, representing graph data structures.
Vertices and Edges: The adventure map shows various attractions (vertices) connected by paths (edges). Graphs consist of vertices (nodes) and edges (connections).
Undirected Graphs: In the map, if paths between attractions can be traveled in either direction, it's an undirected graph. Both directions are accessible.
Directed Graphs: If certain paths are one-way only, the map represents a directed graph, where edges have a direction indicating the way you can travel.
Weighted Graphs: Some paths might have difficulty levels or lengths associated with them. These are like weighted graphs, where edges have weights representing costs or distances.
Applications: Just as you use the adventure map to plan your day at the park, graphs are used in real life for network connections, social networks, and route planning.
Static Data Structure
Dynamic Data Structure
Array
Queue
Stacks
Linked List
An array is a Data structure which is used to store multiple elements of same Data type at continuous locations.
Important terms in Array-
Elements- Each item stored in an array is known as element
Index- Elements are stored in continuous locations so to access different elements index is used
Indexed Arrays: The index can be assigned automatically (*index always starts at 0)
Associative arrays: Are arrays that use named keys that you assign to them.
Multidimensional Arrays: It contains one or more arrays.
A queue is a linear data structure that follows the First In First Out (FIFO) principle. This means that the first element added to the queue will be the first one to be removed. Queues are commonly used in scenarios where order needs to be maintained, such as in task scheduling and managing requests in a server.
Important Terms in Queues:
Enqueue: The operation of adding an element to the back of the queue.
Dequeue: The operation of removing an element from the front of the queue.
Front: The first element in the queue.
Rear: The last element in the queue.
Types of Queues:
Simple Queue: Basic FIFO structure.
Circular Queue: The last position is connected back to the first position to make a circle.
Priority Queue: Elements are dequeued based on priority rather than order.
Double-Ended Queue (Deque): Elements can be added or removed from both the front and back.
A stack is a linear data structure that follows the Last In First Out (LIFO) principle. The most recently added element is the first one to be removed. Stacks are used in scenarios like reversing strings, parsing expressions, and backtracking algorithms.
Important Terms in Stacks:
Push: The operation of adding an element to the top of the stack.
Pop: The operation of removing an element from the top of the stack.
Top: The most recent element added to the stack.
Types of Stacks:
Simple Stack: Basic LIFO structure.
Double-Ended Stack: Can perform push and pop operations at both ends.
A linked list is a linear data structure where elements are not stored in contiguous memory locations. Instead, each element, called a node, contains a data part and a reference (or link) to the next node in the sequence. Linked lists are used for dynamic memory allocation and are efficient for insertions and deletions.
Important Terms in Linked Lists:
Node: The basic unit of a linked list, containing data and a reference to the next node.
Head: The first node in the linked list.
Tail: The last node in the linked list, which points to null.
Types of Linked Lists:
Singly Linked List: Each node points to the next node.
Doubly Linked List: Each node points to both the next and previous nodes.
Circular Linked List: The last node points back to the first node, forming a circle.
Multilevel Linked List: Nodes can point to nodes on different levels.
Level 2
Linked List
Singly Linked List
Doubly Linked List
Circular Linked list
Data : Link to Next Node
A singly linked list consists of nodes where each node stores data and a link to the next node, forming a linear structure.
It allows movement in only one direction (forward), making it efficient for quick additions or removals at the beginning O(1).
However, finding a specific position or navigating backward requires traversing the list from the start, which may take longer (O(n)).
Singly linked lists use less memory compared to some other types due to fewer connections per node.
Link to Prev Node : Data: Link to Next Node
A doubly linked list is a type of list where each piece of data (called a node) holds its information and two connections: one pointing to the next node and one to the previous node.
Unlike single linked lists, it allows moving both forward and backward through the list, making it handy for adding or removing items at both ends quickly O(1).
While it's efficient for ends, finding a specific spot in the middle takes longer (O(n)).
It's good for tasks that need quick ends' changes, but it uses more memory due to extra connections.
Deciding between single and doubly linked lists depends on whether you need frequent changes at both ends and how much memory you can use.
Last Node :Data: Link to First Node
A circular linked list is similar to a singly linked list, but the last node's link points back to the first node, creating a circle.
This circular structure doesn’t have a traditional end, making it useful for applications where continuous access is needed or for implementing features like round-robin scheduling.
It maintains the benefits and drawbacks of singly linked lists, including the need for traversal from the start to find a specific position (O(n)), but provides continuous access without a clear beginning or end.