patternjavaModerate
Stack implementation using a linked list
Viewed 0 times
stackusingimplementationlistlinked
Problem
To understand the concept, I implemented the stack operations using a linked list. Please review the code and tell me your suggestions.
Node.java
LinkList.java
LinkListStack.java
LinkListStackDemo.java
Node.java
public class Node {
public int data;
public Node next;
public Node(int data) {
this.data = data;
}
public void displayNode() {
System.out.print(data);
System.out.print(" ");
}
}LinkList.java
public class LinkList {
private Node first = null;
public void insertFirst(int data) {
Node n = new Node(data);
n.next = first;
first = n;
}
public Node deleteFirst() {
Node temp = first;
first = first.next;
return temp;
}
public void displayList() {
Node current = first;
while (current != null) {
current.displayNode();
current = current.next;
}
}
public boolean isEmpty() {
return (first == null);
}
}LinkListStack.java
public class LinkListStack {
LinkList li = new LinkList();
public void push(int data) {
li.insertFirst(data);
}
public void pop() {
while(!li.isEmpty()){
li.deleteFirst();
}
}
public void displayStack() {
System.out.println(" ");
li.displayList();
}
}LinkListStackDemo.java
public class LinkListStackDemo {
public static void main(String[] args) {
LinkListStack st = new LinkListStack();
st.push(50);
st.push(70);
st.push(190);
st.displayStack();
st.pop();
st.displayStack();
}
}Solution
Time complexity
The time complexity of push and pop operations should be \$O(1)\$, and so it is in your case too. It doesn't matter how many elements you have, these operations should take constant time. (UPDATE: you've edited your original post, and made
Avoid printing to
Instead of the
Generalize
Why limit the stack, linked list, node elements to
The question is tagged "beginner", so I understand you might not be familiar with generics just yet. In that case, see this official tutorial. Or perhaps you can also learn from my example implementation further down.
Add an
Your linked list has an
Reinventing the wheel
When reinventing the wheel (here, linked list), it's good to mimic what exists. For example,
Access modifiers and encapsulation
As @rolfl pointed out,
Also, the members of
Naming
You use poor names in many places.
Suggested implementation
Unit tests
The time complexity of push and pop operations should be \$O(1)\$, and so it is in your case too. It doesn't matter how many elements you have, these operations should take constant time. (UPDATE: you've edited your original post, and made
pop wipe out the entire stack. That's not normal! Normally, the pop operation on a stack should return the most recently added value. That's \$O(1)\$ time.)Avoid printing to
stdoutInstead of the
display* methods that print to stdout, it would be better to override toString. That way your implementation would be more testable.Generalize
Why limit the stack, linked list, node elements to
int type? It would be trivially easy to rewrite to make it work with any type T.The question is tagged "beginner", so I understand you might not be familiar with generics just yet. In that case, see this official tutorial. Or perhaps you can also learn from my example implementation further down.
Add an
isEmpty method for the stackYour linked list has an
isEmpty method but the stack doesn't. It would be good to have such method for the stack too.Reinventing the wheel
When reinventing the wheel (here, linked list), it's good to mimic what exists. For example,
java.util.LinkedList uses the method names addFirst and removeFirst, instead of insertFirst and deleteFirst. It's good to follow the example.Access modifiers and encapsulation
As @rolfl pointed out,
Node should not be exposed to the outside. Users of the stack should not have to know its inner workings.Also, the members of
Node should be private, and the data and next fields can be final. Similarly in the stack, the linked list member should be private.Naming
You use poor names in many places.
- Instead of
nfor the new node when replacing the first item of a linked list,newFirstwould be more intuitive
- Instead of
tempfor the old first item removed from a linked list,oldFirstwould be more intuitive
- Instead of
lifor the linked list in the stack,linkedListwould be more intuitive
Suggested implementation
class LinkList {
private static class Node {
private final T data;
private final Node next;
public Node(T data) {
this.data = data;
}
@Override
public String toString() {
return data.toString();
}
}
private Node first = null;
public void addFirst(T data) {
Node newFirst = new Node(data);
newFirst.next = first;
first = newFirst;
}
public T removeFirst() {
Node oldFirst = first;
first = first.next;
return oldFirst.data;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
Node current = first;
while (current != null) {
builder.append(current).append(" ");
current = current.next;
}
return builder.toString();
}
public boolean isEmpty() {
return first == null;
}
}
class LinkListStack {
private final LinkList linkedList = new LinkList<>();
public void push(T data) {
linkedList.addFirst(data);
}
public T pop() {
return linkedList.removeFirst();
}
public boolean isEmpty() {
return linkedList.isEmpty();
}
@Override
public String toString() {
return linkedList.toString();
}
}Unit tests
@Test
public void testPushAndPop() {
LinkListStack st = new LinkListStack<>();
st.push(50);
st.push(70);
st.push(190);
assertEquals("190 70 50", st.toString());
assertEquals(190, (int) st.pop());
assertEquals("70 50", st.toString());
}
@Test
public void testPopUntilEmpty() {
List values = Arrays.asList(50, 70, 190, 20);
LinkListStack st = new LinkListStack<>();
assertTrue(st.isEmpty());
for (Integer value : values) {
st.push(value);
}
assertFalse(st.isEmpty());
for (int i = values.size(); i > 0; --i) {
assertEquals(values.get(i - 1), st.pop());
}
assertTrue(st.isEmpty());
}Code Snippets
class LinkList<T> {
private static class Node<T> {
private final T data;
private final Node<T> next;
public Node(T data) {
this.data = data;
}
@Override
public String toString() {
return data.toString();
}
}
private Node<T> first = null;
public void addFirst(T data) {
Node<T> newFirst = new Node<T>(data);
newFirst.next = first;
first = newFirst;
}
public T removeFirst() {
Node<T> oldFirst = first;
first = first.next;
return oldFirst.data;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
Node current = first;
while (current != null) {
builder.append(current).append(" ");
current = current.next;
}
return builder.toString();
}
public boolean isEmpty() {
return first == null;
}
}
class LinkListStack<T> {
private final LinkList<T> linkedList = new LinkList<>();
public void push(T data) {
linkedList.addFirst(data);
}
public T pop() {
return linkedList.removeFirst();
}
public boolean isEmpty() {
return linkedList.isEmpty();
}
@Override
public String toString() {
return linkedList.toString();
}
}@Test
public void testPushAndPop() {
LinkListStack<Integer> st = new LinkListStack<>();
st.push(50);
st.push(70);
st.push(190);
assertEquals("190 70 50", st.toString());
assertEquals(190, (int) st.pop());
assertEquals("70 50", st.toString());
}
@Test
public void testPopUntilEmpty() {
List<Integer> values = Arrays.asList(50, 70, 190, 20);
LinkListStack<Integer> st = new LinkListStack<>();
assertTrue(st.isEmpty());
for (Integer value : values) {
st.push(value);
}
assertFalse(st.isEmpty());
for (int i = values.size(); i > 0; --i) {
assertEquals(values.get(i - 1), st.pop());
}
assertTrue(st.isEmpty());
}Context
StackExchange Code Review Q#62710, answer score: 18
Revisions (0)
No revisions yet.