Doubly Linked List Flashcards

1
Q

What is the difference between singly and doubly linked list?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

A

Look at notes!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is a doubly linked list?

A

A data structure

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What properties are in our doubly linked list class?

A

A head, tail and length properties.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A

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

More memory usage.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A

A value property, next property, and previous property.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Try to implement a reverse doubly linked list.

A

Look at notes.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

How would you implement a get method?

Implement it.

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

How would you replace a value of a node?

Implement it.

A

Using the get method.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Implement a unshifting method.

A

Look at notes.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Implement a insert method.

A

Look at notes.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Implement a remove method.

A

Look at notes.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Implement a shift method.

A

Look at notes.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A

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 well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A

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.

15
Q

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

A

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.

16
Q

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.

A

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.