Data Structures

Question 1

What is a data structure?

Answer 1

A data structure defines how data is organised. Consequently, they also influence how data is allocated in computer memory.

For the same amount of data, different data structures can take more or less space in computer memory.

They are implementations of ADTs (Abstract Data Types).

Question 2

What is an ADT (Abstract Data Type)?

Answer 2

An ADT is a conceptual collection of operations that can be performed on a data type, without specifying the implementation details.

They are the building blocks of a data structure. Consequently, data structures are often said to be the realisation or implementation of an abstract data type.

Question 3

What does it mean for a structure to be linear?

Answer 3

For a structure to be linear, it must have a unique first and last element, and for each element, its predecessor and successor are unique.

What this effectively means is that all of their elements are arranged in a sequential order, and each element can be accessed based on their position or index.

Otherwise, it is non-linear.

Question 4

Give an example of a linear and non-linear structure.

Answer 4

Linear:
Array
List
Linear Queue

Non-linear:
Trees
Graphs
Priority, Circular Queue

Question 5

Why is a priority queue not considered a linear data structure, even though data is stored sequentially?

Answer 5

Data is accessed and ordered based on their priorities, not by their position or index. Therefore, a priority queue is considered non-linear.

Question 6

What is the difference between direct and sequential access?

Answer 6

A direct access structure is one such that any element of the structure can be accessed directly.
e.g. An array, where you can access its elements using an offset value.

A sequential access structure is one such that we can only access the Nth element if we have accessed all elements < N.
e.g. A singly linked list, where you must traverse the list sequentially from its head to search for an element.

Question 7

What does it mean for a structure to be homogeneous, as opposed to being heterogeneous?

Answer 7

A homogeneous structure is one that can store a collection of multiple different data types, while a heterogeneous structure can only store data of one type.

Question 8

What is a list?

Answer 8

A list is a dynamic data structure in which data is accessed sequentially. It normally has two special named elements - the head and the tail, representing the first and last element of the list respectively.

By dynamic, we mean that the list does not have a fixed size like arrays.

Data is stored sequentially, making lists linear. They can also store any type of data, making them also homogeneous.

Lists are often the basis for the implementation of other sequential data structures, such as queues and stacks.

Question 9

What is an array?

Answer 9

An array is a fixed size data structure in which data is accessed directly using a memory offset.

For example, if array[0] points to 0x1, then array[10] will point to 0x11.

An array stores data in a linear fashion, and are therefore linear.

Question 10

What advantages do lists have over arrays?

Answer 10

A list accesses elements sequentially, meaning that it will take longer to find elements than in a directly-accessed array.

However, it is much easier to insert and delete nodes, as we do not have to shuffle the list backwards upon deletion like we have to do with arrays.

e.g. [0,1,2,3,4] = [0,1, , 3, 4] = [0, 1, 3, 4]
(3 and 4 had to recursively be shuffled back by 1 space. Lists do not encounter this issue)

Question 11

What is a linked list?

Answer 11

A linked list consists of a collection of records called nodes, each containing at least one member that gives the location of the next node.

In the simplest case - a singly linked list - it consists of a data member representing the value, and a link member representing the memory location of the successor of the node.

Because we have the link member, we can store nodes ANYWHERE IN MEMORY and not necessarily contiguously.

Question 12

What advantages and disadvantages do linked lists suffer from?

Answer 12

Linked lists provide a fair use of memory that is not only dynamic but efficient. Common operations, such as deletion and insertion, are incredibly cheap, as we simply need to modify link nodes.

However, they are extremely difficult to set up and traverse. For example, there is no way to speed up the process of searching, and will always, in worst case, traverse in O(n), regardless of algorithm.

Question 13

What is a circular linked list?

Answer 13

A circular linked list is a form of a singly linked list where the tail of the list is linked back to the head.

It can be useful for something like an enum that needs to cycle, or an implementation of the Josephus election.

Question 14

What is the difference between a singly linked list and a doubly linked list?

Answer 14

A singly linked list has one link, that points to the position in front of it.

A doubly linked list, on the other hand, has two links - both a “next” and a “previous” link.

This means that we can traverse the list both ways, instead of needing to go through the whole list every time we need a single element.

Question 15

What is a stack?

Answer 15

A stack is a restricted form of a list, ordered sequentially but with some set rules.

A stack implements a LIFO structure - Last In, First Out. This means that the last element to be put into the stack will be the first to be taken from it.

This way, one can refer only to the top of the stack, and elements further down in the stack can only be reached by removing elements from it until it is, in worst case, empty.

Using a stack has some qualities though - for example, storing traversed nodes in search problems, or reversing linear orders.

Stacks are also used in runtime memory management as a way of storing the function we’re currently processing.

Question 16

What is a queue?

Answer 16

A queue is, like a stack, a restricted form of a list, ordered sequentially but following the FIFO rule - First In, First Out.

This is basically the opposite of a stack, wherein the first element to be placed into the queue will be the first out.

Queues are sometimes used for obvious reasons, such as job scheduling or printer spool, however they can also be used for things such as storing traversed nodes in some search problems.

Question 17

What is the difference between a stack and a queue?

Answer 17

A stack implements the LIFO rule - where the last element into the stack is the first out, as if you were stacking pizzas or pancakes.

A queue, however, implements FIFO - where the first into the stack is the first out, as if you were in line at the store.

Question 18

What is a priority queue?

Answer 18

A priority queue is a type of queue such that instead of our elements being stored strictly linearly, we give each element a priority.

That priority then determines which will be the first out, rather than their chronological/sequential order.

While a queue is a linear structure, priority queues are actually non-linear because of this.

Question 19

What is a heap?

Answer 19

A heap is a complete binary tree containing labelled nodes, such that no child has a value bigger than the value of its parent.

A binary tree represented in this way eases the job of implementing the operation to find the maximum element, as it is always the root of the tree.

A great benefit of heaps are that, because they are binary trees, they can be represented as an array, making them easy to mathematically traverse (e.g. max = heap[0], parent = heap[i / 2]).

Question 20

What are the operations Sink and Swim?

Answer 20

Sink and Swim are operations on a heap.

Sink is a method to remove something from the heap. It is called as such because our algorithm swaps elements starting from the top. We do this by replacing it with the rightmost element at the lowest level, and swapping it with the largest element until it cannot swap anymore.

Swim is a method to insert something into the heap. It inserts the element as the rightmost point at the lowest level, and systematically swaps the element with the root recursively until we cannot swap anymore.