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.
How can doubly linked lists be used to implement a Least Recently Used (LRU) Cache?
Nodes represent cached items. Recently used items are moved to the front of the list, while least recently used items (nodes at the tail) are removed, maintaining a cache based on access frequency.
Given the head of a doubly linked list, swap the nodes in pairs. For example, given the linked list 1 -> 2 -> 3 -> 4, the function should return 2 -> 1 -> 4 -> 3
Iterate through the list, starting from the head. If the current node and its next node exist, swap their data and pointers (prev, next). Remember to handle edge cases like the last node or odd number of nodes.
You are given two sorted doubly linked lists, head1 and head2. Write a function to merge these lists into a single sorted doubly linked list.
Create a new empty list. Iterate through both head1 and head2 simultaneously, comparing the data of each node. Add the smaller node to the new list and move the corresponding pointer in the original list.
