Data Structures and Algorithms for Designing a Twitter Feed: A Complete Implementation Guide

Designing a Twitter feed requires combining a singly-linked list for chronological tweets, a hash set for follower relationships, and a max-heap to merge multiple sorted streams into a unified timeline.

The labuladong/fucking-algorithm repository provides a comprehensive object-oriented solution to the classic LeetCode 355 "Design Twitter" problem. This implementation demonstrates how to efficiently manage user relationships and retrieve the 10 most recent tweets using fundamental data structures and the "merge k sorted lists" algorithm pattern.

Core Data Structures for Twitter Feed Design

The architecture relies on three interconnected classes that separate concerns between tweet storage, user state management, and API orchestration.

The Tweet Node (Singly-Linked List)

Each tweet acts as a node in a singly-linked list ordered by time. According to the source code in 数据结构系列/设计Twitter.md (lines 31-44), the Tweet class stores three fields:

• id: The unique tweet identifier
• time: A monotonically increasing global timestamp
• next: A pointer to the next (older) tweet

New tweets are inserted at the head of the list, ensuring the chain remains sorted from newest to oldest without re-sorting. This design choice enables O(1) insertion when a user posts content.

The User Entity (HashSet for Following Relationships)

The User class (lines 62-78 in 数据结构系列/设计Twitter.md) encapsulates a user's state using two primary structures:

• followed: A HashSet<Integer> storing IDs of all followed users (including the user themselves)
• head: A reference to the head of the user's tweet linked list

The class provides follow(), unfollow(), and post() methods that manipulate these fields. The HashSet guarantees O(1) complexity for checking and updating follow relationships, while the head pointer enables immediate access to the user's most recent content.

The Twitter Class (HashMap for Global State)

The façade class maintains system-wide state as implemented in lines 84-110:

• timestamp: A global counter incremented for every new tweet
• userMap: A HashMap<Integer, User> mapping user IDs to User objects, creating users on-the-fly when first referenced

This design ensures that postTweet, follow, and unfollow operations execute in constant time by delegating directly to the appropriate User instance.

The Feed Generation Algorithm (Merge K Sorted Lists)

The getNewsFeed method implements the critical timeline generation logic using a max-heap (priority queue) to solve the "merge k sorted lists" problem.

Algorithm Mechanics

When generating a feed for user ID u, the system performs these steps:

1. Collect heads: Retrieve the head pointer from every user in u's followed set (including u themselves). This yields k separate sorted linked lists.

2. Initialize max-heap: Insert all k heads into a priority queue ordered by time in descending order (newest first).

3. Merge and collect: Repeatedly pop the tweet with the highest timestamp from the heap and append its ID to the result list. If the popped tweet has a next pointer, push that next node into the heap to continue traversing that user's history.

4. Termination: Stop after collecting 10 tweet IDs or when the heap empties.

This approach guarantees that tweets are returned in global chronological order (newest first) across all followed users, not just within individual user timelines.

Complexity Analysis

The heap-based merge operates in O(N log k) time, where:

• k is the number of followed users (number of lists being merged)
• N is the total tweets examined (capped at 10 in the problem constraints, or 10 × k in worst-case scenarios)

Each heap operation (poll() and add()) costs O(log k), and we perform at most 10 extract-max operations plus at most 10 insertions of next nodes.

Complete Java Implementation

The following runnable example demonstrates all four required APIs (postTweet, getNewsFeed, follow, unfollow) as implemented in the repository:

import java.util.*;

public class Twitter {
    private static int timestamp = 0;
    private HashMap<Integer, User> userMap = new HashMap<>();
    
    private static class Tweet {
        int id;
        int time;
        Tweet next;
        
        Tweet(int id) {
            this.id = id;
            this.time = timestamp++;
        }
    }
    
    private static class User {
        int id;
        Set<Integer> followed = new HashSet<>();
        Tweet head = null;
        
        User(int id) {
            this.id = id;
            follow(id); // Users follow themselves by default
        }
        
