Why Doubly Linked List Over Singly Linked List in DSA C - Quick Recap

Recall & Review

beginner

What is a doubly linked list?

A doubly linked list is a type of linked list where each node has two pointers: one to the next node and one to the previous node. This allows traversal in both directions.

beginner

Why might we prefer a doubly linked list over a singly linked list?

Because doubly linked lists allow easy backward traversal and efficient deletion of nodes without needing to traverse from the head, unlike singly linked lists.

beginner

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

Doubly linked lists 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

How does deletion of a node differ between singly and doubly linked lists?

In singly linked lists, to delete a node, you must find the previous node by traversing from the head. In doubly linked lists, you can access the previous node directly, making deletion faster.

beginner

Can doubly linked lists be traversed backwards? Why is this useful?

Yes, doubly linked lists can be traversed backwards because each node has a pointer to the previous node. This is useful for operations like reverse iteration or undo functionality.

What extra pointer does a doubly linked list node have compared to a singly linked list node?

A Pointer to the next next node

B Pointer to the head node

C Pointer to the tail node

D Pointer to the previous node

A doubly linked list node has a pointer to the previous node, allowing backward traversal.

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

A Inserting at the head

B Finding the head node

C Deleting a node when given a pointer to it

D Traversing from head to tail

Deleting a node is faster because the previous node is directly accessible in a doubly linked list.

What is a downside of doubly linked lists?

A Uses more memory per node

B Cannot traverse backwards

C Cannot insert at tail

D No pointer to next node

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

Which traversal is NOT directly supported by a singly linked list?

A Forward traversal

B Backward traversal

C Traversal from head

D Traversal to tail

Singly linked lists do not support backward traversal because nodes only point forward.

Why might you choose a singly linked list over a doubly linked list?

A Want to save memory

B Need faster deletion

C Need backward traversal

D Want to traverse backwards

Singly linked lists use less memory per node, making them better when memory is limited.

Explain the main reasons to use a doubly linked list instead of a singly linked list.

Think about how nodes connect and how operations like deletion work.

Describe the trade-offs between singly and doubly linked lists in terms of memory and operation efficiency.

Consider what each node stores and how it affects traversal and deletion.