Doubly-LinkedList

Question 1

Is the Doubly LinkedList Random or Sequential Access?

Answer 1

Sequential

Question 2

What data structure is the Doubly-LinkedList nearly exactly the same as?

Answer 2

The Singly-LinkedList.

Question 3

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

Answer 3

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

Question 4

Define the ‘Next’ value of a Node.

Answer 4

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

Question 5

Define the ‘Previous’ value of a Node.

Answer 5

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

Question 6

Will the head node have a previous pointer?

Answer 6

No, it will be null.

Question 7

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

Answer 7

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 8

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

Answer 8

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 9

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

Answer 9

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 10

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

Answer 10

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 11

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

Answer 11

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 12

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

Answer 12

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 13

Are the BigO TimeComplexities of a Doubly-LinkedList the same as those of a Singly-LinkedList?

Answer 13

Yes.

Question 14

What is the BigO of ACCESSING a Doubly-LinkedList?

Answer 14

O(n) - Linear Search

Question 15

What is the BigO of SEARCHING a Doubly-LinkedList?

Answer 15

O(n) - Linear Search

Question 16

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

Answer 16

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

Question 17

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

Answer 17

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

Question 18

Use cases for a Doubly-LinkedList? (2)

Answer 18

1. Browser history.

2. Undo-Redo functionality.

Question 19

When is a Doubly-LinkedList useful?

Answer 19

When you need stack-like functionality that requires traversing back and forth through the Stack.

Question 20

What are some beneficial attributes of LinkedLists?

Answer 20

1. 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.