🔁Data Structures Unit 2 Review

A singly linked list only lets you move forward through the nodes. A doubly linked list fixes that limitation by giving each node two pointers instead of one: one pointing to the next node and one pointing to the previous node. This bidirectional linking is what makes the structure so flexible.

Each node in a doubly linked list contains three fields:

Data storing the node's value
Next pointer pointing to the following node
Previous pointer pointing to the preceding node

The list itself maintains a head pointer (pointing to the first node) and a tail pointer (pointing to the last node). The head's previous pointer is null, and the tail's next pointer is null.

Because you can traverse in both directions, doubly linked lists simplify operations that are awkward in singly linked lists. For example, if you're given only a pointer to a node you want to delete, you can reach both its neighbors directly without traversing from the head. Common real-world uses include undo/redo functionality in text editors and forward/back navigation in web browsers.

Structure of doubly linked lists, CS 201: Lecture 25: Singly and Doubly-Linked Lists

Operations in doubly linked lists

Every insertion or deletion in a doubly linked list requires updating two pointers per affected node (next and previous), compared to just one in a singly linked list. Here's how each operation works:

Insertion at the beginning:

Create a new node
Set the new node's next to the current head
Set the new node's prev to null
Set the old head's prev to the new node
Update head to point to the new node
If the list was empty, also set tail to the new node

Insertion at the end:

Create a new node
Set the new node's prev to the current tail
Set the new node's next to null
Set the old tail's next to the new node
Update tail to point to the new node
If the list was empty, also set head to the new node

Insertion in the middle (after a given node $A$ ):

Create a new node $N$
Set $N$ 's next to $A$ 's next
Set $N$ 's prev to $A$
Set $A$ 's next's prev to $N$
Set $A$ 's next to $N$

Deletion at the beginning:

Set head to the current head's next
Set the new head's prev to null
If the list is now empty, set tail to null

Deletion at the end:

Set tail to the current tail's prev
Set the new tail's next to null
If the list is now empty, set head to null

Deletion in the middle (removing node $N$ ):

Set $N$ 's previous node's next to $N$ 's next
Set $N$ 's next node's prev to $N$ 's prev

Traversal is straightforward: forward traversal starts at head and follows next pointers until null; backward traversal starts at tail and follows prev pointers until null. Both are $O(n)$ .

Circular Linked Lists

Concept of circular linked lists

In a standard linked list, the last node's next pointer is null, marking the end. A circular linked list changes this: the last node's next pointer loops back to the first node, forming a continuous cycle with no null terminator.

There are two variants:

Circular singly linked list: The last node's next points to the head. You can only traverse forward, but you can reach any node from any starting point by continuing around the loop.
Circular doubly linked list: The last node's next points to the head, and the head's prev points to the last node. This gives you full bidirectional traversal with no dead ends.

Circular lists are a natural fit for problems that involve cycling through elements repeatedly. Round-robin CPU scheduling rotates through processes in a loop. Multiplayer game turns cycle through players continuously. Circular buffers use the same idea to manage fixed-size queues where old data gets overwritten.

One thing to watch for: since there's no null to signal the end, traversal logic needs a different stopping condition. You typically save a reference to your starting node and stop when you reach it again.

Doubly vs singly linked lists

Space complexity:

Singly linked lists use one pointer per node. Doubly linked lists use two, so they consume more memory per node.
Circular variants don't add extra memory beyond their non-circular counterparts. The last node simply reuses its existing pointer to point to the head instead of null.

Time complexity:

Operation	Singly Linked	Doubly Linked	Circular (Singly)	Circular (Doubly)
Insert at beginning	$O(1)$	$O(1)$	$O(1)$	$O(1)$
Insert at end	$O(n)$ *	$O(1)$	$O(1)$ **	$O(1)$
Delete at beginning	$O(1)$	$O(1)$	$O(1)$	$O(1)$
Delete at end	$O(n)$	$O(1)$	$O(n)$	$O(1)$
Delete given node	$O(n)$	$O(1)$	$O(n)$	$O(1)$
Traversal	Forward only, $O(n)$	Both directions, $O(n)$	Forward only, $O(n)$	Both directions, $O(n)$

* $O(1)$ if you maintain a tail pointer, which singly linked lists sometimes do.

** Assumes you maintain a pointer to the last node, which is standard practice for circular singly linked lists.

Ease of implementation:

Singly linked lists are the simplest since each operation only updates one pointer per node.
Doubly linked lists require more careful pointer management (two pointers per update), but the payoff is $O(1)$ deletion of any node you already have a reference to.
Circular linked lists add complexity around maintaining the loop. You need to handle the circular connection whenever you insert or delete, and your traversal logic must detect when you've completed a full cycle to avoid infinite loops.

🔁Data Structures Unit 2 Review