Doubly-LinkedList

Question 1

Is the Doubly LinkedList Random or Sequential Access?

Answer 1

Sequential

Question 2

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

Answer 2

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

Question 3

Define the ‘Next’ value of a Node.

Answer 3

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

Question 4

Define the ‘Previous’ value of a Node.

Answer 4

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

Question 5

Will the head node have a previous pointer?

Answer 5

No, it will be null.

Question 6

How do we add to the head of a Doubly-LinkedList? (3)

Answer 6

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.

Question 7

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

Answer 7

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.

Question 8

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

Answer 8

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.

Question 9

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

Answer 9

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.

Question 10

How do we ADD to the tail of a Doubly-LinkedList? (3)

Answer 10

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.

Question 11

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

Answer 11

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.

Question 12

What is the BigO of ACCESSING a Doubly-LinkedList?

Answer 12

O(n) - Linear Search

Question 13

What is the BigO of SEARCHING a Doubly-LinkedList?

Answer 13

O(n) - Linear Search

Question 14

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

Answer 14

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

Question 15

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

Answer 15

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

Question 16

Use cases for a Doubly-LinkedList? (2)

Answer 16

1. Browser history.
2. Undo-Redo functionality.

Question 17

When is a Doubly-LinkedList useful?

Answer 17

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

Question 18

What are some beneficial attributes of LinkedLists?

Answer 18

Adaptability of the Nodal structure.

Since all information is stored inside of a shell (a Node) it makes it much easier to move the information around.

This combined with the pointer system allows for non-contiguous but still fast operating speed.