Doubly Linked List

Question 1

What is the difference between singly and doubly linked list?

Answer 1

The doubly linked list has a pointer pointing back to its previous node.

Question 2

Create a doubly linked list with a pop and push methods.

Answer 2

Look at notes!

Question 3

What is a doubly linked list?

Answer 3

A data structure

Question 4

What properties are in our doubly linked list class?

Answer 4

A head, tail and length properties.

Question 4

What are the disadvantages of doubly linked lists compared to arrays?

Answer 4

Accessing a specific element by index is slower in linked lists as you need to traverse the list to find it.

More memory usage.

Question 4

What properties are in our Node class for our doubly linked list?

Answer 4

A value property, next property, and previous property.

Question 5

What are the advantages of using doubly linked lists over arrays?

Answer 5

Inserting or deleting nodes in the middle of a linked list is faster than arrays as no elements need to be shifted.

Question 6

Try to implement a reverse doubly linked list.

Answer 6

Look at notes.

Question 7

How would you implement a get method?

Implement it.

Answer 7

Using the the index, you want to work from the tail or head, whichever is closest.

Question 8

How would you replace a value of a node?

Implement it.

Answer 8

Using the get method.

Question 9

Implement a unshifting method.

Answer 9

Look at notes.

Question 10

Implement a insert method.

Answer 10

Look at notes.

Question 11

Implement a remove method.

Answer 11

Look at notes.

Question 12

Implement a shift method.

Answer 12

Look at notes.

Question 13

Why are doubly linked lists useful for implementing undo/redo functionality?

Answer 13

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.

Question 14

How can doubly linked lists be used to implement a Least Recently Used (LRU) Cache?

Answer 14

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.

Question 15

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

Answer 15

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.

Question 16

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.

Answer 16

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.