Doubly Linked List Structure and Node Design in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a doubly linked list?

A doubly linked list is a chain of nodes where each node has three parts: data, a link to the next node, and a link to the previous node. This allows moving forward and backward through the list.

beginner

What are the three parts of a node in a doubly linked list?

A node has: 1) data (the value stored), 2) next pointer (link to the next node), and 3) previous pointer (link to the previous node).

intermediate

Why does a doubly linked list need a previous pointer?

The previous pointer lets us move backward in the list, making it easier to traverse in both directions and to delete or insert nodes without starting from the head.

beginner

Show a simple Python class design for a doubly linked list node.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

beginner

What is the difference between singly and doubly linked lists?

Singly linked lists have nodes with only a next pointer, so you can only move forward. Doubly linked lists have both next and previous pointers, so you can move forward and backward.

What does the 'prev' pointer in a doubly linked list node point to?

A The next node in the list

B The tail of the list

C The head of the list

D The previous node in the list

The 'prev' pointer always points to the previous node, allowing backward traversal.

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

A Data

B Index number

C Next pointer

D Previous pointer

Nodes do not store index numbers; they only store data and pointers to next and previous nodes.

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

A To allow traversal in both directions

B To save memory

C Because it is simpler to implement

D Because it uses less pointers

Doubly linked lists allow moving forward and backward, unlike singly linked lists.

In Python, how do you initialize the next and previous pointers in a doubly linked list node?

A self.next = 0, self.prev = 0

B self.next = '', self.prev = ''

C self.next = None, self.prev = None

D self.next = [], self.prev = []

Pointers are initialized to None to show they do not point to any node yet.

What happens if the previous pointer of a node is None?

A It is the first node

B It is the last node

C The list is empty

D The node is disconnected

If prev is None, the node is the first node in the list.

Describe the structure of a doubly linked list node and explain why each part is important.

Think about how you move through the list and what information each node holds.

Explain the main difference between singly and doubly linked lists and when you might use each.

Consider traversal directions and ease of insertion/deletion.