Data Structures*

• A data structure is a collection of related data items held in a computer's memory.
• An array is a collection of variables of the same data types grouped together under a single identifier.
• A record is a set of data items all related to a single entity.
• A 3D array is a collection of either 1D or 2D arrays.
• The dimension of a 3D array changes depending upon the index NOT the number of arrays.
• Stacks are Last-In, First-Out Data Structures. This means that the most recent piece of data placed onto the stack is the first piece to be taken off it.
• Adding data to a stack is called pushing and removing data is called popping.
• To implement a stack, we can use an array to store the data and a variable to point to the top of the stack.
• Queues are First-In, First-Out data structures. This means that the most recent piece of data to be placed within the queue will be last taken out.
• Queues are implemented using an array and two variables, one variable points to the first item in the queue and the other points to the free space.
• Binary tree is a data structure composed of nodes (leaves) and links between them (branches). Each node has up to 2 others coming off it.
• Binary trees are used to implement another data structure called a binary search tree. They are identical to to a binary tree, however, on one condition, the node to the left of the branch must be less than the data in the right node.

  
• Pre-Order Traversal is a method of reading a binary search tree by reading from the start of the root, traverse the left sub tree and then right.

  A) 1

  B) 2

  C) 3

  D) 4

  E) 5

  F) 6

  G) 7

  
• In-Order Traversal is a method of reading a binary search tree by traversing the left sub tree then the root and then then the right sub tree.

  A) 1

  B) 2

  C) 3

  D) 4

  E) 5

  F) 6

  G) 7

  
• Post-Order Traversal is a method of reading a binary search tree by traversing the left sub tree then the right then the root.

  A) 1

  B) 2

  C) 3

  D) 4

  E) 5

  F) 6

  G) 7

  
• Using an array or linked list can implement a binary tree. You would have to index the root as 0 and use the formulae to index the left and right nodes: Left = 2n+1 Right = 2n + 2
• To remove data from a binary tree from a leaf with 0 branches, you just delete the node and set the point which was referencing the node to null.
• To remove data from a binary tree from a leaf with 1 branch, you must update the pointer of the parent to point to the address of the child of the node to be deleted. Then delete the data.
• To remove data from a binary tree with a leaf with 2 branches, you must first use an in-order traversal to identify the smallest node beneath the one to be deleted. This is known as the successor. All pointers related to the successor are updated to reflect the nodes to be deleted. The node is then removed.
• A linked list the most common data structure and it is dynamic. They are made up of nodes with each node linked the the next within the list. They use data and a pointer, which points to the next piece of data in the list.
• To add data to a linked list, you can adjust the current node that points to where you wish to place the new node and we tell the new node to point to the next in the list.

  
• To remove an item in a linked list, you adjust the node before the one to be deleted and update the pointer to point at the next item in the list after the node is removed.
• Hash tables have two components: a table and a mapping function, also called a hash function or hash algorithm, which the decides the location for the data in the table.
• Hash function = Length of data / Table size (Remainder is used for index)
• The problem with the mapping function in a hash table is that if two new data items with each length appear they will collide for a location. To solve this, we use separate chaining, this means that if a piece of data such as jane is entered, it will also be stored at 4 but as a new node. This means that when searching the index 4, the linked list within will have to be searched also.

  
• Use for Pre-Order Traversal is to clone a tree.
• Use for In-Order Traversal is to search a tree in its correct order.
• Use for Post-Order Traversal is for stack-based programming.
• Stacks are Last-In, First-Out data structures. This means that the most recent piece of data placed onto the stack is the first piece to be taken off it.