Write short notes on any two of the following: i) Queue using linked list ii) Hashing iii) Post fix expression evaluation iv) Linked list operations

Queue Using Linked List

A queue is a data structure that follows the First-In-First-Out (FIFO) principle, meaning the first element added to the queue (front) is the first one to be removed (rear). Implementing a queue using a linked list is a common approach due to its flexibility and efficient memory usage.

1. Implementation:

   • A queue using a linked list consists of nodes, each containing data and pointers to the next and previous nodes.
   • Two pointers, front and rear, are used to keep track of the beginning and end of the queue, respectively.
   • Enqueue Operation: To add an element to the queue (i.e., enqueue), a new node is created, its data field is set to the new element, and the node is inserted at the rear of the list.
   • Dequeue Operation: To remove an element from the queue (i.e., dequeue), the element at the front of the list is removed, and the front pointer is advanced to the next node.
   • Empty Check: To check if the queue is empty, it is sufficient to check if the front pointer is null.

2. Complexity:

   • Enqueue: O(1) - Adding an element to the rear of the list takes constant time.
   • Dequeue: O(1) - Removing an element from the front of the list also takes constant time.

Hashing

Hashing is a technique used to organize and retrieve data efficiently. It involves mapping keys to values, allowing fast retrieval of values based on their keys. A hash function is used to calculate the index or address of the key in the hash table, where the value is stored.

1. Hash Function:

   • A hash function is a mathematical function that maps a key to a hash value.
   • Common hash functions include:
     • Division Method: The key is divided by the size of the hash table, and the remainder is used as the hash value.
     • Multiplication Method: The key is multiplied by a constant, and the fractional part of the product is used as the hash value.
     • Universal Hashing: A family of hash functions is used, and a random function is selected from the family to calculate the hash value.

2. Hash Table:

   • A hash table is an array of elements, each of which can hold a key-value pair.
   • The size of the hash table should be chosen carefully to avoid collisions, where multiple keys map to the same hash value.
   • Collisions can be handled using various techniques, such as chaining and open addressing.

3. Search and Retrieval:

   • To search for a value, the hash function is applied to the key, and the resulting hash value is used to determine the location of the key-value pair in the hash table.
   • If the key is found, the corresponding value is retrieved.

4. Advantages of Hashing:

   • Fast search and retrieval: With a good hash function, the search time for a value is O(1) on average.
   • Efficient memory usage: Only the keys and values are stored in the hash table, reducing memory overhead.

Linked List Operations

Linked lists are a fundamental data structure consisting of nodes, each containing data and a reference to the next node. They offer efficient insertion and deletion operations.

1. Insertion:
   • To insert a node at the beginning of the list (i.e., head insertion):
     • Create a new node with the given data.
     • Set the new node's next pointer to the current head node.
     • Update the head pointer to point to the new node.

• To insert a node at the end of the list (i.e., tail insertion):
  • Traverse the list until the last node is reached.
  • Create a new node with the given data.
  • Set the last node's next pointer to the new node.

1. Deletion:
   • To delete a node from the beginning of the list (i.e., head deletion):
     • Store the data from the head node.
     • Update the head pointer to point to the next node.
     • Delete the old head node.

• To delete a node from the end of the list (i.e., tail deletion):

  • Traverse the list until the second to last node is reached.
  • Set the second to last node's next pointer to null.
  • Delete the old last node.

• To delete a node in the middle of the list:

  • Traverse the list until the node to be deleted is found.
  • Store the data from the node to be deleted.
  • Connect the previous node's next pointer to the next node of the node to be deleted.
  • Delete the node to be deleted.

1. Search:
   • To search for a node with a given value:
     • Traverse the list and compare the data in each node with the given value.
     • Return the node if the data matches the given value.
     • If the data is not found, return null.