Data Structures 2

Data Structures 2

1. Arrays = An organised group of items, each of the same data type. The number of items is fixed in size.

   • Array Processing = Loops are used to process the data stored in arrays.
   • Array Searching
     • Linear = Used when data is not sorted. Starts at one end of the array. Each element is examined in turn until the correct element is located or the end of the array is reached.
     • Binary = This can only be applied to an array where the data is in order. Examines element in middle, halves data continuously until correct information is found.

2. Recursion = When a method calls itself.

3. Array Sorting

   • Bubble sort = work through list examining pairs of records. If a pair is in wrong order, records are swapped. Keeps passing through list until no swaps are made.
   • Insertion sort = Loop for each element in the unsorted part of the list. Search through list finding the position of the highest element. Swap highest element with the element at the top of the unsorted list. The top element is in the correct position so is now part of the sorted list. Repeat until each item has been put in place.
   • Quick Sort = Select the first element. Partition the list so that those items less than the first item come after it and those items greater than the first item come before it. The first item is then in its correct position. Sort the two separate lists.

4. Pointers and Objects

   • Pointer = A reference to a potential area of storage.
   • Memory Leakage = When storage is no longer referenced, the system may lose storage space.

5. Classes

   • Class consist of a description of all the data in a record together with the operations that can be applied to it (known as methods).

6. Data Structures

   • A data structure is a group of related items.
   • Dynamic Data Structure is one that can grow as data is added and shrink when data is removed.
     • Implementation occurs when a class is created which has at least two fields. One field holds data the other is a reference to another similar object.
       • When a programing language does not have pointer data structures implementation occurs using an array. This can take up a lot of memory.
     • Stack = A dynamic data structure operating on the principle of Last In, First Out. When an item is removed, it is always the most recently added item.
       • Operations = initialise, push(to add to the stack) and pull (to remove from the stack).
       • Errors = Attempting to remove data from an empty stack.
       • Stack usage = Starting operations for an undo function, in a browser storing the previously visited webpages.
       • Implementation = Either directly or using an array.
         • Using Pointers: A class called stackNode is defined. An object of this class has two fields one called element which stores data, the other called Next which is a reference to the next stackNode.
     • Queue = A dynamic data structure operating on the principle of First In first Out. When an item is removed, it is always the item that has been in the queue the longest
       • Queue Errors = Attempting to remove from an empty queue.
       • Usage = For printers or for the processor to process tasks.
     • Linked List Array Implementation: An array of records can be set up. Each record has at least 2 fields: one to hold data and another to to indicate the position of the next record in the list. An integer called start used to indicate first record and free to indicate a free position.
     • Tree = Dynamic data structure organised as a series of layers. Each data item (node) is linked to exactly one element in the layer above and any number below.
       • Operations = initialise, add to the tree, access the tree (traversals), search the tree and remove from the tree.
       • Tree Errors = removing from an empty tree, searching for items that do not exist.
       • Tree Usage = Directory structure.
       • Binary sort tree = When data is added to the first free node encountered. A decision as to whether to use the left or right sub tree is made according to the value of the key field.
         • Tree traversal = A method of going around a tree visiting each node. The BST does not at first sight have any obvious methods of extracting the data in order.