In the previous post, we introduced Queue and discussed array implementation. In this post, linked list implementation is discussed. The following two main operations must be implemented efficiently.

In a Queue data structure, we maintain two pointers, front and rear. The front points the first item of queue and rear points to last item.

enQueue() This operation adds a new node after rear and moves rear to the next node.

deQueue() This operation removes the front node and moves front to the next node.

Java programming

[pastacode lang=”java” manual=”%2F%2F%20Java%20program%20for%20linked-list%20implementation%20of%20queue%0A%20%20%0A%2F%2F%20A%20linked%20list%20(LL)%20node%20to%20store%20a%20queue%20entry%0Aclass%20QNode%0A%7B%0A%20%20%20%20int%20key%3B%0A%20%20%20%20QNode%20next%3B%0A%20%20%20%20%20%0A%20%20%20%20%2F%2F%20constructor%20to%20create%20a%20new%20linked%20list%20node%0A%20%20%20%20public%20QNode(int%20key)%20%7B%0A%20%20%20%20%20%20%20%20this.key%20%3D%20key%3B%0A%20%20%20%20%20%20%20%20this.next%20%3D%20null%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F%2F%20A%20class%20to%20represent%20a%20queue%0A%2F%2FThe%20queue%2C%20front%20stores%20the%20front%20node%20of%20LL%20and%20rear%20stores%20ths%0A%2F%2Flast%20node%20of%20LL%0Aclass%20Queue%0A%7B%0A%20%20%20%20QNode%20front%2C%20rear%3B%0A%20%20%20%20%20%20%0A%20%20%20%20public%20Queue()%20%7B%0A%20%20%20%20%20%20%20%20this.front%20%3D%20this.rear%20%3D%20null%3B%0A%20%20%20%20%7D%0A%20%20%20%20%20%20%0A%20%20%20%20%2F%2F%20Method%20to%20add%20an%20key%20to%20the%20queue.%20%20%0A%20%20%20%20void%20enqueue(int%20key)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Create%20a%20new%20LL%20node%0A%20%20%20%20%20%20%20%20QNode%20temp%20%3D%20new%20QNode(key)%3B%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20queue%20is%20empty%2C%20then%20new%20node%20is%20front%20and%20rear%20both%0A%20%20%20%20%20%20%20%20if%20(this.rear%20%3D%3D%20null)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20this.front%20%3D%20this.rear%20%3D%20temp%3B%0A%20%20%20%20%20%20%20%20%20%20%20return%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Add%20the%20new%20node%20at%20the%20end%20of%20queue%20and%20change%20rear%0A%20%20%20%20%20%20%20%20this.rear.next%20%3D%20temp%3B%0A%20%20%20%20%20%20%20%20this.rear%20%3D%20temp%3B%0A%20%20%20%20%7D%0A%20%20%20%20%20%20%0A%20%20%20%20%2F%2F%20Method%20to%20remove%20an%20key%20from%20queue.%20%20%0A%20%20%20%20QNode%20dequeue()%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20queue%20is%20empty%2C%20return%20NULL.%0A%20%20%20%20%20%20%20%20if%20(this.front%20%3D%3D%20null)%0A%20%20%20%20%20%20%20%20%20%20%20return%20null%3B%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Store%20previous%20front%20and%20move%20front%20one%20node%20ahead%0A%20%20%20%20%20%20%20%20QNode%20temp%20%3D%20this.front%3B%0A%20%20%20%20%20%20%20%20this.front%20%3D%20this.front.next%3B%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20front%20becomes%20NULL%2C%20then%20change%20rear%20also%20as%20NULL%0A%20%20%20%20%20%20%20%20if%20(this.front%20%3D%3D%20null)%0A%20%20%20%20%20%20%20%20%20%20%20this.rear%20%3D%20null%3B%0A%20%20%20%20%20%20%20%20return%20temp%3B%0A%20%20%20%20%7D%0A%7D%0A%20%20%0A%20%20%20%0A%2F%2F%20Driver%20class%0Apublic%20class%20Test%0A%7B%0A%20%20%20%20public%20static%20void%20main(String%5B%5D%20args)%20%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20Queue%20q%3Dnew%20Queue()%3B%0A%20%20%20%20%20%20%20%20q.enqueue(10)%3B%0A%20%20%20%20%20%20%20%20q.enqueue(20)%3B%0A%20%20%20%20%20%20%20%20q.dequeue()%3B%0A%20%20%20%20%20%20%20%20q.dequeue()%3B%0A%20%20%20%20%20%20%20%20q.enqueue(30)%3B%0A%20%20%20%20%20%20%20%20q.enqueue(40)%3B%0A%20%20%20%20%20%20%20%20q.enqueue(50)%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20System.out.println(%22Dequeued%20item%20is%20%22%2B%20q.dequeue().key)%3B%0A%20%20%20%20%7D%0A%7D%0A” message=”” highlight=”” provider=”manual”/]

 Output:

Dequeued item is 30

Time Complexity: Time complexity of both operations enqueue() and dequeue() is O(1) as we only change few pointers in both operations. There is no loop in any of the operations.

[ad type=”banner”]

Categorized in: