Implementing a queue with a single linked list where enqueue and dequeue operation take O(1).

Implementing a queue with a single linked list where enqueue and dequeue operation take O(1).

Keep the address of the last node in the list in a variable “last”. Now for enqueue operation, you could insert a new node at the end of the list, in O(1), by changing the “last” node to link to the new node, and then updating the variable “last” to point to this new node. For dequeue operation, just remove a node from the front of the list, also in O(1). Note that you would want to keep a symbolic “head” node at the beginning of your list, to ensure that the list in never empty (if the list is empty, “last” would be a dangling pointer, and you may run into a runtime error when trying to insert a new node).

Update: Here is some pseudocode, and here is some C++ code for this.

1 Like

Please write pseudocode.

The Idea is same as said by drajingo…
here is implementation

// Because You look Gorgeous in Black.... :D

#include <stdio.h>
#include <stdlib.h>

struct Node
{
	int data;
	struct Node *next;
};

struct Node * ad[1000000];
int size = 0;

void enQueue(struct Node **head_ref, struct Node **tail_ref, int data)
{
	struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
	if(!newNode)
	{
		printf("Memory Error!\n");
		return;
	}
	
	newNode->data = data;
	newNode->next = NULL;

	// Empty queue
	if(*head_ref == NULL)
	{
		*head_ref = *tail_ref = newNode;
		ad[size] = newNode;
		size++;
		return;
	}

	(*tail_ref)->next = newNode;
	*tail_ref = newNode;
	ad[size] = newNode;
	size++;
}

void deQueue(struct Node **head_ref, struct Node **tail_ref)
{
	// empty queue
	if(*head_ref == NULL)
	{
		printf("Empty Queue\n");
		return;
	}

	// if only one element if queue
	if(*head_ref == *tail_ref)
	{
		printf("Element Dequeued %d\n", (*tail_ref)->data);
		free(*tail_ref);
		*head_ref = *tail_ref = NULL;
		size--;
		return;
	}

	printf("Element Dequeued %d\n", (*tail_ref)->data);
	struct Node *temp = *tail_ref;
	size--;
	*tail_ref = ad[size-1];
	free(temp);
}

int main()
{
	int choice = 1;
	struct Node *head = NULL;
	struct Node *tail = NULL;
	while(1)
	{
		printf("\nEnter Choice\n 1. Enqueue\n 2. Dequeue\n 3. Exit\n\n");
		scanf("%d", &choice);

		if(choice == 1)
		{
			int data;
			printf("Enter Data to Enque\n");
			scanf("%d", &data);
			enQueue(&head, &tail, data);
		}
		else if(choice == 2)
		{
			deQueue(&head, &tail);
		}
		else if(choice == 3)
		{
			break;
		}
		else
		{
			printf("Wrong Choice.. \nPlease Try again\n\n");
		}
	}
	return 0;
}

I tested it but still bugs may creep in (if found please correct me… )

1 Like