Data Structures & Collections

Question 1

What are the different types of data structures?

Answer 1

Linear
-Arrays
-Linked-Lists
-Stack
-Queue
Hierarchal
-Trees
-Graph
-Heaps

Question 2

What are Data Structures?

Answer 2

A data organization, management, and storage format that enables efficient access and modification through convenient operations.

Question 3

What are basic data structure operations?

Answer 3

Inserting, Deleting, Searching, Iterating, Sorting, Merging

Question 4

What is an Array?

Answer 4

Basic Data Structure, often used in the implementation of other data structures

Question 5

What is a Linked Lists?

Answer 5

A sequence of data structures are called nodes in which one nodes reference points to the next. The first node is called the head, the last is called the tail.

Question 6

What are the different types of Linked Lists?

Answer 6

• Simple Linked List - Each node only has one reference to the next ( Goes from head to tail ) the tail points to null.
• Doubly Linked List - Each node has a reference forward to the nest node and backwards to the previous node (except the head and tail) the head and tail points to null.
• Circular Linked List - The tail has reference to the head node.

Question 7

Linked List vs. Arrays

Answer 7

Linked List are better at insertion and deletion than arrays.

One disadvantage of a linked list against an array is that it does not allow direct access to the individual elements. If you want to access a particular item then you have to start at the head and follow the references until you get to that item.

Another disadvantage is that a linked list uses more memory compared with an array - we extra 4 bytes (on 32-bit CPU) to store a reference to the next node.

Question 8

What is a Stack?

Answer 8

A Linear data structure and a type of list that operations to the element follows LIFO (Last In First Out) aka operations only occur on the top element.

Like a stack of plates.
Removing the top element is called popping.

To obtain the value at the top but not removing it is called peaking.

Placing an object on the top is called pushing.

Question 9

What is a Queue?

Answer 9

An interface within the Collections API that it’s implementations are much like lines for a rollercoaster or lines at the grocery store, operates under FIFO(First In First Out). Both ends are open for operations.
Adding elements is enqueuing (only to the backend)
Removing elements is dequeuing(only to the front end).

Question 10

What is a Deque?

Answer 10

A interface apart of the Collections API that extends from Queue and is a double ended Queue that can add and remove from both ends, FIFO and LIFO

Question 11

What is a Tree?

Answer 11

A very common heirarchical data structure, Much like an OS file system structure or an In memory representation of an HTML document. Each element is represented by a node.
Root node is the first node
Parent nodes have references to child nodes.
Sibling nodes have the same parent
Leaf nodes are nodes that have no child
A branch is a complete line (path) from the leaf to the root

Question 12

collections vs Collection vs Collections

Answer 12

collection - a collection of entities, or an aggregate Data Structure i.e. Arrays and Maps

Collection - Interface within the Collections API

Collections - Utility Class that has static, convenient methods that operate on Data Structures in the Collections API or return them.

Question 13

Collections API

Answer 13

Starts from the Iterable Class
then Colllections class inherits the Iterable class.
Under the Collections class you have these interfaces
-List
    1.) ArrayList
    2.) LinkedList
    3.) Stack
    4.) Vector
-Set
    1.)HashSet
    2.)TreeSet
    3.)(maybe) LinkedHashSet
-Queue
    1.) PriorityQueue
    2.)ArrayQueue
    3.)LinkedList

Question 14

What is a List

Answer 14

Lists are an interface that have positional access i.e. indexing, allows duplicates, and is always sequentially ordered. Real world example is like a train, each train car resembles a node, linked to the other.

Question 15

What is an ArrayList?

Answer 15

Implemented using arrays
Increases size by 50% each time it needs to increase size Default size is 10
Can only hold objects

Question 16

ArrayList vs LinkedList

Answer 16

It’s elements can be accessed directly by using the get and set methods, since ArrayList is essentially an array. LinkedList is implemented as a double linked list. Its performance on add and remove is better than Arraylist, but worse on get and set methods.

Question 17

What is a Vector?

Answer 17

Vectors are similar to ArrayLists in which they can be accessed by get and set methods and size dynamically. The only major differences is Vectors are thread-safe as opposed to ArrayLists. Which are not. Addittionally while an ArrayList increases its size by 50% each time it needs to. A Vector increases its size by 100%

Question 18

What is a set?

Answer 18

an interface apart of Collections API No Positional access i.e. indexing, does no allow duplicates, not always sequentially ordered Real world example is data tables that are normalized, unique entries, identifying keys like social security, driver licence number. Examples:
Hashset, treeset, hashtable

Question 19

What is a map?

Answer 19

A part of the aggregate data Structures
Keys stored as a set, values as a List
Interface that uses key-value pairs
The key values are linked to a memory address in the heap As fast accessing time O(1)
map
Maps are not iterable, but the set of their keys are iterable.

Question 20

HashMap vs TreeMap vs HashTable

Answer 20

•HashMap:
May have a null key Many null values

•TreeMap:
No null Keys
Many null values

•HashTable:
No null keys
No null values Thread safe Deprecated