Difference between array queue and linked list queue

WBOY
Release: 2023-09-03 11:05:05
forward
667 people have browsed it

introduce

A queue is a linear data structure that inserts and removes queue elements in a specific order. We can implement queues in C by using arrays and linked lists. Both queue implementations have their own advantages and uses. In this tutorial, we will differentiate between array-based queues and linked-list-based queues.

What is a queue?

A queue is a series of elements that use the FIFO (first in, first out) principle for element insertion and deletion. Queues in computer science are similar to queues in real life, the first person to enter the queue will be removed first.

The process of removing queue data is called deQueue. The operation of adding data to the queue is called enQueue.

The queue has two points -

  • After- Elements in the queue are inserted from here.

  • Front- The element in the queue will be removed from here.

We can implement queues in two ways -

  • Array-based queue

  • List-based queue or linked list queue

Array-based queue

Queues implemented using arrays are called array-based queues. It uses two pointers: Front and Rear, which represent the deletion point and insertion point in the Queue respectively.

In this implementation, the array size is predefined before data is inserted. This is the simplest way to insert and delete queue data.

Difference between array queue and linked list queue

List-based queue

In list-based queues or linked-list-based queues, linked lists are used for queue implementation. Each queue node consists of two parts: one part is used to store data, and the other part is the link part or the memory part.

Each queue element is connected to the memory of the next queue element. There are two pointers in a list-based queue -

  • Previous pointer- Memory representing the last queue element.

  • Back pointer- The memory representing the first element of the queue.

Difference between array queue and linked list queue

The difference between array queue and linked list queue

The Chinese translation of is:

S.No

Array-based queue

Queue based on linked list

1

Complexity

It is easy to implement and perform operations.

It is not easy to implement.

2

Search process

It helps to search easily and quickly.

Slow speed and difficult search operation.

3

Queue size

Define the queue size during initialization.

No need to define the queue size when initializing the queue.

4

Insertion and deletion operations

It is difficult to insert data at the beginning, but easy to insert data at the end of the queue.

It provides simple data insertion at both ends of the queue.

5

Access data

Random data access.

It provides sequential access to queue elements.

6

Queue size adjustment

Changing the queue size is difficult.

It's easy to adjust the queue size.

7

Memory usage

It consumes less memory.

It consumes more memory.

8

advantage

  • Faster and easier to implement.

  • It consumes less memory.

  • Randomly access elements.

  • Inserting and removing queue elements is easy.

  • Easily adjust the queue size without declaring the queue size in advance.

9

shortcoming

  • Resizing the queue is difficult.

  • Declare the queue size in advance.

  • The processing speed is very slow.

  • The structure is complex and consumes a lot of memory.

Use array-based queues and linked-list-based queues

If your queue has a fixed size and there is no need to change the queue size, you can implement the queue using an array. Array-based queues are also useful when searching is fast and consumes less memory.

Linked list-based queue implementations are useful when the queue size is dynamic and queue elements are inserted and deleted multiple times. Although it consumes more memory, it is suitable for large-scale applications

in conclusion

Using array-based queues and linked-list-based queues depends on requirements. In large-scale applications, array-based queues are unsuccessful and linked-list queues are used instead.

Array-based queues use less memory, but waste a lot of memory because after inserting elements in the backend, there will be some unused memory left before the first element.

The above is the detailed content of Difference between array queue and linked list queue. For more information, please follow other related articles on the PHP Chinese website!

source:tutorialspoint.com
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template
About us Disclaimer Sitemap
php.cn:Public welfare online PHP training,Help PHP learners grow quickly!