Data Structures Flashcards
What is UTF-8
Encoding standard, same as ASCII for Latin letters. Every code point from 0-127 is stored in a single byte (8 bits). Code points > 128 is stored in 2 - 6 bytes.
Character encoding. What happens when you type keys on a keyboard?
Provides a key to unlock code. It is a set of mappings between the bytes in the computer and the characters in a character set.
When you enter keys on a keyboard, the character encoding maps characters you choose to specific bytes in computer memory.
What are ASCII characters?
255 characters to be used that map back to 8 bit bytes.
Unicode
Comprehensive encoding that represents all possible characters
What is an array
A contiguous area of memory consisting of equal sized elements. You can store primitive types, objects, or references to other arrays.
What is the performance of adding and removing an element from the beginning, end, and middle of an array
Beginning: Add – O(n) / Delete O(n)
Middle: Add – O(n) / Delete O(n)
End: Add - O(1) / Delete O(1)
When should you use a linked list over an array
- You need insertions/deletions to be fast
* You insert or delete items in the middle of a list
When should you use arrays over linked lists
- You frequently need random, unordered access to the data
- You need fast performance to perform reads
- The number of items doesn’t change during execution so you can easily allocate contiguous memory.
What is the complexity of adding, deleting and searching for nodes in a Linked List
Add and Delete: 0(1)
Search: O(n)
How do you traverse a linked list
When starting at the head, you should make note of the current node and continue to loop through until reaching the tail. Progressing through the list involves setting the currentNode = nextNode
How would you reverse a singly Linked List
Starting at the head, I would keep track of the current, previous, and next nodes, resetting the current node’s next node = previous node, then continue to progress through the list by setting the current node to the next node.
