Data Structures Flashcards by James Finch

Describe the format of Linked List data structure (3)

Linear data structure
Data is not stored in contiguous memory
Comprised of nodes which have a variable for the data to be stored and a pointer to the next node in the list.

How well did you know this?

Not at all

Perfectly

Advantages of Linked List (3)

Dynamic size
Memory is not wasted
Effective insertion and deletion as data doesn’t have to move like in arrays

How well did you know this?

Not at all

Perfectly

Disadvantage of Linked List (3)

Using more memory per node due to having to maintain the pointer
O(n) access due to having to traverse list from head
Cache inefficient as memory is not stored in contiguous memory

How well did you know this?

Not at all

Perfectly

Complexity of insert/delete at beginning of Linked List

O(1)

How well did you know this?

Not at all

Perfectly

Complexity of insert/delete at end of Linked List

O(n)

How well did you know this?

Not at all

Perfectly

Complexity of insert/delete at given point in Linked List

O(n)

How well did you know this?

Not at all

Perfectly

Complexity of searching/accessing Linked List by index

O(n)

How well did you know this?

Not at all

Perfectly

Describe the format of a Stack data structure (4)

Linear data structure
Follows Last in First Out, access via the top of the stack
Can be fixed size or dynamic
Can be implemented with both Arrays or Linked List

How well did you know this?

Not at all

Perfectly

Advantages of Stack data structure (4)

Simplicity
Efficiency: O(1) operations
LIFO
Limited memory usage

How well did you know this?

Not at all

Perfectly

Disadvantages of Stack data structure (2)

Limited access: O(n)
Possibility of overflow if fixed size

How well did you know this?

Not at all

Perfectly

Common Stack operations (5)

Push
Pop
Peek
Size
isEmpty

How well did you know this?

Not at all

Perfectly

Complexity of insert in Stack

O(1)

How well did you know this?

Not at all

Perfectly

Complexity of removal in Stack

O(1)

How well did you know this?

Not at all

Perfectly

Describe the structure of Queue data structure (4)

Linear data structure
Follows First in First Out
Can be fixed size or dynamic
Can be implemented with both Arrays or Linked List

How well did you know this?

Not at all

Perfectly

Common Queue operations (5)

Enqueue O(1)
Dequeue O(1)
Peek
Size
IsEmpty

How well did you know this?

Not at all

Perfectly

What is a Binary Search Tree?

A tree data structure where each node has two children and they fit a specific ordering such as:
All left children < n < all right children

How well did you know this?

Not at all

Perfectly

What are the advantages of BST? (5)

Efficient searching: O(log n) time complexity
Ordered structure: Elements are stored in sorted order, making it easy to find the next or previous element
Dynamic insertion and deletion: Elements can be added or removed efficiently
Balanced structure: Can be balanced to maintain logarithmic height, ensuring efficient operations
Space efficiency

How well did you know this?

Not at all

Perfectly

What are the disadvantages of BST? (5)

Not self-balancing: Unbalanced BSTs can lead to poor performance
Worst-case time complexity: In the worst case, BSTs can have a linear time complexity for searching and insertion
Memory overhead: Pointers
BSTs can become inefficient for very large datasets
Limited functionality: BSTs only support searching, insertion, and deletion operations

How well did you know this?

Not at all

Perfectly

What are the common operations for BST and their time complexities? (3)

Insert: O(log(N))
Delete: O(log(N))
Search: O(log(N))

What are some applications of a BST? (5)

Searching: Finding a specific element in a sorted collection
Sorting: Sorting a collection of elements in ascending or descending order
Range queries: Finding elements within a specified range
Data storage: Storing and retrieving data in a hierarchical manner
Databases: Indexing data for efficient retrieval

What is a balanced tree?

Tree where the left and right sub trees are some what similar so that operations are O(log(n))

What is a complete binary tree?

A complete binary tree is a binary tree in which every level of the tree is fully filled, except for perhaps the last level. To the extent that the last level is filled, it is filled left to right.

What is a full binary tree?

A full binary tree is a binary tree in which every node has either zero or two children.That is, no nodes have only one child.

What is a perfect binary tree?

Binary tree which is both full and complete

What is in-order traversal of a binary tree?

Left branch, current node, right branch. For a binary search tree, this would traverse in ascending order.

What is pre-order traversal of a binary tree?

This visits the current node, before visiting its children. Root is always visited first

What is post-order traversal of a binary tree?

This visits its children before, visiting the current node. Root is always visited last.

How do you remove element from BST, what is the time complexity?

Replace the node to be removed with its in order successor. Finding successor is O(log(n)) time complexity

What is a Heap data structure?

A Heap is a complete binary tree data structure that satisfies the heap property: for every node, the value of its children is less than or equal to its own value. Meaning the root will either hold the max or min value of data structure.

How is a heap normally implemented? How do you get the children of an element?

With and array, where the left and right children are given by (2*index) + 1 and (2*index) + 2

What are the advantages of Heap data structure? (5)

- Efficient insert and delete operations - Efficient priority queue implementation - O(1) access to Max or Min - Less memory as Binary Tree is complete - Heapsort implementation

What are the disadvantages of Heap data structure? (5)

- Flexibility - Bad for searching - Not stable data structure - Memory management - Complexity

What are the common operations for Heap? (4)

- Insert O(log(N)) - Delete O(log(N)) - Min/Max O(1) - Heapify O(n)

What are applications of Heaps? (5)

- Priority Queues - Heapsort Algo - Memory management, memory blocks stored in Heap and used to efficient allocate it to programs - Graph algorithms Dijkstra's and Kruskal's - Job scheduling based on priority

What is the algorithm for inserting an element into a Heap?

- Insert at the end of the heap array and work up its parent nodes swap if it is larger. O(log(N))

What is the algorithm for deleting the root node in Heap?

- Remove the root node and replace with last element in Heap. Swap element with its largest child and move down the branch till Heap ordering is restored. O(log(N))

What is a Graph data structure?

A graph is simply a collection of nodes with some edges between the nodes.

What is a directed Graph?

A directed graph allows travel down its edges in one direction only.

What is a connected Graph?

Where every pair of nodes has an edge between them.

What is an acyclic Graph?

Graph without cycle in it.

What are the ways to represent a graph? (2)

- Adjacency List: Each node has a list of its adjacent nodes - Adjacency Matrix: True value in matrix[i][j] means there is a path between node i and j. This implementation can be less efficient.

What is depth first search in terms of a Graph data structure? What is breadth first search?

- Depth: Starting at the root or some other node and exploring each branch first before moving onto the next branch. - Breadth: Explore each neighbour first before moving a level down

When is DFS used for a Graph?

When you want to visit every node, it is simpler

When is BFS used for a Graph?

Normally when you want to find the shortest path between two nodes

What is Bi-directional search for a Graph? When is it used?

It is used to find the shortest path between two nodes and is a breadth search starting from each node. When these collide you have found the shortest path.