Data Structures and ADT Quiz

Data Structure

• Data structures are organized formats for storing, managing, and retrieving data efficiently.
• Common types include arrays, linked lists, stacks, queues, trees, and graphs.
• They facilitate operations like searching, sorting, inserting, and deleting data.

Abstract Data Type (ADT)

• An ADT is a model for a data type where its behavior is defined by a set of operations.
• Key properties of ADTs include encapsulation, where implementation details are hidden, providing a clear interface.
• Examples of ADTs include lists, stacks, queues, and trees, each supporting various operations.

List ADT

• The List ADT is a collection of elements with a defined ordering, allowing duplicates.
• Main operations include insertion, deletion, access, search, and traversal.
• Lists can be implemented in several ways, including arrays and linked lists.

Insertion in Singly Linked List

• A singly linked list consists of nodes, each containing data and a pointer to the next node.
• Insertion can happen at various positions: at the beginning, at the end, or in the middle of the list.
• Inserting at the head involves adjusting the head pointer to a new node pointing to the former first node.
• Inserting at the tail requires traversing to the last node and linking it to the new node.
• Insertion in the middle involves finding the appropriate node and adjusting pointers accordingly.
• Complexity of insertion operations is generally O(1) when adding at the head, while it's O(n) for finding the right position.