LinkedLists & ArrayLists Review

How does a Doubly LinkedList work? Mention:

• Travesal

• Nodes/pointers (ex: value, next, prev)

• It’s a list that allows you to traverse both forwards and backwards.

• Each node has 3 pointers: value, next that points to the successive node, and prev that points to the previous node.

What are the 2 pros of using Doubly LinkedList?

• Removes & inserts at both ends of the list efficiently.

• Traverses backwards easily.

What are the 2 cons of using a Doubly LinkedList?

• Uses extra memory because it moves backwards and has ‘prev’ pointer.

• Getting to a specific index still requires O(n) complexity.

What are the 2 best use-cases for Doubly LinkedList?

• Implementing stacks or queues.

• When you frequently need to move back and forth in a list.

How does a Singly LinkedList work? Mention:

• Travesal

• Nodes/pointers (ex: value, next, prev)

• You can only move forwards in a Singly LinkedList.

• Each node has 2 pointers: next and value.

What are the 2 pros of using Singly LinkedList?

• Uses less memory than Doubly LinkedList.

• Inserting/removing only at the end is O(1).

What are the 2 cons of using Singly LinkedList?

• You can’t move backwards.

• Adding/removing at the end requires an O(n) complexity.

What are the 2 best use-cases for Singly LinkedList?

• Creating a simple queue where you mostly operate at the head.

• When you want to use less memory.

How does an ArrayList work?

It’s basically an array that grows dynamically in size that uses indexes instead of pointers like Singly and Doubly LinkedLists do.

What are the 2 pros of an ArrayList?

• You can get elements quickly by index.

• Adding an element to the end of the ArrayList is O(1) amortized.

What are the 2 cons of an ArrayList?

• Inserting/Removing at the front & end requires O(n) complexity.

• Resizing of the array is also an O(n) complexity.

What’s the best use-case of an ArrayList?

When you’re mainly interested in accessing and retrieving elements rather than modifying the list by inserting/deleting anything.