Skip to content

Instantly share code, notes, and snippets.

@sricharankrishnan
Created April 12, 2023 04:50
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save sricharankrishnan/30a4276c2cd159c0f151dce8b162c5e7 to your computer and use it in GitHub Desktop.
Save sricharankrishnan/30a4276c2cd159c0f151dce8b162c5e7 to your computer and use it in GitHub Desktop.
A stack (linked list style) data structure implementation done in java along with respective time complexities for each method
/**
* Linked List Stack Implementation
* public void push(E value): O(1)
* public Node peek(): O(1)
* public void pop(): O(1)
*/
import java.util.*;
public class LinkedListStack<E> {
private class Node<E> {
public E value;
public Node next;
public Node(E value) {
this.value = value;
this.next = null;
}
public Node(E value, Node next) {
this.value = value;
this.next = next;
}
public String toString() {
return "[Node: " + this.value + "]";
}
}
public Node head;
public int size;
public LinkedListStack() {
this.head = null;
this.size = 0;
}
/* O(1) */
public void push(E value) {
if (!Objects.isNull(value)) {
Node node = new Node(value, this.head);
this.head = node;
++this.size;
}
}
/* O(1) */
public Node peek() {
return (this.isEmpty()) ? null : this.head;
}
/* O(1) */
public void pop() {
if (!this.isEmpty()) {
this.head = this.head.next;
--this.size;
}
}
public boolean isEmpty() {
return this.size() == 0;
}
public int size() {
return this.size;
}
public String toString() {
String string = "";
if (!this.isEmpty()) {
Node node = null;
for (int i = 0; i < this.size(); ++i) {
node = (i == 0) ? this.head : node.next;
string += (i == this.size() - 1) ? node : node + " --> ";
}
}
return string;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment