Linked List Summary

Theoretical Foundation of Linked Lists

This article introduces the following points:

The main types of linked lists are singly linked list, doubly linked list, and circular linked list.
Storage method of linked lists: the nodes of a linked list are stored in memory separately and connected by pointers.
How to perform CRUD (Create, Read, Update, Delete) operations on linked lists.
Performance analysis of arrays and linked lists in different scenarios.

Classic Linked List Problems

Dummy Head Node

One major issue with linked lists is that to operate on the current node, you must find the previous node first. This creates an awkward situation for the head node since there is no previous node.

Each time we deal with the head node's situation, it has to be handled separately, so using a dummy head node can solve this problem.

In this post, I've provided code examples with and without a dummy head node. By comparing them, everyone will notice the benefits of using a dummy head.

Basic Operations of Linked Lists

In the above post:

We practiced the five common operations on linked lists by designing a linked list.

This is a very good problem to practice basic operations on linked lists, assessing:

Obtaining the value of the node at index in the linked list
Inserting a node at the front of the linked list
Inserting a node at the end of the linked list
Inserting a node before the node at index in the linked list
Deleting the value of the node at index in the linked list

One could say that after solving this problem, you have acquired a grasp of basic operations with linked lists and no longer need to worry about understanding insertions, deletions, modifications, and queries related to them.

Here I still used the technique of employing a dummy head node; you can review this when looking over your code.

Reverse Linked List

In the above post:

It explains how to reverse a linked list.

Since the code for reversing a linked list is relatively simple, some students might have memorized it directly, but they still tend to make mistakes when writing it out.

Reversing a linked list is a high-frequency interview question and tests the interviewee's proficiency with linked list operations.

In the post, I provided two methods of reversal: iterative method and recursive method.

I suggest that everyone first thoroughly understand the iterative method before looking at the recursive method, as recursion can be quite convoluted; if you haven't mastered iteration yet, you'll likely struggle with recursion as well.

Delete the N-th node from the end

We use a virtual head node and the two-pointer method to remove the N-th node from the end of a linked list.

Intersection of Linked Lists

Intersection of Linked Lists uses two pointers to find the intersection point of two linked lists (where references are exactly identical, i.e., memory addresses are exactly identical).

Circular Linked List

It explains how to find a loop in a linked list and how to locate its entry point. This problem can be considered one of the more difficult problems regarding linked lists. However, the code is quite concise, mainly due to some mathematical proofs.

Summary

Linked List Basics

A linked list consists of nodes where each node stores:
- Data
- A pointer/reference to the next node
Types of linked lists:
- Singly linked list: One-directional links
- Doubly linked list: Links in both forward and backward directions
- Circular linked list: The last node links back to the first node

Linked List Operations

Basic Operations:
- Traversal: Visiting each node in sequence
- Insertion: Adding a node at a specific position
- Deletion: Removing a node from a specific position
- Searching: Finding a node with a given value
Advanced Operations:
- Reverse a linked list:
  - Iteratively adjust the pointers to reverse the direction of links
- Swap two adjacent nodes:
  - Use temporary pointers to adjust links
  - Time complexity: O(n), Space complexity: O(1)
- Remove the N-th node from the end:
  - Use a two-pointer approach
  - Maintain a gap of n nodes between pointers

Cycle Detection in Linked Lists

Problem: Detect if a linked list contains a cycle
Solution: Floyd’s Cycle Detection Algorithm (Tortoise and Hare Method):
- Two pointers: slow and fast
  - slow moves one step at a time
  - fast moves two steps at a time
- If they meet, a cycle exists
Steps to find the cycle start:
- After detecting a cycle, reset one pointer to the head
- Move both pointers one step at a time until they meet
- The meeting point is the start of the cycle
Mathematical reasoning for the algorithm:
- The distance traveled by the pointers can be represented as:
  - x+y+n×z=2×(x+y), where n is the number of cycles

Performance Analysis

Array vs. Linked List:
- Array:
  - Access: O(1)(random access via index)
  - Insert/Delete: O(n) (shifting elements)
- Linked List:
  - Access: O(n) (sequential traversal)
  - Insert/Delete: O(1) (if the reference to the node is provided)
Applications:
- Array: Suitable for frequent lookups and indexed operations
- Linked List: Suitable for dynamic insertions/deletions and sparse data