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 “ concrete data type ” refer to the internal representation of an ADT’s data. The two data structures most often used to implement collections in most programming languages are arrays and linked structures which uses static and dynamic ap proaches in storing and accessing data in the computer’s memory respectively.

Hwa Chong Institution H2 Computing 3 10.2 Array Array is the underlying data structure of a Python list, but it is more restrictive than Python lists. We have learnt and practiced enough for lists, but here let’s have a recap on the concepts of array, and compare with linked structures. 10.2.1 Data Structure An array represents a sequence of items of the same data type (homogeneous). Items can be accessed, retrieved, stored or replaced at given index positions. Random Access and Contiguous Memory Array indexing is a random access operation Address of an item: base address + offset. Index operation has two steps: 1. Fetch the base address of the array’s memory block 2. Return the result of adding the (index * k) to this address, where k is the number of memory cells required by an array item. Static Memory Arrays are static. The capacity or length of the array is determined at compile time, so need to specify the size with a constant. Physical Size and Logical Size - The physical size of an array is its total number of array cells - The logical size of an array is the number of items currently in it - To avoid reading garbage, must track both sizes In general, the logical and physical size tell us important things about the state of the array: - If the logical size is 0, the array is empty - Otherwise, at any given time, the index of the last item in the array is the logical size minus 1. - If the logical size equals the physical size, there is no more room for data in the array

Hwa Chong Institution H2 Computing 4 10.2.2 Operations on Arrays Indexing is the key tool in traversal, search and retrieval in an array. We now discuss the implementation of insertion and removal on arrays. In our examples, we assume the following data settings: The array, A, has an initial logical size of 0 and a default physical size, or capacity, of 5. Inserting an Item into an Array ● Check for available space before attempting an insertion ● Shift items from logical end of array to target index position down by one - To open hole for new item at target index ● Assign new item to target index position ● Increment logical size by one Example: Insert item D5 at position 1 in an array of four items Here is the pseudo-code for the insertion operation: # check for available space IF (logicalSize = physicalSize): OUTPUT “ No room for insertion !!” ELSE # shift items down by one position FOR index ← logicalSize-1 TO targetIndex STEP -1 A[index+1] ← A[index] ENDFOR # add new item and increment logical size A[targetIndex] ← newItem logicalSize ← logicalSize + 1 ENDIF

Hwa Chong Institution H2 Computing 5 Removing an Item from an Array ● Shift items from next target index position to the logical end of the array up by one - To close hole left by removed item at target index ● Decrement logical size by one Example: Removal of an item at position 1 in an array of five items Here is the pseudo-code for the removal operation: # shift items up by one position FOR index ← targetIndex+1 TO logicalSize-1 A[index-1] ← A[index] ENDFOR # decrement logical size logicalSize ← logicalSize - 1 10.3 Linked Structure After arrays, linked structures are probably the most commonly used data structures in programs. Like an array, a linked structure is a concrete data type that is used to implement many types of collections, including lists. A linked structure decouples logical sequence of items in the structure from any ordering in memory, i.e. Noncontiguous/dynamic memory representation scheme. For your reference, though not in the syllabus, linked structures can be doubly linked, or circular linked.

Hwa Chong Institution H2 Computing 6 10.3.1 Node The basic unit of representation in a linked structure is a node. A singly linked node contains a data item and a link to the next node. You can set up nodes to use noncontiguous memory in several ways: ● Using pointers (a null or nil represents the empty link as a pointer value): Memory allocated from the object heap ● Using references to objects (e.g., Python) - In Python, None can mean an empty link - Automatic garbage collection frees programmer from managing the object heap ● Using two parallel arrays Defining a Node Class ● Node classes are fairly simple ● Flexibility and ease of use are critical ● Node instance variables are usually referenced without method calls, and constructors allow the user to set a node’s link(s) when the node is created A nod