Contents of Data Structures

Studying for my exam of Algorithms and Data Structures. This collection of flashcards it is focused on the data structure part, which means it will contain questions about definitions, problem solving, and other possible questions.

What Happens When an Array Gets Full?

When an array gets full, a new array with a larger size needs to be created, and all existing elements must be copied to this new array.

What is the Definition of an Array?

An array is a fixed collection of items that are RANDOMLY ACCESSIBLE by integers (numbers), which are the index.

What is the Definition of an ArrayList?

An array list is a collection of ordered data whose size may change (a dynamic array). Items are not only added or removed, but the memory used changes, too.

What is the Definition of a LinkedList?

A linked list is a linear data structure where elements are not stored in adjacent memory locations. This happens because instead of storing single elements, the linked list stores nodes (the data and a pointer/reference to the next element).

What is the Definition of Memory Overhead? 

Memory overhead is the extra memory a data structure spends beyond the data itself. 

What is the Definition of a DoubleLinkedList?

A double linked list is a variant of a linked list in which each element has a link/reference to both, the previous and next element.

What is the Definition of a XOR DoubleLinkedList?

A XOR double linked list is a specialized double linked list where each node stores the bitwise XOR of the address of its previous and next nodes, instead of storing two separate.

What is the Time Complexity (Big O Notation) for Accessing a Element in a LinkedList? And Why?

ACCESSING a node inside of a linked list is O(n), because instead of having indexes for each element, each element contains the reference to the next element.

What is the Time Complexity (Big O notation) for Inserting a Element in a LinkedList? And Why?

INSERTING a node/element in a linked list is O(1), but only if/ because you already have the references for doing this operation.

** if you do not have the references, then it is O(n), because of the searching part without indexes**

What is the Time Complexity (Big O Notation) for Deleting a Element in a LinkedList? And Why?

DELETING a node/element in a linked list is O(1), but only if/ because you already have the right references for doing this operation. (the pointers will be adjusted)

** if you do not have the references, then it is O(n), because of the searching part without indexes**

What is the Time Complexity (Big O notation) for Updating a Element in a LinkedList? And Why?

UPDATING an element in a linked list can be O(1) or/and O(n).

• O(1): if you already have the references, or if it is to update the head or the tail of the linked list (first and last element).

• O(n): if you have to search for the reference/index, or if you need to find it by the previous value.

What is the Time Complexity (Big O Notation) for Accessing a Element in an Array or ArrayList? And Why?

ACCESSING an element inside of an array is O(1), that happens because each element has its own index.

What is the Time Complexity (Big O notation) for Deleting a Element in an ArrayList? And Why?

DELETING an element from the array list is O(n), because you need to recalculate the array's size to maintain its previous structure. UNLESS, you are deleting it from the VERY END of an array list, then it is O(1).

What is the Time Complexity (Big O notation) for Inserting a Element in an ArrayList? And Why?

INSERTING an element beyond the array's size, it is O(n), because you need to deal with the "array is full problem" — that means that a new array must be created and inside of it, a copy from all the existing elements.

What is the Time Complexity (Big O notation) for Updating a Element in an Array or ArrayList? And Why?

UPDATING an element inside an array is O(1) because you already have the index for this specific position.

Which situations an ArrayList is a better choice than a LinkedList?

• Situations with frequent random access, because the array list access is based by index (O(1)) and with a linked list accessing it by index is O(n), because you must walk from the head, UNLESS you already hold the reference (it becomes O(1)).

• In memory-sensitive applications, the array list is better, because it stores the elements side by side and needs no extra memory per element. With a linked list, more memory is necessary because each node contains the data AND a reference for the next element, so the memory overhead is higher.

Which situations an LinkedList is a better choice than a ArrayList?

• A linked list is better when insertions and deletions dominate, especially at the beginning or at a known position: they are O(1) because only references are reconnected, with no shifting. It also handles unknown or highly variable sizes without copying, and it needs no adjacent block of memory.

• A linked list is the best choice for Queue and Deck behavior because both ends of the structure are used. With a head and tail reference, enqueue and dequeue are both O(1), with no shifting. In an array list, removing from the front is O(n), because every remaining element must shift left. THE MAIN REASON IS THE TAIL REFERENCE. 

**IT CAN BE GOOD FOR EXTRA POINTS: an array can serve as a queue in O(1) but only if it is implemented as a circular buffer, with two indices (head and tail) that wrap around, instead of shifting elements. It is what Java does with/in ArrayDeque**

