Doubly linked list in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a doubly linked list?

A doubly linked list is a type of linked list where each node contains three parts: data, a pointer to the next node, and a pointer to the previous node. This allows traversal in both directions.

beginner

How does a doubly linked list differ from a singly linked list?

A singly linked list has nodes with only one pointer to the next node, allowing traversal in one direction. A doubly linked list has two pointers per node, enabling traversal forwards and backwards.

intermediate

What are the advantages of using a doubly linked list?

Advantages include easy backward traversal, efficient deletion of a node when given a pointer to it, and easier insertion before a given node compared to singly linked lists.

intermediate

What is a common disadvantage of doubly linked lists compared to singly linked lists?

They use more memory because each node stores an extra pointer to the previous node, and operations can be slightly slower due to managing two pointers.

intermediate

Describe the steps to insert a new node after a given node in a doubly linked list.

1. Create the new node with data.<br>2. Set the new node's next pointer to the given node's next.<br>3. Set the new node's previous pointer to the given node.<br>4. Update the given node's next node's previous pointer to the new node (if it exists).<br>5. Update the given node's next pointer to the new node.

What pointers does each node in a doubly linked list contain?

A Pointers to the next and previous nodes

B Pointer to the next node only

C Pointer to the previous node only

D No pointers, only data

Each node in a doubly linked list has two pointers: one to the next node and one to the previous node.

Which operation is easier in a doubly linked list compared to a singly linked list?

A Accessing the middle node directly

B Finding the head node

C Backward traversal

D Sorting the list

Backward traversal is easier because nodes have pointers to their previous nodes.

What is a disadvantage of doubly linked lists?

A They use more memory per node

B They cannot be traversed backwards

C They do not allow insertion

D They have no pointers

Doubly linked lists use more memory because each node stores two pointers instead of one.

If you have a pointer to a node in a doubly linked list, how can you delete it efficiently?

A By copying data from the next node

B You must start from the head to delete it

C You cannot delete nodes in doubly linked lists

D By updating the previous and next nodes' pointers to skip it

You can delete a node by adjusting the previous node's next pointer and the next node's previous pointer to bypass the node.

Which of these is NOT a part of a doubly linked list node?

A Data

B Pointer to head node

C Pointer to previous node

D Pointer to next node

Nodes do not store a pointer to the head node; they only store data and pointers to adjacent nodes.

Explain what a doubly linked list is and how it works.

Think about how nodes connect forwards and backwards.

Describe the advantages and disadvantages of using a doubly linked list.

Consider what extra pointer means for memory and functionality.