{"id":26920,"date":"2017-12-26T22:07:24","date_gmt":"2017-12-26T16:37:24","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26920"},"modified":"2017-12-26T22:07:24","modified_gmt":"2017-12-26T16:37:24","slug":"java-programming-queue-data-structure-linked-list-implementation","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-programming-queue-data-structure-linked-list-implementation\/","title":{"rendered":"Java Programming-Queue -Data Structure-Linked List Implementation"},"content":{"rendered":"

In the previous post<\/a>, we introduced Queue and discussed array implementation. <\/span>In this post, linked list implementation is discussed. The following two main operations must be implemented efficiently.<\/p>\n

In a Queue data structure, we maintain two pointers, front<\/em> and rear<\/em>. The front<\/em> points the first item of queue and rear<\/em> points to last item.<\/p>\n

enQueue()<\/strong> This operation adds a new node after rear <\/em>and moves rear<\/em> to the next node.<\/p>\n

deQueue()<\/strong> This operation removes the front node and moves front<\/em> to the next node.<\/p>\n

Java programming<\/strong><\/p>\n[pastacode lang=\u201djava\u201d manual=\u201d%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\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

\u00a0<\/strong>Output:<\/p>\n

Dequeued item is 30<\/pre>\n
Time Complexity:<\/strong> 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.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
Java programming queue data structure linked list implementation In the previous post, we introduced Queue and discussed array implementation<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[73012,79476],"tags":[80342,80340,80330,80339,80331,80327,80334,80332,80333,80341,80335,80338,80336,80337,80328,80329],"class_list":["post-26920","post","type-post","status-publish","format-standard","hentry","category-data-structures","category-linked-list","tag-circular-queue-implementation-in-c","tag-circular-queue-using-linked-list-in-c","tag-doubly-linked-list-implementation-in-java","tag-implement-queue-using-linked-list-geeksforgeeks","tag-linked-list-data-structure-in-java","tag-linked-list-implementation-c","tag-linked-list-implementation-in-c","tag-linked-list-implementation-in-java-source-code","tag-linked-list-program-in-java","tag-linked-queue-in-data-structure","tag-queue-implementation-using-array","tag-queue-using-linked-list-algorithm","tag-queue-using-linked-list-c","tag-queue-using-linked-list-java","tag-singly-linked-list-implementation-in-java","tag-singly-linked-list-java-tutorial"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26920","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26920"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26920\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26920"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26920"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26920"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}