Skip to main content

​
Overview

Push Swap uses a doubly-linked list structure to represent both Stack A and Stack B. Each node contains not only the data value but also metadata used for optimization during sorting.

​
The t_list Structure

The core data structure is defined in push_swap.h:21-31: 
typedef struct s_list
{
    int             nbr;           // The actual value stored in the node
    int             index;         // Current position in the stack
    int             push_cost;     // Cost to push this node to the other stack
    int             above_median;  // Flag: true if above median position
    int             cheapest;      // Flag: true if this is the cheapest node to move
    struct s_list   *target_node;  // Pointer to target node in other stack
    struct s_list   *next;         // Next node in the list
    struct s_list   *prev;         // Previous node in the list
}   t_list;

​
Field Descriptions

Stores the integer value that was passed as input. This is the actual number that needs to be sorted.Type: intUsage: Compared during sorting operations to determine the correct position of nodes.
Represents the current position of the node in its stack, starting from 0 at the top.Type: intUpdated by: current_index() function (init_a_to_b.c:15-34)Purpose: Used to calculate rotation costs and determine if a node is above or below the median.
The total number of operations required to move this node to its target position in the other stack.Type: intCalculated by: cost_analysis_a() function (init_a_to_b.c:64-82)Formula:
  • If above median: cost = index + target_index
  • If below median: cost = (stack_len - index) + target_cost
Boolean flag indicating whether the node is in the upper half of the stack.Type: int (used as boolean)Purpose: Determines whether to use rotate (ra/rb) or reverse rotate (rra/rrb) operations.Set in: current_index() - nodes at position ≤ median/2 are marked as above_median.
Boolean flag marking the node with the lowest push_cost in the stack.Type: int (used as boolean)Set by: set_cheapest() function (init_a_to_b.c:84-102)Usage: Only one node per stack is marked as cheapest at any time.
Points to the node in the opposite stack where this node should be positioned.Type: struct s_list *Set by:
  • set_target_a() - When moving from A to B (init_a_to_b.c:36-62)
  • set_target_b() - When moving from B to A (init_b_to_a.c:15-41)
Logic:
  • From A to B: Find the largest value in B that is smaller than the current node
  • From B to A: Find the smallest value in A that is larger than the current node
Points to the next node in the stack (towards the bottom).Type: struct s_list *Value: NULL for the last node in the stack.
Points to the previous node in the stack (towards the top).Type: struct s_list *Value: NULL for the first node (top) of the stack.Purpose: Enables bidirectional traversal of the list.

​
Doubly-Linked List Implementation

The Push Swap implementation uses a circular doubly-linked list structure that provides several advantages:

​
Benefits

  1. Efficient Rotation: Both forward (ra/rb) and reverse rotation (rra/rrb) operations are O(1) with proper pointer manipulation
  2. Bidirectional Traversal: Can traverse the stack from top to bottom or bottom to top
  3. Easy Node Insertion/Deletion: Push and pop operations are efficient

​
Structure Properties

  • The top of the stack is the first node (stack head pointer)
  • The bottom of the stack is the last node
  • Top node’s prev pointer is NULL
  • Bottom node’s next pointer is NULL

​
Stack Utility Functions

The implementation provides several utility functions for working with stacks:

​
stack_len()

int stack_len(t_list *stack)
Location: stack_utils.c:15-28 Purpose: Returns the number of nodes in a stack. Implementation: 
int stack_len(t_list *stack)
{
    int count;

    if (!stack)
        return (0);
    count = 0;
    while (stack)
    {
        stack = stack->next;
        count++;
    }
    return (count);
}
Time Complexity: O(n) where n is the stack size.

​
find_min()

t_list *find_min(t_list *stack)
Location: stack_utils.c:64-82 Purpose: Returns a pointer to the node with the minimum value in the stack. Implementation:
  • Traverses the entire stack
  • Compares each node’s nbr value
  • Returns pointer to the node with the smallest value
  • Returns NULL if stack is empty
Usage: Used in set_target_a(), set_target_b(), and min_on_top() functions.

​
find_max()

t_list *find_max(t_list *stack)
Location: stack_utils.c:84-102 Purpose: Returns a pointer to the node with the maximum value in the stack. Implementation:
  • Traverses the entire stack
  • Compares each node’s nbr value
  • Returns pointer to the node with the largest value
  • Returns NULL if stack is empty
Usage: Used as fallback in set_target_a() when no suitable smaller value exists in Stack B.

​
Memory Management

All nodes are dynamically allocated and must be properly freed. The implementation includes a free_stack() function to deallocate all nodes in a stack when sorting is complete or when an error occurs.

​
Performance Characteristics

OperationTime Complexity
stack_len()O(n)
find_min()O(n)
find_max()O(n)
Access by indexO(n)
Push/Pop (top)O(1)
RotationO(1)
Where n is the number of elements in the stack.

Build docs developers (and LLMs) love

Get started for freeTalk to us