Prerequisite:
If you have not covered the following topics, please study below topics before starting this tutorial.
Linked list and Stack:
Stack works on the concept of LIFO(Last In First Out). It means the item which is added at last to the stack is processed first. It means item addition(PUSH operation) and item processing(POP operation) takes place at same place. This position in the stack is called top pointer.
In Linked list item can be added to any place using the head pointer which points to the first item in the linked list.
By combining both the definitions we conclude that we can fix head pointer in the linked list where both addition and processing of items will be performed. In this case the head pointer in the linked list will behave like the top pointer of the stack.
Strategy section will explain how to implement the stack using linked list.
Strategy
As mentioned above we will use head pointer of the linked list as the top pointer of the stack. Below are the details of implementation of stack using linked list.
1. LinkedListNode - This class will only define structure of linked list node.
2. StackUsingLinkedList - This class will implement all necessary logic to operate stack using Linked ListNode as storage unit. Below are the basic operations/variables to implement the stack.
a. head pointer - This is the variable which always points to the first node of the linked list.
b. push(item)-This operation adds a element to the start of the linked list pointed by head pointer.
c. pop()-This operation fetches and removes an item from the linked list pointed by head pointer.
d. peek()-This operation fetches an item from the linked list pointed by head pointer.
d. getSize()-This operation will return the number of elements in the linked list.
e. size - This variable will be used to track size of the stack.
f. printLinkedList() - This is the optional method to see the content of the stack.
Below is the class diagram for the implementation of the stack using linked list mentioned above:
Here we are going to write algorithms for all the operations of the linked list mentioned in the above diagram.
push( item )- This operation adds the element in the linked list at the position pointed by head pointer. Since head pointer is known and accessed in O(1) time, the time complexity of this operation is O(1).
Below is the implementation of push(item) operation.
push(item)
{
1. newNode=new LinkedListNode(item)
2. newNode.next=head
3. head=newNode
4. size++
}
pop( )- This operation fetches and removes the last added element from the linked list pointed by the head pointer. Since head pointer is known and accessed in O(1) time, the time complexity of this operation is O(1).
Below is the the implementation of pop() operation.
pop():item
{
1. if head == null
2. Error("No item present to be popped");
3. item=head.data
4. head=head.next
5. size--
6. return item
}
peek( )- This operation fetches the last added element from the linked list pointed by the head pointer. Since head pointer is known and accessed in O(1) time, the time complexity of this operation is O(1).
Below is the the implementation of peek() operation.
peek():item
{
1. if head == null
2. Error("No item present to be popped");
3. item=head.data
4. return item
}
getSize() = This operation returns the size of linked list using size variable. Below is the implementation of getSize() operation.
getSize():Integer
{
return size;
}
printLinkedList()- This operation prints all the elements of the linked list by traversing the linked list using head pointer. Since entire linked list is traversed here, time complexity of this operation is O(n)
printLinkedList()
{
1. if head == null
2. Error("No item present in the linked List");
3. tempHead=head
4. while(tempHead!=null)
5. print(tempHead.data)
6. tempHead=temHead.next
}
Below is the java code implementation of the above discussed algorithms
public class StackLinkedListTest {
/**
* @param args
* @throws Exception
*/
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
StackUsingLinkedList<Integer> linkedList=new StackUsingLinkedList<Integer>();
linkedList.push(1);
linkedList.push(2);
linkedList.push(5);
linkedList.push(6);
linkedList.push(11);
linkedList.printLinkedList();
System.out.println("Size of the stack is: "+linkedList.getSize());
System.out.println("Peek item is: "+linkedList.peek());
System.out.println("Popped item is: "+linkedList.pop());
System.out.println("Popped item is: "+linkedList.pop());
System.out.println("StackUsingLinkedList after deleting two elements");
linkedList.printLinkedList();
System.out.println("Peek item is: "+linkedList.peek());
System.out.println("Size of the stack is: "+linkedList.getSize());
}
}
class LinkedListNode<T>
{
public T data;
public LinkedListNode next;
public LinkedListNode(T item)
{
data=item;
next=null;
}
}
class StackUsingLinkedList<T>
{
private LinkedListNode head;
private int size=0;
public void push(T item)
{
LinkedListNode newNode=new LinkedListNode(item);
newNode.next=head;
head=newNode;
size++;
}
public T pop() throws Exception
{
if(head==null)
{
throw new Exception("Linked List is empty");
}
T item=(T) head.data;
head=head.next;
size--;
return item;
}
public T peek() throws Exception
{
if(head==null)
{
throw new Exception("Linked List is empty");
}
T item=(T) head.data;
return item;
}
public int getSize()
{
return size;
}
public void printLinkedList() throws Exception
{
if(head==null)
{
throw new Exception("Linked List is empty");
}
LinkedListNode tempHead=head;
System.out.println("============StackUsingLinkedList printing - starts===========");
while(tempHead!=null)
{
System.out.print(tempHead.data+"\t");
tempHead=tempHead.next;
}
System.out.println("");
System.out.println("============StackUsingLinkedList printing - ends===========");
}
}