Doubly Linked List Flashcards
What is the difference between singly and doubly linked list?
The doubly linked list has a pointer pointing back to its previous node.
Create a doubly linked list with a pop
and push
methods.
Look at notes!
What is a doubly linked list?
A data structure
What properties are in our doubly linked list class?
A head, tail and length properties.
What are the disadvantages of doubly linked lists compared to arrays?
Accessing a specific element by index is slower in linked lists as you need to traverse the list to find it.
More memory usage.
What properties are in our Node class for our doubly linked list?
A value property, next property, and previous property.
What are the advantages of using doubly linked lists over arrays?
Inserting or deleting nodes in the middle of a linked list is faster than arrays as no elements need to be shifted.
Try to implement a reverse doubly linked list.
Look at notes.
How would you implement a get method?
Implement it.
Using the the index, you want to work from the tail or head, whichever is closest.
How would you replace a value of a node?
Implement it.
Using the get method.
Implement a unshifting method.
Look at notes.
Implement a insert method.
Look at notes.
Implement a remove method.
Look at notes.
Implement a shift method.
Look at notes.
Why are doubly linked lists useful for implementing undo/redo functionality?
Each node can represent a past state. Traversing backwards and updating references allows you to easily revert to a previous state stored in the list.