Doubly Linked Lists

Question 1

There are 3 attributes of a DLL node, what are they

Answer 1

T item
DLLNode next
DLLNode prev

Question 2

If there is only one element in the DLL what will the node look like

Answer 2

Data space is filled
Next is null
Prev is null

Question 3

What does the first node (head) of a DLL look like

Answer 3

Data
Next points to next node in DLL
Prev is null

Question 4

What does the last node in a DLL look like

Answer 4

Data
Next is null
Prev points to previous node in the DLL

Question 5

What does a middle node in a DLL look like

Answer 5

Data
Next points to the next node in the DLL
Prev points to the previous node in the DLL

Question 6

Steps to insert a node at the end of a DLL

Answer 6

Make a temp node, with data and null prev and next

Connect prev to what used to be tail

Assign tail to new temp node

Question 7

Steps to insert a node in the middle of a DLL

Answer 7

Find position we want to add at

Make a temp node with data and null prev and next

Change next of previous node to point to temp

Change prev of temp node to point to previous node

Change prev of next node to point to temp node

Change next of temp node to point to next node

Now it is part of the list

Question 8

benefits of doubly linked lists

Answer 8

can iterate in reverse

can be extended - do not need to know the exact amount of elements needed beforehand

Question 9

order of growth for searching a doubly linked list

Answer 9

big O (N)

Question 10

how should nodes be updated to prevent losing access to them

Answer 10

one side at a time

Question 11

disadvantage of a linked list

Answer 11

must search through entire list before accessing

if searching, it’ll take iterating through the entire list before discovering that an element doesn’t exist in the list

Question 12

benefits of a linked list

Answer 12

easy to insert anywhere into the list