✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-055

Stack Implementation Using Linked Lists

A linked-list-based stack stores each element in a node and uses a reference to the first node as the stack top. Push and pop operations are normally performed at the head of the linked list.

Explanation

Overview

A linked-list stack is an implementation of the stack abstract data type using dynamically connected nodes. Each node stores data and a reference to the next node, while the top reference identifies the most recently inserted node.

Purpose

This implementation is useful when the stack size changes dynamically and a fixed array capacity is undesirable.

Key concepts

name: Core idea; description: The central focus of stack implementation using linked lists is the capability described here: A linked-list-based stack stores each element in a node and uses a reference to the first node as the stack top. Push and pop operations are normally performed at the head of the linked list.; name: Problem context; description: Stack Implementation Using Linked Lists is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using stack implementation using linked lists, check its assumptions, input requirements, expected output, and resource constraints.

Time complexity

push: O(1); pop: O(1); peek: O(1); isEmpty: O(1); size: O(1) when a size counter is maintained; search: O(n)

Space complexity

O(n) for n nodes, including one next reference per node and node-allocation overhead.

Example

operations: PUSH(10); PUSH(20); afterPush: TOP → 30 → 20 → 10 → NULL; afterPop: TOP → 20 → 10 → NULL; removedElement: 30; explanation: Each push adds a node at the head. Each pop removes the head node.

Advantages

Can grow dynamically as nodes are allocated.; Does not require a predetermined maximum capacity.; Push and pop at the top take O(1) time.; Does not require shifting existing elements.; Uses memory according to the number of stored nodes, subject to allocation overhead.

Example or application

Operations

  • PUSH(10)

  • PUSH(20)

  • PUSH(30)

  • POP()

After Push

TOP → 30 → 20 → 10 → NULL

After Pop

TOP → 20 → 10 → NULL

Removed Element

30

Explanation

Each push adds a node at the head. Each pop removes the head node.

Definition

A linked-list stack is an implementation of the stack abstract data type using dynamically connected nodes. Each node stores data and a reference to the next node, while the top reference identifies the most recently inserted node.

Purpose

This implementation is useful when the stack size changes dynamically and a fixed array capacity is undesirable.

Internal Structure

Node

Contains a data field and a next reference.

Top

References the node containing the most recently inserted element.

Next

Connects a node to the node immediately below it in the stack.

Size

An optional counter storing the number of nodes.

Initial State

Top

NULL

Stack

EMPTY

Size

0

Push Procedure

  • Create a new node containing the value.

  • Set the new node's next reference to the current top.

  • Update top to reference the new node.

  • Increase the size counter if maintained.

Pop Procedure

  • Check whether top is null.

  • If the stack is empty, report or handle underflow.

  • Save the data stored in the top node.

  • Move top to the next node.

  • Release or discard the removed node according to the language's memory-management rules.

  • Decrease the size counter if maintained.

  • Return the saved value.

Peek Procedure

  • Check whether top is null.

  • Read the data in the top node.

  • Return the value without changing the top reference.

Advantages

  • Can grow dynamically as nodes are allocated.

  • Does not require a predetermined maximum capacity.

  • Push and pop at the top take O(1) time.

  • Does not require shifting existing elements.

  • Uses memory according to the number of stored nodes, subject to allocation overhead.

Limitations

  • Each node requires additional memory for a next reference.

  • Node allocation and deallocation can introduce overhead.

  • Memory may be less cache-friendly than a contiguous array.

  • Reference management increases implementation complexity.

  • The stack can still run out of available memory.

Time Complexity

Push

O(1)

Pop

O(1)

Peek

O(1)

Is Empty

O(1)

Size

O(1) when a size counter is maintained

Search

O(n)

Space Complexity

O(n) for n nodes, including one next reference per node and node-allocation overhead.

Array Vs Linked List

Capacity

An array stack may have fixed capacity or dynamic resizing; a linked-list stack grows node by node.

Memory

Array stacks avoid per-node reference storage, while linked-list stacks require a next reference for each node.

Locality

Arrays generally provide better cache locality because elements are stored contiguously.

Push And Pop

Both implementations normally support O(1) push and pop at the top, excluding occasional array resizing and allocation overhead.

Implementation Considerations

  • Use null to represent an empty top reference.

  • Create the new node before changing the top reference.

  • Preserve the old top when connecting the new node.

  • Handle memory release according to the programming language.

  • Maintain the size counter if the interface requires constant-time size queries.

  • Avoid accessing a removed node after its memory has been released.

Common Applications

  • Dynamic expression evaluation

  • Function-call management

  • Undo histories

  • Depth-first search

  • Backtracking algorithms

  • Managing temporary data

Learning Objectives

  • Understand how linked-list nodes represent stack elements.

  • Explain why the head can serve as the stack top.

  • Describe push, pop, and peek procedures.

  • Compare array-based and linked-list-based stacks.

  • Analyze memory and operation complexity.

Key Takeaways

  • The top reference points to the first node.

  • Push inserts a new node at the head.

  • Pop removes the head node.

  • Push and pop normally take O(1) time.

  • The implementation grows dynamically but requires additional reference memory.

Related Topics

  • Introduction to Stacks

  • Stack Operations — Push, Pop, and Peek

  • Stack Implementation Using Arrays

  • Linked List Node and Memory Structure

  • Dynamic Memory Allocation

  • Stack Overflow and Underflow

Key Concepts

NameDescription

Core idea

The central focus of stack implementation using linked lists is the capability described here: A linked-list-based stack stores each element in a node and uses a reference to the first node as the stack top. Push and pop operations are normally performed at the head of the linked list.

Problem context

Stack Implementation Using Linked Lists is relevant when a computational task requires the behavior or capability described by this topic.

Correct use

Before using stack implementation using linked lists, check its assumptions, input requirements, expected output, and resource constraints.

Practice Questions

QuestionAnswer

What is the main purpose of stack implementation using linked lists?

A linked-list-based stack stores each element in a node and uses a reference to the first node as the stack top. Push and pop operations are normally performed at the head of the linked list.

What should be checked before applying stack implementation using linked lists?

For stack implementation using linked lists, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints.

How can an implementation of stack implementation using linked lists be validated?

Trace a representative stack implementation using linked lists case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Scienexy Computer Science Reference

Suggest a correction or source · More in Algorithms & Data Structures