Python Queues using Linked Lists

• Queues can be implemented using different data structures in Python, each with its own performance characteristics.

Queue Implementations

• Python List Implementation: Enqueue operations use list.append(x), and dequeue operations use list.pop(0). This is slow because every element must be moved forward when dequeuing.
• Circular Python List Implementation: Maintains a start index and adds elements to the end of the list, updating the end index for enqueue. Dequeue involves incrementing the start index and if the list becomes empty, resets the start index to 0. This is also slow because the list might become full.
• Linked List Implementation: Enqueue operations adds to the end of the list, and dequeue removes from the start. This is generally the preferred method.

Python Code for Queue Implementation using Linked List

• The code defines a Node class with fields for data and next.
• The implementation uses a Queue class with front and rear pointers. It also has a num_items attribute.
• Enqueue:
  • A new node is created with the given data.
  • If the queue is empty, both front and rear are set to the new node.
  • If the queue is not empty, the new node is added to the end, and rear is updated.
  • The item count is incremented
• Dequeue:
  • If the queue is empty, None is returned.
  • Otherwise, the data from the front node is stored.
  • The front is moved to the next node.
  • If this makes the queue empty, rear is set to None.
  • The item count is decremented
  • Returns the dequeued data.
• Size: the size() method returns the number of items in the queue.

Running time for Queue Implementation

• Enqueue operations has a running time of $O(1)$.
• Dequeue operations has a running time of $O(1)$.
• Size operations has a running time of $O(1)$.

Usefulness of Queues

• Breadth-first search explores all neighbors, then their neighbors, and so on.
• Task scheduling
• Signal processing

Midterm 2 Statistics

• The average score was 78.
• The median score was 80.
• The standard deviation was 15.

What is a Tree?

• Trees are collections of nodes and edges.
• Each node has a parent, except the root.
• Each node has zero or more children.
• A node with no children is called a leaf.
• Edges connect two nodes.
• There is a unique path from the root to every other node.
• Nodes can be reached from the root by following edges.
• There are no cycles in a tree.

Tree Examples

• Family trees organize lineage
• Directory structures organize files
• Organization charts represent company hierarchy
• Decision trees represent decision-making processes

Tree Vocabulary

• Root: Topmost node with no parent.
• Parent: Node directly above another node.
• Child: Node directly below another node.
• Siblings: Nodes with the same parent.
• Leaf: Node with no children.
• Edge: Connection between nodes.
• Path: Sequence of nodes and edges.
• Depth of a node: Length of the path from the root to the node.
• Height of a node: Length of the longest path from the node to a leaf.
• Height of a tree: Height of the root node.

Binary Tree

• Each node has at most two children.
• A left child.
• A right child.

Implementing Trees

• The code defines a Node class with attributes for data, left child, and right child.

Tree Traversal

• Tree traversal is how all nodes are visited.

Depth-First Search

• Explores each branch as far as possible before backtracking.
  • Pre-order: Visit the root, then the left subtree, then the right subtree.
  • In-order: Visit the left subtree, then the root, then the right subtree.
  • Post-order: Visit the left subtree, then the right subtree, then the root.

Breadth-First Search

• Explores all neighbors, then their neighbors, and so on.

def preorder(node):
 if node is not None:
 print(node.data)
 preorder(node.left)
 preorder(node.right)
def inorder(node):
 if node is not None:
 inorder(node.left)
 print(node.data)
 inorder(node.right)
def postorder(node):
 if node is not None:
 postorder(node.left)
 postorder(node.right)
 print(node.data)