Why the Memory Overhead is Higher in LinkedList?

Memory overhead is high in linked list because every node must ALSO store a reference to the next node.

Why the Memory Overhead is Lower in ArrayList?

Memory overhead is low in array list because the elements are stored side by side and nothing else is needed besides some unused capacity.

What are the FOUR Operations on an Array? (name, what it does and time complexity for each)

1. create — it is the operation to insert a new element inside of an array, described as one O(n) operation because it may require growing the array and shifting the following elements.

int [ ] array = new int [5];

2. write / set — it is the operations that overwrites the value stored at the given index, described as O(1) because the address is computer directly as base + index x elementSize, with no search and no traversal.

array [0] = 10;
array [1] = 20;
array [2] = 30;

3. read / get — it is the operation that returns the value stored at a given index, described as O(1) because the address is computed directly with the same formula, so the element is reached instantly instead of being walked to.

int x = array [2];

4. dispose / destroy — it is the operation that releases the array's memory, described as O(1) because Java has no explicit free: you set the reference to null and the garbage collector reclaims the whole block at once (rather than freeing cell by cell).

array = null;

What are the TWELVE Operations on an ArrayList? (name, what it does and time complexity for each)

1. create (new) — it is the operation that creates an empty dynamic array, described as O(1) because no memory is reserved at that moment. Java only allocates the internal backing array when the first element is added.

ArrayList<Integer> list = new ArrayList<>();

