C949v4 Study Guide | Determines Data Structure Impact

Implementation of Data Structures Array (Chapter 1.1, 1.4, 1.5) Linked list (doubly & singly linked) (Chapter 2) Stack operations (Chapter 3) Queue operations (push, pop, peek, enqueue, dequeue) (Chapter 3) Deque operations (Chapter 3) Hash table (Chapter 4) Trees (leaf nodes, root, height) (Chapter 4) Heaps (Chapter 7) Sets (including intersection) (Chapter 8) Graph (vertices, adjacency) (Chapter 9)

Array

Description: A data structure that stores a fixed-size sequence of elements of the same type in contiguous memory locations.

Comparison: Elements are compared by their index.

Insertion: Elements can be inserted at the end in O(1) time. Inserting at the beginning or middle takes O(n) time.

Deletion: Elements can be deleted in O(1) time from the end of the array. Deleting from the beginning or middle takes O(n) time.

Indexing: Elements are accessed using their index.

Hierarchy: have a flat structure.

Linked List

Description: A data structure that consists of a sequence of nodes, each containing an element and a reference to the next node.

Comparison: Elements are compared by their value.

Insertion: Elements can be inserted at the beginning or end of the linked list in O(1) time. Inserting in the middle takes O(n) time.

Deletion: Elements can be deleted in O(1) time if the node to be deleted is known. Deleting a node requires traversing in O(n) time to find the node to be deleted.

Indexing: Elements are accessed by traversing from the beginning or end.

Hierarchy: have a flat structure.

Stack

Description: A data structure that follows the Last-In-First-Out (LIFO) principle.

Comparison: Elements are compared by their value.

Insertion: Elements are inserted at the top in O(1) time.

Deletion: Elements are deleted from the top in O(1) time.

Indexing: Elements are not accessed by index

Hierarchy: have a flat structure.

pop()

operation removes and returns the item at the top of the stack

push()

inserts an item on the top of the stack

peek()

returns but does not remove item at top of stack

enqueue()

Adds an element to the back of the queue.

dequeue()

Removes the front element from the queue and returns it.

Queue

Description: A data structure that follows the First-In-First-Out (FIFO) principle.

Comparison: Elements are compared by their value.

Insertion: Elements are inserted at the back in O(1) time.

Deletion: Elements are deleted from the front in O(1) time.

Indexing: Elements are not accessed by index

Hierarchy: have a flat structure.

Hash Table

a data structure that stores unordered items by mapping each item to a location in an array or vector

Hash function

computes a bucket index from the item’s key

Chaining

handles hash table collisions by using a list for each bucket, where each list may store multiple items that map to the same bucket

key

the value used to map to an index in a hash table

Modulo Operator

computes the integer remainder when dividing two numbers and is a common hash function

Binary Tree

a data structure in which each node stores data and has up to two children, known as a left and right child

Heap sort

sorting algorithm that takes advantage of a max-heap’s properties by repeatedly removing the max and building a sorted array in reverse order

Set

an ADT for a collection of distinct items

Graph

Description: A collection of nodes (vertices) connected by edges.

Comparison: Nodes are compared by their value.

Insertion: Nodes and edges are inserted by adding them to the graph as new vertices or edges, respectively.

Deletion: Nodes and edges are deleted by removing them from the graph along with any connections to other vertices or edges.

Indexing: Nodes are not accessed by index in a graph.

Hierarchy: Graphs have a hierarchical structure.

Dictionary

Description: A collection of key-value pairs where each key maps to a value.

Get: Returns the value associated with a specified key.

Set: Sets the value associated with a specified key.

Delete: Removes a key-value pair from the dictionary.

List

an ADT for holding ordered data

heaplist

A binary heap can be represented as a list, where the root node is at index 1 and the children of a node at index i are at indices 2i and 2i+1.

child and parent

Each node has at most two children and one parent. The parent of a node can be found by taking the floor of the node index divided by 2.

min-heap

A binary heap where the value of each parent node is less than or equal to its children.

max-heap

A binary heap where the value of each parent node is greater than or equal to its children.

weight and direction

Edges can have weights to represent the strength or cost of the connection between two vertices. Edges can also be directed, meaning they have a specific start and end point, or undirected, meaning they have no specific start or end point.

vertices/nodes/edges

The nodes in a graph are also called vertices, and the edges are the connections between them. Edges are often represented as pairs of nodes, such as (u, v) to indicate an edge between vertices u and v.

directed graph

Edges have a direction and can only be traversed in one direction.

undirected grap

Edges have no direction and can be traversed in either direction.

tree traversal

The process of visiting each node in a tree in a specific order.

inorder traversal

Visits the left subtree, then the current node, and finally the right subtree.

preorder traversal

Visits the current node, then the left subtree, and finally the right subtree.

postorder traversal

Visits the left subtree, then the right subtree, and finally the current node.

Doubly Linked List

Description: A data structure that consists of a sequence of nodes, each containing an element and references to the previous and next nodes.

Comparison: Elements are compared by their value.

Insertion: Elements can be inserted at the beginning or end of the doubly linked list in O(1) time. Inserting in the middle of the list takes O(n) time.

Deletion: Elements can be deleted in O(1) time if the node to be deleted is known. Deleting a node requires traversing the list in O(n) time to find the node to be deleted.

Indexing: Elements are accessed by traversing the list from the beginning or end.

Hierarchy: have a flat structure.

collision

when an item being inserted into a hash table maps to the same bucket as an existing item in a hash table

full

if every node on a binary tree contains 0 or 2 children

complete

complete on all levels of the binary tree except possible the last level, contain all possible nodes and all nodes in the last level are a as far left as possible

perfect

if all internal nodes on the binary tree have 2 children and all leaf nodes are at the same level

bag

an ADT for storing items in which the order does not matter and duplicate items are allowed