Implement Queue/Stack with Linked List

labuladongOriginalAbout 1970 words

Prerequisite Knowledge

Before reading this article, you should first learn:

Basic Principles of Queues/Stacks

Implementing a Stack with a Linked List

Some readers may already know how to implement a queue and a stack using a linked list as the underlying data structure. It's quite simple, really; you can just directly use the API of a doubly linked list.

Note that I'm directly using Java's standard library LinkedList here. If you use our previously implemented MyLinkedList, it would work just as well.

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())

go 🤖

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

Tip

The above code essentially treats the tail of the doubly linked list as the top of the stack. The time complexity for adding or removing elements at the end of the doubly linked list is O(1), which meets the requirements.

Of course, you could also use the head of the doubly linked list as the top of the stack, as the time complexity for adding or removing elements at the head is also O(1). The implementation would be just as valid. You only need to make a few changes: addLast -> addFirst, removeLast -> removeFirst, getLast -> getFirst, and you're set.

Implementing a Queue with a Linked List

Similarly, implementing a queue with a linked list is just as straightforward. You can directly 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

go 🤖

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
    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

Hint

The code above essentially treats the tail of the doubly linked list as the end of the queue and the head as the front of the queue. The complexity of adding or removing elements at both the head and tail of a doubly linked list is O(1), meeting the requirements of the queue API.

Of course, you can also reverse this by using the head of the doubly linked list as the end of the queue and the tail as the front. Similar to stack implementation, you just need to change the way you call the list methods.

End of Article Reflection

Doubly linked lists are quite versatile; they can handle both queue and stack APIs effectively. But consider this: when implementing a queue with an array, might there be an issue?

The queue API requires adding elements at one end and removing them from the other. However, adding or removing elements from the head of an array has a time complexity of $O(n)$ . Is there a way to optimize this?

Think about it, and I will provide the answer in the next chapter.