Learning journey ->
Let’s begin with the basics.
What are Data Structures?
Data structures are a way to organize and store data efficiently in a computer’s memory. They are fundamental building blocks in programming and are essential for tasks like searching, sorting, and managing data in various applications, including game development and website management.
Here are some common data structures you should start with:
- An array is a collection of elements of the same data type, stored in contiguous memory locations. It’s indexed by integers, making it easy to access elements by their position.
Example (in Python):
my_array = [1, 2, 3, 4, 5]
- A linked list is a linear data structure where elements (nodes) are connected through pointers. There are singly linked lists (each node points to the next) and doubly linked lists (each node points to both the next and the previous).
Example (in Python):
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Create nodes and establish links
node1 = Node(10)
node2 = Node(20)
node3 = Node(30)
node1.next = node2
node2.next = node3
# Display the original linked list
def display_linked_list(head):
current = head
while current is not None:
print(current.data, end=" -> ")
current = current.next
print("None")
print("Original Linked List:")
display_linked_list(node1)
# Remove the element with value 20
current = node1
while current is not None:
if current.next and current.next.data == 20:
current.next = current.next.next
break
current = current.next
# Display the updated linked list
print("\nLinked List after Removing 20:")
display_linked_list(node1)There’s a more efficient and generalized way to remove nodes from a linked list while preserving the integrity of the list.
To handle the case where the first, specific value and last node (tail) needs to be removed from a singly linked list, you can modify the remove_node function to account for this situation.
In this function:
- We introduce a
prevvariable to keep track of the previous node while traversing the list. - When we find the node with the value to remove, we update the
nextpointer of the previous node (prev.next) to skip the node to be removed. This covers the case where the last node is the one to be removed.
Please see below:-
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Creating nodes
node1 = Node(10)
node2 = Node(20)
node3 = Node(30)
node4 = Node(40)
# Connecting nodes
node1.next = node2
node2.next = node3
node3.next = node4
# Display
def display_linked_list(head):
current = head
while current is not None:
print(current.data, end=" | ")
current = current.next
print("None")
print("Original List")
display_linked_list(node1)
def remove_node(head, value_to_remove):
if head is None:
return None
# Handle the case where the first node needs to be removed
if head.data == value_to_remove:
return head.next
current = head
while current.next is not None:
if current.next.data == value_to_remove:
current.next = current.next.next
return head
prev = current # Keep track of the previous node
current = current.next
# Handle the case where the last node needs to be removed
if current.data == value_to_remove:
prev.next = None
return head
# Remove node with value 10
node1 = remove_node(node1, 10)
# Remove node with value 20
node1 = remove_node(node1, 20)
# Remove node with value 40
node1 = remove_node(node1, 40)
print("\nRemove List")
display_linked_list(node1)
# Append nodes
new_node = Node(55)
current = node1
while current.next is not None:
current = current.next
current.next = new_node
new_node = Node(88)
current = node1
while current.next is not None:
current = current.next
current.next = new_node
print("\nAppend List")
display_linked_list(node1)
- A stack is a linear data structure with a last-in, first-out (LIFO) order. It’s used for tasks like tracking function calls, parsing expressions, and undo operations.
Example (in Python):
my_stack = []
my_stack.append(1)
my_stack.append(2)
my_stack.append(3)
# Now the stack is [1, 2, 3]
===> Another example <===
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
else:
return "Stack is empty"
def peek(self):
if not self.is_empty():
return self.items[-1]
else:
return "Stack is empty"
def size(self):
return len(self.items)
# Create a stack
stack = Stack()
# Push elements onto the stack
stack.push(10)
stack.push(20)
stack.push(30)
# Peek at the top element
top_element = stack.peek()
print(f"Top element: {top_element}")
# Pop elements from the stack
popped_element = stack.pop()
print(f"Popped element: {popped_element}")
# Check if the stack is empty
print(f"Is the stack empty? {stack.is_empty()}")
# Get the size of the stack
stack_size = stack.size()
print(f"Stack size: {stack_size}")
Output ===>>>
Top element: 30
Popped element: 30
Is the stack empty? False
Stack size: 2
———->
In this example:
We define a Stack class with push, pop, peek, size, and is_empty methods.
We create a stack, push elements onto it, peek at the top element, pop elements off it, check if it’s empty, and get its size.
The output will demonstrate the basic functionality of a stack. You’ll notice that the last element pushed (30) is the first one popped, confirming the Last-In, First-Out (LIFO) behavior of a stack.
- A queue is a linear data structure with a first-in, first-out (FIFO) order. It’s used for tasks like managing tasks in a printer queue or handling requests in a web server.
Example (in Python):
from collections import deque
my_queue = deque()
my_queue.append(1)
my_queue.append(2)
my_queue.append(3)
# Now the queue is [1, 2, 3]
- Trees are hierarchical data structures with a root node and child nodes. They are used in many algorithms and are the basis for more complex data structures like binary trees and heaps.
Example (a simple binary tree in Python):
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
These are some of the foundational data structures. Start by understanding how each works, how to perform basic operations on them (insertion, deletion, traversal), and when to use them in different scenarios.