HCI 10. Data Structures

Hwa Chong Institution H2 Computing 1 10 Data Structures Learning Outcome 10.1 Overview of Collections Collection is a group of items that we want to treat as conceptual unit. Collections can be homogeneous when all items in the collection must be of the same type, or heterogeneous when items can be of different types. For example, lists are heterogeneous in Python. 10.1.1 Linear Collections Ordered by position Examples: Grocery lists, Stacks of dinner plates, A line of customers waiting at a bank 10.1.2 Hierarchical Collections Structure reminiscent of an upside-down tree D3’s parent is D1; its children are D4, D5, and D6 Examples: a file directory system, a company’s organizational tree, a book’s table of contents Data Structures Understand the concept of static allocation of memory Understand the concept of dynamic allocation of memory Create, insert, and delete operations for stack and queue (linear and circular) Understand the concept of free space list (which could be another linked list or an array). Create, update (edit, insert, delete) and search operations for a linear linked list. Exclude: doubly-linked list and circular linked list Create, update (edit, insert, delete*) and search operations for a binary search tree. Exclude: deletion of nodes from binary search tree Understand pre-order, in-order and post-order tree traversals; and application of in-order tree traversal for binary search tree. Programming Elements and Constructs Understand the use of stacks in recursive programming Implementing Algorithms and Data Structures Write programs to implement operations for stacks, queues (linear and circular), linear linked lists and binary search trees. Exclude: doubly-linked list and circular linked list

Hwa Chong Institution H2 Computing 2 10.1.3 Graph Collections Each data item can have many predecessors and many successors D3’s neighbors are its predecessors and successors Examples: Maps of airline routes between cities; electrical wiring diagrams for buildings 10.1.4 Unordered Collections Items are not in any particular order. One cannot meaningfully speak of an item’s predecessor or successor Example: Bag of marbles 10.1.5 Operations on Collections ● Traversal: This operation visits each item in a collection ● Search and retrieval: Search for a given target item or an item at a given position ● Insertion: Adds an item to a collection at a given position ● Removal: Deletes a given item or the item at a given position ● Determine the size: Determines the size of a collection – the number of items it contains 10.1.6 Abstraction and Abstract Data Types ● To a user, a collection is an abstraction ● In Computer Science, collections are abstract data types (ADTs) - ADT users are concerned with learning its interface - Developers are concerned with implementing their behavior in the most efficient manner possible “Data structure” and