How to implement a stack using a linked list in Go

Explanation

Step 1: The stack is initially empty.

Step 2: A push operation adds an item to the top of the stack. The top shifts one place above its previous position.

Step 3: Each subsequent push adds an item to the top of the stack.

Step 4: A pop command removes an item from the top-1 position of the stack. The top shifts one place below its previous position.

Linked List Based Implementation

A stack implemented using a linked list does not have an upper bound on the number of items that can be added. An item is added to the head of the linked list using the push operation. Therefore, with each addition, the head pointer changes. Similarly, the head of the linked list is removed using the pop operation. The head pointer then points to the second node in the linked list.

The illustration below shows how a linked list-based stack works:

Implementation

A linked list basedstack implementation can be broken down into several functions. The purpose of each function is discussed below:

Function	Purpose
`Size`	Returns the number of items in the stack
`Push`	Adds a data item to the stack
`Pop`	Removes a data item from the stack
`IsEmpty`	Returns true if the stack is empty. Else, returns false
`Peek`	Returns the value at the top of the linked list but does not remove it
`Print`	Displays all elements of the stack

Function definitions

The functions used to implement an linked list based stack are defined as follows:

func (s *StackLinkedList) Size() int {}
func (s *StackLinkedList) IsEmpty() bool {}
func (s *StackLinkedList) Peek() (int, bool) {}
func (s *StackLinkedList) Push(value int) {}
func (s *StackLinkedList) Pop() (int, bool) {}
func (s *StackLinkedList) Print() {}

Example

The code below shows an linked list based implementation of the stack in Golang:

package main
import "fmt"
type Node struct {
 value int
 next *Node
}
type StackLinkedList struct {
 head *Node
 size int
}
// Size() function 
func (s *StackLinkedList) Size() int {
    return s.size
}
// IsEmpty() function 
func (s *StackLinkedList) IsEmpty() bool {
    return s.size == 0
}
// Peek() function 
func (s *StackLinkedList) Peek() (int) {
    if s.IsEmpty() {
        fmt.Println("StackEmptyException")
        return 0
    }
    return s.head.value
}
// Push() function
func (s *StackLinkedList) Push(value int) {
    s.head = &Node{value, s.head}
    s.size++
}
// Pop() function
func (s *StackLinkedList) Pop() (int, bool) {
    if s.IsEmpty() {
        fmt.Println("StackEmptyException")
        return 0, false
    }
    value := s.head.value
    s.head = s.head.next
    s.size--
    return value, true
}
// Print() function 
func (s *StackLinkedList) Print() {
    temp := s.head
    fmt.Print("Values stored in stack are: ")
    for temp != nil {
        fmt.Print(temp.value, " ")
        temp = temp.next
    }
    fmt.Println()
}
func main() {
	var stack StackLinkedList // create a stack variable of type StackLinkedList
    /* Adding items to stack */
	stack.Push(1)
	stack.Push(2)
	stack.Push(3)
  
    stack.Print() // Print the stack
    fmt.Println("Checking length of stack:")
    fmt.Println(stack.Size()) // Get Length
    fmt.Println("Removing an Item:")
    stack.Pop() // Remove an item
    stack.Print() 
    fmt.Println("Getting Item at Top of Linked List")
    fmt.Println(stack.Peek()) // Get Top-most item
}

Explanation

An object of the struct StackLinkedList is created named stack. It refers to a head node and has an int variable to keep track of the size of the stack.
The push function creates a new head node. It assigns it the int value that is passed in the parameter. In our case, we push three values separately into the stack.
The length function returns the number of elements in the stack.
The pop function first checks if the stack is empty. It raises an exception in that case. Otherwise, it makes the second node in the linked list the head node and deletes the first node. It also decrements the size variable by one.
The peek function returns the value of the head node of the linked list.
The print function iterates over each node and prints its value.

Time complexity

Let us examine the time complexity for each operation in a linked list-based stack:

Operation	Time Complexity
`IsEmpty`	$O(1)$
`Peek`	$O(1)$
`Size`	$O(1)$
`Push`	$O(1)$
`Pop`	$O(1)$
`Print`	$O(n)$

New on Educative

Learn to Code

Learn any Language as a beginner

Develop a human edge in an AI powered world and learn to code with AI from our beginner friendly catalog

🏆 Leaderboard

Daily Coding Challenge

Solve a new coding challenge every day and climb the leaderboard

Free Resources