Data Structures Part 2 Flashcards
Array
An ordered group of items, each of the same data type. The number of items is fixed in size. Each item is identified by a subscript.
Use Record When
The data is all about one object e.g. a person, a holiday.
The data is of different data types
Use array when
The data is about a number of different items.
The data is all of the same data type.
Record
A data structure that holds a number of related data values (possibly of different data types) , normally about the object.
Linear (sequential) search
A search where each record is examined in turn until required records is found or the end of the list is reached.
Binary search
A search on an ordered list where the middle item is inspected, if it is not the correct item, decide which half of the list contains the required value. Search that half of the list. Repeat the process.
half the list is discarded. This process is repeated.
Swapping
The process of exchanging the contents of two storage locations.
Bubble Sort
Work through the list examining pairs of records.
If a pair is in the wrong order then swap them.
keep passing through the list until no swaps are made.
Insertion Sort
Loop for each element in the unsorted part of the list.
Search through the list finding the position of the highest element.
Swap the highest element with the element at the top of the unsorted part of the 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 it’s correct position.
Sort the two separate lists.
Quick Sort - Advantage
It is fastest/most efficient type of sort algorithm. It uses recursion
Sort choice depends on
The number of elements in the list. The amount of disorder in the list. If the data structure is sorted. The amount of temporary storage available Computer /processor speed Data type.
Pointer
A reference to a storage location, an address.
Class
A class consists of a description of all of the data in a record together with the operations that can be applied to it.
Data structure
It’s an organised group of related data items.
Static Data Structure
A data structure that is fixed in size, such as an array.
A dynamic data structure
It’s one that can grow as data is added and shrink when data is removed.
Stack
The stack is 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. E.g. Undo function
Pull
Removing an item from a stack.
Pushing
Adding an item to a stack
Stack Errors
Trying to remove (pull) from an empty stack.
Stack Usages
- Implement an undo function.
- Implement a back function.
Quueue
A queue is a dynamic data structure operating on the principle of First In First Out. When an item is removed it is always the item which has been in the queue the longest.
Queue Errors
Trying to remove an item from an empty queue.
Queue Usages
- Print queue (spooling)
- Keyboard buffer
- Audio/video streaming buffering.
Linked List
A Linked List is a dynamic data structure operating on the principle of each item being linked to the next by a pointer. It is more versatile than a stack or a queue since data may be added or removed in any order.
Linked List Errors
Searching for an item that is not present.
Linked List Usage
List joining blocks of a file on a disc.
Double linked List
It has a link going to previous record as well as the next record. The list may then be searched in either direction.
Circular linked list
It has the last element linked back to the first.
Binary Tree
A tree is a 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 layers below.
Root
A very top of a tree.
Branch
A path joining parts of a tree.
Terminal Node
A final node which has no branches beneath it.
Subtree
From any node the branches beneath it form trees.
Parent
A node immediately above a given node.
Child
Nodes connected to and immediately below a given node.
Level
All nodes, the same number of branches away from the root node, have the same level.
Tree errors
Deleting or searching something that doesn’t exist. - Node not found.
Tree Usage
- Hierarchical file structure.
- Domain name structure.
Binary Sort Tree
A binary tree where all the values in the left subtree of any node are smaller than the values in the node AND all the values in the right subtree of any node are larger than the value in the node.
Traverse
The process of visiting in turn each element in a data structure.
