Circular Data Structures Quiz

Circular List

• Data structure with nodes linked in a circle, the last node points to the first node
• A node has an integer value (int info) and a pointer to the next node in the list (struct list *next)
• Defined using a type definition typedef struct node *ptr;
• Memory allocated using malloc(sizeof(struct node))
• Error handling for memory allocation is included using an if statement (if (p != null))

Inserting a Node

• insert(ptr p, int n) function inserts n nodes after the given pointer p
• Iterates n times, allocating a new node
• Links the nodes sequentially in a circle
• Creates an iterative chain from the original node (p) onward
• The last node in the chain is linked back to the original node (p).

Inserting a Node at the Start

• insert(ptr p) function inserts a new node at the beginning of the circular list
• locates the last node in the list
• Allocates a new node (q)
• Sets the next pointer of the new node (q->next) to point to the node after the last node
• Sets the next pointer of the last node (p->next) to point to the new node

Inserting a Node at the End

• insert(ptr p) function inserts a new node at the end of the circular list
• Iterates through the list stopping before original node p->next
• Allocates a new node (q)
• Sets the next pointer of the new node (q->next) to point to the node after the last node
• Sets the next pointer of the last node (p->next) to point to the new node

Replacing Data

• replace(ptr p, int n, int num) function replaces the data in the nth node of the list with num.
• Handles empty list case using if (p == null): Prints "empty list"
• Iterates n times through the list to reach the nth node
• Assigns the given data num to the nth node

Circular List Limitations

• No backward traversal possible
• Cannot delete a node knowing only a pointer to that node directly

Doubly Linked List

• Each node has two pointers: One to the next node and one to the previous node.
• Enables traversal in both directions.

Creating a Single Node

• struct node definition with int info, struct node *pre, and struct node *next.
• typedef struct node *ptr; statement defines a pointer to struct node.
• The code provides a Void main() function that demonstrates creating a struct node and populating its elements with example values (p->info = 10; p-> pre = null; p-> next = null;)

Trees

• Non-linear data structures
• Each node can point to more than one node
• A root node is the topmost node in a tree
• Nodes organize data hierarchically.

Binary Tree

• Tree where each node has at most two children (left and right)
• Can have empty subtrees

Terminologies

• Father: A node that has another node as a child node
• Son: A node that is a child of another node
• Leaf: A node with no children
• Ancestor: A node that has another node as a descendant
• Descendant: A node that is a child or a descendant of another node
• Brothers: Nodes that share the same parent node.

Almost Complete Binary Tree

• Binary tree of depth D
• Any node in a level less than D-1 has two sons
• Any node in the tree with a right descendant in level D should have a left son; and every left descendant in that node is a leaf at level D or has two sons.

Tree Construction

• The root of the tree is the first element added to the tree
• Inserting nodes based on the order they would appear on a tree, right node is greater, left node is smaller

Operations

• Finding duplicates in the tree
• Traversal (pre-order, in-order, post-order)
• Searching
• Sorting

Test your knowledge of circular linked lists, including how to insert nodes and manage memory allocation. This quiz covers the fundamental concepts of defining and manipulating this unique data structure in programming. Ensure you understand both the circular structure and node management techniques.