2. write / set (add (e) or add (i, e) — add (e) it is the operation that appends a new element at the end, described as O(1) because the element is written directly after the last one, with no shifting. And the other, add (i, e) is the operation that inserts a new element at a given position, described as O(n) because every element after the position will be shifted.

list.add (30); // add (e) at the end
list.add (3,20) // add (i, e) position and the element

3. read / get (get(i)) — is the operation that returns the element at the given index, described as O(1) because the backing array is adjacent, so the address is computed as the same array formula.

int x = list.get(0);

4. delete / remove (remove(i)) — is the operation that deletes the element at the given position, described as O(n) because every element after that position must be shifted one place to the left to close the gap.

list.remove(3);

5. clear (clear) — is the operation that removes every element, described as O(n) because each element reference is set to null, so the garbage collector can collect those objects.

list.clear();

6. size (size) — is the operation that returns how many elements the list holds, described as O(1) because the count is stored in an internal field and simply read.

int size = list.size();

7. isEmpty (isEmpty) — is the operation that returns true if the list holds no elements, described as O(1) because it only compares the stored size field to zero.

boolean empty = list.isEmpty();

8. extend (ensureCapacity(n)) — is the operation that reserves room for more elements, described as O(n) when it actually grow, since a new array is allocated and every element is copied, BUT O(1) when the current capacity is already large enough because nothing is reallocated.

list.ensureCapacity(100);

8. shrink (trimToSize(n)) — is the operation that cuts the unused capacity, described as O(n) because it allocates a smaller array and copies every element element to it.

list.trimToSize();

---

9. contains (contains(x)) — is the operation that checks if a given value exists, described as O(n) because it is a linear search.

list.contains(25);

10. sort (sort(list)) — is the operation that orders the elements, described as O(n log n) because Java's Collections.sort uses TimSort, which is an optimised merge sort that exploits already-ordered runs in the data.

Collections.sort(list);

11. forEach (forEach()) — is the operation that visits every element and applies an action as O(n) because each element is visited exactly once (it is an iterator pattern, so it reads sequentially).

for (int v : list) { } // going through the list
list.forEach(v -> System.out.println(v)); // forEach

12. map + filter (map().filter()) — they are operations that transform every element (map) and keep only those that satisfy a condition (filter), both of them described as O(n) because they make a single pass over the data (but they also allocate a new list, so extra memory O(n)).

list.stream().map(v -> v * 2).filter(v -> c > 20).toList();

What are the EIGHT Operations on a LinkedList? (name, what it does and time complexity for each)

1. create (new) — it is the operation that creates a new element, described as O(1) because a node is just an object allocated in memory with a data field and a next reference (there is no contiguous block and no size to reserve)

LinkedList<Integer> list = new LinkedList<>(); // empty list
Node newNode = new Node(30); // one node

2. write / set (at the end without tail reference) — it is the operation that inserts a new element after the last node, described as O(n) because you must find the last element by walking the whole chain, and only then set its next reference to the new node.

Node current = head;
while (current.next != null) current = current.next;
current.next = new Node (30);

3. write / set (at the end with tail reference) — it is the operation that inserts a new element after the last node, described as O(1) because the last node is already known, so no walking is needed.

tail.next = new Node (30);
tail = tail.next;

4. write / set (at the beginning) — it is the operation that places a new element before the current head, described as O(1) because only two references are rewired.

newNode.next = head;
head = newNode // or list.addFirst(e)

5. read / get (by index) — it is the operation that returns the element at the given position, described as O(n) because there is no index to compute. To use the index, you must iterate from the head, counting nodes until the counter reaches the wanted index.

Node current = head;
for (int i = 0; i < index; i++) current = current.next;
return current.data;   // or list.get(2);

6. delete / remove (node, i, v) — it is the operation that removes an element, if you have the references of the node is described as O(1); if you are passing an index or value is O(n); and if you are deleting the head is O(1).

prev.next = current.next; // already has the references
list.remove(1); // by index
list.remove(Integer.valueOf(30)); // by value

7. clear — it is the operation that removes every element, described as O(1) in Java, because setting head = null and size = 0, makes the whole chain unreachable at once, letting the garbage collector reclaim every node.

head = null;
tail = null;
size = 0; // or list.clear();

8. size / length — it is the operation that returns how many elements the list holds, described as O(1) in Java, because the count is kept in an internal field and simply read.

int size = list.size():

9. isEmpty — it is the operation that returns true if the list holds no elements, described as O(1), because it only checks whether head == null or whether the stored size is zero.

boolean empty = list.isEmpty():

What are the Differences Between a DoubleLinkedList and a LinkedList?

1. two references per node — instead of one reference (to the next node), the double linked list also allows each node to store the reference for the previous node.

2. traversal — double linked list goes in both directions in O(n) while the ‘normal’ linked list goes only forwards.

3. delete a known node — O(1) in double linked list, because the predecessor is already inside the node.

4. insert before a known node — O(1) in double linked list, because the predecessor is already inside the node.

5. delete at the tail — O(1) in double.

6. memory — double linked list has higher overhead because of the extra reference per note, it is about 8 bytes on a 64-bit machine (which doubles the per-element overhead).

What a Bitwise XOR Stands for?

A bitwise XOR is a binary operation that takes two bit patterns and performs the logical exclusive or operation on each pair of corresponding bits.

The possible results are:

• 1 — if ONLY one of the bits is 1.

• 0 — if BOTH have/are the same value.

XOR operation:

0101 (decimal 5)

0011 (decimal 3)

results in 0110 (decimal 6)

What are the names of the Operations on an XOR DoubleLinkedList? (name and time complexity for each)

1. create a node — described as O(1) because is a single allocation followed by two writes: the data and the xor field.

2. storing an element — described as O(1) because it is a single XOR of the previous and the next reference in onde field.

3. getting the next or previous element — described as O(1) because it XORs the stored field together: next = xor ^ prev or prev = xor ^ next.

4. traverse the whole list — described as O(n) because it performs n steps of O(1), and it must carry the previous address in a helper variable: without it, the XOR cannot be decoded and the chain is lost.

5. insert at head — described as O(1) because only the xor fields of the new node and the old head are recomputed.

6. insert after a known node — described as O(1) because you have both the node and its successor.

7. insert at tail — described as O(1) when a tail pointer is stored because the last node is already known.

8. delete at head — described as O(1) because it only moves the head to the next node and updates one xor field.

9. delete a known node — described as O(n) and this is the honest weakness of the XOR list: knowing only the node, you can extract neither prev nor next, so you must traverse to recover one of them before you can rewire.

10. delete tail — described as O(n) because you must reach the second-to-last node to rewire its reference.

What is the Definition of a Set?

A set is a data structure that can store distinct values, without any particular order. It only stores unique values, has dynamic size, is implement using linked lists, hash tables or arrays.

What is the Definition of a Key-Value Pair Data Structure?

A Key-Value Pair is a data structure that stores elements as key / value pairs, where each value is accessed through an alphanumeric key instead of a numerical index.

What is the Definition of a SortedMap ?

A SortedMap is a table structure that keeps its keys sorted at all times, implemented on a dynamic array, so that reading a key is a binary search — O(log n) — because the ordering allows the search space to be halved at every step.

What is the Definition of a HashMap ?

A HashMap is a table structure that uses a hash function to compute each key's position directly, so reading a key is O(1) on average because no search is performed at all — the position is calculated, not found.