1
Q

Is the Doubly LinkedList Random or Sequential Access?

A

Sequential

2
Q

What’s the key difference between the Doubly-LinkedList and the Singly-LinkedList? And what benefit does this provide?

A

It tracks both the next and previous Nodes in the list. This allows you to traverse the list in both directions.

3
Q

Define the ‘Next’ value of a Node.

A

That particular Nodes pointer which points to the next object in the list.

4
Q

Define the ‘Previous’ value of a Node.

A

That particular Nodes pointer which points to the previous object in the List.

5
Q

Will the head node have a previous pointer?

A

No, it will be null.

6
Q

A
1. Set the new Node’s next to point towards the current head of the list.
2. Take the new node that we want to insert, and set it’s previous to null.
3. Set the current head’s previous to point towards this new `Node.
7
Q

A
1. Set the head Node’s next to point towards a null value.
2. Set the second Node’s previous to also point towards a null value.
8
Q

How do we INSERT into the middle of a Doubly-LinkedList? (3)

A
1. Set the Node’s previous to point to the Node previous to the position you want to insert at.
2. Set the new Node’s next to point to the Node after the position you want to insert at.
3. Set the next and previous on the Node’s before and after the one you’re inserting to point towards the new Node.
9
Q

How do we REMOVE from the middle of a Doubly-LinkedList? (3)

A
1. Set the Node before the one we want to remove’s next to point to the Node after the one we want to remove.
2. Set the Node after the one we want to remove’s previous to point to the Node before the one we want to remove.
3. Set both pointers of the Node we want to remove to point to a null value.
10
Q

A
1. Set the next pointer of the current tail to point towards the new Node we want to become the tail.
2. Set the previous of the new node that we’re adding to be pointing to the current tail of the list.
3. Make the new Node’s next point to a null value.
11
Q

How do we REMOVE from the tail of a Doubly-LinkedList? (2)

A
1. Set the tail Node’s previous to point to null.
2. Set the second to last Node’s next to also point to null.
12
Q

What is the BigO of ACCESSING a Doubly-LinkedList?

A

O(n) - Linear Search

13
Q

What is the BigO of SEARCHING a Doubly-LinkedList?

A

O(n) - Linear Search

14
Q

What is the BigO of INSERTING into a Doubly-LinkedList?

A

O(1) for tail operation - If stored in memory.
O(n) for everywhere else.

15
Q

What is the BigO of DELETING from a Doubly-LinkedList?

A

O(1) for tail operation - If stored in memory.
O(n) for everywhere else.

16
Q

Use cases for a Doubly-LinkedList? (2)

A
1. Browser history.
2. Undo-Redo functionality.
17
Q

A

When you need stack/queue functionality that requires traversing back and forth through the data structure.

18
Q

What are some beneficial attributes of LinkedLists?

A