Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

go

How to implement a stack using a linked list in Go

Hassaan Waqar

A Stack is an abstract data type for data storage. It follows the LIFO or last-in-first-out order for retrieving data. Elements that are added at the end are removed first.

The illustration below shows how a stack works:

How does a stack work?

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:

How does a linked list based stack work?

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)O(1)
Peek O(1)O(1)
Size O(1)O(1)
Push O(1)O(1)
Pop O(1)O(1)
Print O(n)O(n)

RELATED TAGS

go

CONTRIBUTOR

Hassaan Waqar
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring