Implement Queue/Stack with Linked List

Prerequisites

Before reading this article, you need to learn:

Implementing a Stack with a Linked List

Some of you may already know how to use a linked list as the base data structure for implementing a queue or a stack. It is very simple — you can just use the API of the standard doubly linked list.

Here I use the standard library's linked list container. If you use the MyLinkedList we wrote before, the logic is the same.

java

import java.util.LinkedList;

// Implement a stack using linked list as the underlying data structure
public class MyLinkedStack<E> {
    private final LinkedList<E> list = new LinkedList<>();

    // Add an element to the top of the stack, time complexity O(1)
    public void push(E e) {
        list.addLast(e);
    }

    // Pop an element from the top of the stack, time complexity O(1)
    public E pop() {
        return list.removeLast();
    }

    // Look at the top element of the stack, time complexity O(1)
    public E peek() {
        return list.getLast();
    }

    // Return the number of elements in the stack, time complexity O(1)
    public int size() {
        return list.size();
    }

    public static void main(String[] args) {
        MyLinkedStack<Integer> stack = new MyLinkedStack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.println(stack.peek()); // 3
        System.out.println(stack.pop()); // 3
        System.out.println(stack.peek()); // 2
    }
}

cpp

// Implement a stack using linked list as the underlying data structure
#include <list>
#include <iostream>

template<typename E>
class MyLinkedStack {
private:
    std::list<E> list;

public:
    // Add an element to the top of the stack, time complexity O(1)
    void push(const E &e) {
        list.push_back(e);
    }

    // Pop an element from the top of the stack, time complexity O(1)
    E pop() {
        E value = list.back();
        list.pop_back();
        return value;
    }

    // Look at the element at the top of the stack, time complexity O(1)
    E peek() const {
        return list.back();
    }

    // Return the number of elements in the stack, time complexity O(1)
    int size() const {
        return list.size();
    }
};

int main() {
    MyLinkedStack<int> stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    while (stack.size() > 0) {
        std::cout << stack.pop() << std::endl;
    }
    return 0;
}

python

from collections import deque

# Implement stack using linked list as underlying data structure
# Python's deque is a double-ended linked list
class MyLinkedStack:
    def __init__(self):
        self.list = deque()

    # Add element to the top of the stack, time complexity O(1)
    def push(self, e):
        self.list.append(e)

    # Pop element from the top of the stack, time complexity O(1)
    def pop(self):
        return self.list.pop()

    # Peek at the top element of the stack, time complexity O(1)
    def peek(self):
        return self.list[-1]

    # Return the number of elements in the stack, time complexity O(1)
    def size(self):
        return len(self.list)


if __name__ == "__main__":
    stack = MyLinkedStack()
    stack.push(1)
    stack.push(2)
    stack.push(3)
    print(stack.pop())
    print(stack.peek())
    print(stack.size())

import "container/list"

// use linked list as the underlying data structure to implement a stack
type MyLinkedStack struct {
    list *list.List
}

func NewMyLinkedStack() *MyLinkedStack {
    return &MyLinkedStack{list: list.New()}
}

// push an element to the top of the stack, time complexity O(1)
func (s *MyLinkedStack) Push(e interface{}) {
    s.list.PushBack(e)
}

// pop an element from the top of the stack, time complexity O(1)
func (s *MyLinkedStack) Pop() interface{} {
    element := s.list.Back()
    if element != nil {
        s.list.Remove(element)
        return element.Value
    }
    return nil
}

// peek the top element of the stack, time complexity O(1)
func (s *MyLinkedStack) Peek() interface{} {
    element := s.list.Back()
    if element != nil {
        return element.Value
    }
    return nil
}

// return the number of elements in the stack, time complexity O(1)
func (s *MyLinkedStack) Size() int {
    return s.list.Len()
}

// test
func main() {
    stack := NewMyLinkedStack()
    stack.Push(1)
    stack.Push(2)
    stack.Push(3)
    fmt.Println(stack.Pop()) // 3
    fmt.Println(stack.Pop()) // 2
    fmt.Println(stack.Peek()) // 1
}

javascript

// use linked list as the underlying data structure to implement stack
// JavaScript does not have a built-in doubly linked list, so an array is used here instead
// However, you can refer to the previous implementation of a
// doubly linked list and implement your own JS doubly linked list
class MyLinkedStack {
    constructor() {
        this.list = [];
    }

    // push an element to the top of the stack, time complexity O(1)
    push(e) {
        this.list.push(e);
    }

    // pop an element from the top of the stack, time complexity O(1)
    pop() {
        return this.list.pop();
    }

    // peek at the top element of the stack, time complexity O(1)
    peek() {
        return this.list[this.list.length - 1];
    }

    // return the number of elements in the stack, time complexity O(1)
    size() {
        return this.list.length;
    }
}

// test
const stack = new MyLinkedStack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop()); // 3
console.log(stack.pop()); // 2
console.log(stack.peek()); // 1

Note

The code above uses the tail of the doubly linked list as the top of the stack. Adding or removing elements at the tail (stack top) has time complexity O(1), which meets the requirement.

Of course, you can also use the head of the doubly linked list as the top of the stack. Since adding or removing elements at the head is also O(1), this method works too. You only need to make a few changes, such as changing addLast to addFirst, removeLast to removeFirst, and getLast to getFirst.

Implementing a Queue with a Linked List

Similarly, you can use a linked list to implement a queue — just use the API of the doubly linked list:

java

import java.util.LinkedList;

// use LinkedList as the underlying data structure to implement the queue
public class MyLinkedQueue<E> {
    private final LinkedList<E> list = new LinkedList<>();

    // insert element to the end of the queue, time complexity O(1)
    public void push(E e) {
        list.addLast(e);
    }

    // remove element from the front of the queue, time complexity O(1)
    public E pop() {
        return list.removeFirst();
    }

    // view the front element of the queue, time complexity O(1)
    public E peek() {
        return list.getFirst();
    }

    // return the number of elements in the queue, time complexity O(1)
    public int size() {
        return list.size();
    }

    public static void main(String[] args) {
        MyLinkedQueue<Integer> queue = new MyLinkedQueue<>();
        queue.push(1);
        queue.push(2);
        queue.push(3);

        System.out.println(queue.peek()); // 1
        System.out.println(queue.pop()); // 1
        System.out.println(queue.pop()); // 2
        System.out.println(queue.peek()); // 3
    }
}

cpp

// Implement a queue using a linked list as the underlying data structure
#include <iostream>
#include <list>


template<typename E>
class MyLinkedQueue {
private:
    std::list<E> list;

public:
    // Insert an element at the end of the queue, time complexity O(1)
    void push(const E &e) {
        list.push_back(e);
    }

    // Remove an element from the front of the queue, time complexity O(1)
    E pop() {
        E front = list.front();
        list.pop_front();
        return front;
    }

    // View the front element of the queue, time complexity O(1)
    E peek() {
        return list.front();
    }

    // Return the number of elements in the queue, time complexity O(1)
    int size() {
        return list.size();
    }
};

int main() {
    MyLinkedQueue<int> queue;
    queue.push(1);
    queue.push(2);
    queue.push(3);

    std::cout << queue.peek() << std::endl; // 1
    std::cout << queue.pop() << std::endl; // 1
    std::cout << queue.pop() << std::endl; // 2
    std::cout << queue.peek() << std::endl; // 3

    return 0;
}

python

# deque is a doubly linked list in Python
from collections import deque

# use a linked list as the underlying data structure to implement the queue
# Python's deque is a doubly linked list
class MyLinkedQueue:
    def __init__(self):
        self.list = deque()

    # insert an element at the end of the queue, time complexity O(1)
    def push(self, e):
        self.list.append(e)

    # remove an element from the head of the queue, time complexity O(1)
    def pop(self):
        return self.list.popleft()

    # view the element at the head of the queue, time complexity O(1)
    def peek(self):
        return self.list[0]

    # return the number of elements in the queue, time complexity O(1)
    def size(self):
        return len(self.list)

if __name__ == "__main__":
    queue = MyLinkedQueue()
    queue.push(1)
    queue.push(2)
    queue.push(3)
    print(queue.peek()) # 1
    print(queue.pop()) # 1
    print(queue.pop()) # 2
    print(queue.peek()) # 3

import (
	"container/list"
	"fmt"
)

// Implement queue using a linked list as the underlying data structure
type MyLinkedQueue struct {
	list *list.List
}

// Constructor
func NewMyLinkedQueue() *MyLinkedQueue {
	return &MyLinkedQueue{list: list.New()}
}

// Insert an element at the end of the queue, time complexity O(1)
func (q *MyLinkedQueue) Push(e interface{}) {
	q.list.PushBack(e)
}

// Remove an element from the front of the queue, time complexity O(1)
func (q *MyLinkedQueue) Pop() interface{} {
	front := q.list.Front()
	if front != nil {
		return q.list.Remove(front)
	}
	return nil
}

// View the front element, time complexity O(1)
func (q *MyLinkedQueue) Peek() interface{} {
	front := q.list.Front()
	if front != nil {
		return front.Value
	}
	return nil
}

// Return the number of elements in the queue, time complexity O(1)
func (q *MyLinkedQueue) Size() int {
	return q.list.Len()
}


func main() {
	queue := NewMyLinkedQueue()
	queue.Push(1)
	queue.Push(2)
	queue.Push(3)
	fmt.Println(queue.Peek()) // 1
	fmt.Println(queue.Pop())  // 1
	fmt.Println(queue.Pop())  // 2
	fmt.Println(queue.Peek()) // 3
}

javascript

// Implement a queue using a linked list as the underlying data structure
// JavaScript does not have a built-in doubly linked list, so we use an array here
// However, note that the time complexity of the shift() method is O(n)
// if you implement your own JS doubly linked list,
// you can achieve O(1) complexity for the queue
class MyLinkedQueue {
    constructor() {
        this.list = [];
    }

    // Insert an element at the end of the queue, time complexity O(1)
    push(e) {
        this.list.push(e);
    }

    // Remove an element from the front of the queue, time complexity should be O(1)
    // However, since we are using a JavaScript array as the
    // underlying data structure, the actual time complexity is O(n)
    pop() {
        return this.list.shift();
    }

    // Peek at the front element of the queue, time complexity O(1)
    peek() {
        return this.list[0];
    }

    // Return the number of elements in the queue, time complexity O(1)
    size() {
        return this.list.length;
    }
}

// test
const queue = new MyLinkedQueue();
queue.push(1);
queue.push(2);
queue.push(3);
console.log(queue.peek()); // 1
console.log(queue.pop()); // 1
console.log(queue.pop()); // 2
console.log(queue.peek()); // 3

Note

The code above uses the tail of the doubly linked list as the queue tail, and the head as the queue head. Adding or removing elements at either end has time complexity O(1), which matches the requirements of a queue.

You can also do the opposite: use the head as the queue tail and the tail as the queue head. Just like with the stack implementation, you only need to change how you call the list methods.