Doubly Linked Lists - Programming for Machine Learning and Business

Moving Forward and Backward Through Nodes¶

first = {"value": 1, "prev": None, "next": None}
second = {"value": 2, "prev": first, "next": None}
first["next"] = second

print(first["next"]["value"])
print(second["prev"]["value"])

A doubly linked list lets each node look both forward and backward¶

Singly linked lists made one-way traversal simple. Doubly linked lists add a `prev` link as well as `next`, which makes reverse movement and some updates easier, but also means every insertion must maintain two directions consistently.

Key Idea¶

A doubly linked list stores references in both directions, which makes backward navigation easier than in a singly linked list.

Worked Example and Practice Lab¶

The first example shows the core upgrade from a singly linked list: once two nodes are connected, you can follow the relationship in either direction.

Doubly Linked-List Operations¶

These examples separate forward links, backward links, and insertion behavior.

Link two nodes¶

A doubly linked list stores both prev and next references.

Move forward¶

Follow the next references to traverse from head to tail.

Move backward¶

Follow the prev references to step back from the tail.

Insert a node in the middle¶

When inserting between two nodes, both the forward and backward links must be updated.

Exercises¶

Explain what extra link a doubly linked-list node stores compared with a singly linked node.
Describe one situation where backward traversal is useful.
Explain why inserting in the middle requires more updates than in a singly linked list.
Compare the tradeoff between easier navigation and extra maintenance work.

Guided Practice¶

What extra reference does a doubly linked-list node store compared with a singly linked node?¶

A sort indexThat is not the defining difference.

A reference to the previous nodeCorrect. Doubly linked lists support backward links.

A built-in queueNodes do not store a queue like that.

A file handleThat has nothing to do with linked-list structure.

Why can a doubly linked list move backward more easily?¶

Because it uses tuplesTuple usage is unrelated here.

Because each node stores `prev` as well as `next`Correct. The backward reference enables reverse traversal.

Because it is always sortedSorting is not guaranteed by the structure.

Because Python reverses it automaticallyThe node links are what matter.

Key Takeaway¶

Doubly linked lists trade extra bookkeeping for more flexible navigation. Each node can move forward and backward, which prepares you for richer graph- and tree-style pointer relationships later in the sequence.