{"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

<\/div> 
\/\/ Java program for linked-list implementation of queue  \/\/ A linked list (LL) node to store a queue entryclass QNode{    int key;    QNode next;         \/\/ constructor to create a new linked list node    public QNode(int key) {        this.key = key;        this.next = null;    }} \/\/ A class to represent a queue\/\/The queue, front stores the front node of LL and rear stores ths\/\/last node of LLclass Queue{    QNode front, rear;          public Queue() {        this.front = this.rear = null;    }          \/\/ Method to add an key to the queue.      void enqueue(int key)    {                 \/\/ Create a new LL node        QNode temp = new QNode(key);              \/\/ If queue is empty, then new node is front and rear both        if (this.rear == null)        {           this.front = this.rear = temp;           return;        }              \/\/ Add the new node at the end of queue and change rear        this.rear.next = temp;        this.rear = temp;    }          \/\/ Method to remove an key from queue.      QNode dequeue()    {        \/\/ If queue is empty, return NULL.        if (this.front == null)           return null;              \/\/ Store previous front and move front one node ahead        QNode temp = this.front;        this.front = this.front.next;              \/\/ If front becomes NULL, then change rear also as NULL        if (this.front == null)           this.rear = null;        return temp;    }}     \/\/ Driver classpublic class Test{    public static void main(String[] args)     {        Queue q=new Queue();        q.enqueue(10);        q.enqueue(20);        q.dequeue();        q.dequeue();        q.enqueue(30);        q.enqueue(40);        q.enqueue(50);                 System.out.println("Dequeued item is "+ q.dequeue().key);    }}<\/code><\/pre> <\/div>\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=”banner”]\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}]}}