        void follow(int userId) {
            followed.add(userId);
        }
        
        void unfollow(int userId) {
            if (userId != this.id) {
                followed.remove(userId);
            }
        }
        
        void post(int tweetId) {
            Tweet newTweet = new Tweet(tweetId);
            newTweet.next = head;
            head = newTweet;
        }
    }
    
    public void postTweet(int userId, int tweetId) {
        if (!userMap.containsKey(userId)) {
            userMap.put(userId, new User(userId));
        }
        User u = userMap.get(userId);
        u.post(tweetId);
    }
    
    public List<Integer> getNewsFeed(int userId) {
        List<Integer> res = new ArrayList<>();
        if (!userMap.containsKey(userId)) return res;
        
        // Max-heap ordered by time (newest first)
        PriorityQueue<Tweet> pq = new PriorityQueue<>((a, b) -> b.time - a.time);
        
        // Collect heads of all followed users' tweet lists
        for (int followeeId : userMap.get(userId).followed) {
            if (userMap.containsKey(followeeId)) {
                Tweet head = userMap.get(followeeId).head;
                if (head != null) pq.add(head);
            }
        }
        
        // Merge k sorted lists
        while (!pq.isEmpty() && res.size() < 10) {
            Tweet t = pq.poll();
            res.add(t.id);
            if (t.next != null) {
                pq.add(t.next);
            }
        }
        return res;
    }
    
    public void follow(int followerId, int followeeId) {
        if (!userMap.containsKey(followerId)) {
            userMap.put(followerId, new User(followerId));
        }
        if (!userMap.containsKey(followeeId)) {
            userMap.put(followeeId, new User(followeeId));
        }
        userMap.get(followerId).follow(followeeId);
    }
    
    public void unfollow(int followerId, int followeeId) {
        if (userMap.containsKey(followerId)) {
            userMap.get(followerId).unfollow(followeeId);
        }
    }
}

This implementation mirrors the design found in 数据结构系列/设计Twitter.md and supports the example usage pattern shown in the repository's walkthrough.

Summary

• Tweet storage: Use a singly-linked list with head insertion to maintain chronological order in O(1) time per post.
• Following relationships: Employ a HashSet within each User object for O(1) follow/unfollow checks and O(k) iteration when building feeds.
• Global user registry: Maintain a HashMap<Integer, User> to locate any user by ID in constant time.
• Feed generation: Apply the merge k sorted lists algorithm using a max-heap (priority queue) to produce a globally ordered timeline in O(N log k) time.
• Source location: The complete design and analysis are documented in labuladong/fucking-algorithm/数据结构系列/设计Twitter.md.

Frequently Asked Questions

What data structures are needed to design a Twitter feed?

You need four core structures: a singly-linked list for each user's tweets (enabling O(1) insertion at the head), a HashSet within each user to track followed accounts (O(1) membership testing), a HashMap to map user IDs to User objects globally, and a PriorityQueue (max-heap) to merge multiple sorted tweet streams when generating feeds.

How does the Twitter feed algorithm merge posts from multiple users?

The algorithm treats each followed user's tweet history as a sorted linked list. It initializes a max-heap with the head (most recent tweet) of each list, then repeatedly extracts the newest tweet across all lists. After extracting a tweet, it pushes that user's next older tweet into the heap, maintaining the invariant that the heap always contains the newest unseen tweet from each user.

What is the time complexity of generating a Twitter news feed?

Generating a feed containing the 10 most recent posts requires O(N log k) time, where k is the number of followed users and N is the number of tweets retrieved (capped at 10). Each heap insertion and extraction costs O(log k), and we perform at most 2N heap operations (one pop and potentially one push per retrieved tweet).

Where can I find implementations in other programming languages?

The repository provides equivalent solutions in Python, C++, and other languages within the 多语言解法代码/solution_code.md file. These implementations adapt the same algorithmic approach—linked lists for tweet storage and heaps for feed merging—to language-specific data structures like Python's heapq module.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}