Queue and Linked Lists

Queue and Linked Lists

is an n ordered list in which all insertions take place at one end, the rear, while all deletions take place at the other end, the front.  It is an example of a linear data structure.  

A queue is an n ordered list in which all insertions take place at one end, the ____, while all deletions take place at the other end, the ____.  It is an example of a linear data structure.  

rear

front

A queue has a ________ structure where elements can only be added to the rear of the queue and removed from the front of the queue. 

First-In, First-Out (FIFO)

A queue has two main operations, what are those?

• enqueue for insertion and

• dequeue for deletion.  

Queue operation for insertion?

Enqueue

Queue operation for deletion?

Dequeue

Queues are known as ________ lists.

First In First Out (FIFO)

Adds an item onto the end of the queue.

enqueue(new-item:item-type)

Removes the item from the front of the queue.

dequeue()

Returns the item at the front of the queue.

front():item-type

Returns the item at the front of the queue.

back()

True if no more items can be dequeued and there is no front item.

is-empty():Boolean

True if no more items can be enqueued.

is-full():Boolean

Pushes a new element on to the end of the queue.

push(newElement)

Removes (but does not return) the element at the front of the queue

pop()

Returns the number of elements in the queue

get-size():Integer

ENUMERATION: The following are operations involved in a circular array implementation of a queue.

• Insertion at the rear of the array is constant time

• Removal from the front is linear time

• Removal from the rear of the array is constant time

• Insertion at the front is linear time

In linked list implementation of queue, each node for a single-linked list would store a total of ___ references.

two

In linked list implementation of queue, each node for a double-linked list would store a total of _____ references.

three

TRUE OR FALSE

Linked-list implementations of queue require more storage because of the extra space required for the links.

TRUE

It is a linear data structure, in which the elements are not stored at contiguous memory locations.

LinkedList

The elements in a linked list are linked using _____.

pointers

A linked list consists of?

• nodes where each node contains

  • a data field and

  • a reference(link) to the next node in the list.

A linked list consists of nodes where each node contains?

• a data field

• a reference(link) to the next node in the list.

ENUMERATE:

Three types of LinkedList:

1. Singly Linked List

2. Doubly Linked List

3. Circular Linked List

It is the most common form of a Linked List where each node contains a data field and a single pointer to the next node in the list.

Singly Linked List

The reference to the first node in the list is called the ____ of the list.

HEAD

The ________ field contained in the node is used to traverse to the next node and to its next node and so on till we reach a node that points to NULL.

pointer/reference/link

This is the last node in the list.

a node that points to NULL

TRUE OR FALSE

Also, a singly linked list can only be traversed in one and only one direction i.e. from head to the last node. There is no way to traverse from the last node back to the head.

It is a linked data structure that consists of a set of sequentially linked records called nodes.

Doubly Linked List

In Doubly Linked List, each node contains how many fields?

two

In Doubly Linked List, each node contains two fields, called?

• links

  • that are references to the previous and

  • to the next node in the sequence of nodes.

It  is a linked list where all nodes are connected to form a circle. There is no NULL at the end.

Circular Linked List

TRUE OR FALSE

A circular linked list can be a singly circular linked list or doubly circular linked list.

TRUE