ROLL NO:23691A3160: Assessmentz2

Assessmentz2
? ROLL NO:23691A3160
1) Linked lists are a fundamental data structure in computer science used for
storing collections of data. There are several types of linked lists, each with its
own characteristics and variations:
1.
Singly Linked List
a. In a singly linked list, each node contains data and a reference (link) to
the next node in the sequence.
b. The last node typically points to null, indicating the end of the list.
c. Traversal is only forward from the head (start) to the tail (end).
2.
Doubly Linked List
a. In a doubly linked list, each node has references to both the next and
the previous nodes.
b. This allows for bidirectional traversal: you can traverse forward from the
head to the tail, and backward from the tail to the head.
c. Each node requires extra memory for storing the reference to the
previous node.
3.
Circular Linked List
a. A circular linked list is a variation of a linked list where the last node
points back to the first node (forming a circle).
b. Circular linked lists can be singly or doubly linked.
c. They are often used in applications where continuous traversal is needed,
like round-robin scheduling.
4.
Singly Linked List with Tail Pointer
a. This is a singly linked list where besides the head pointer, there is also
a pointer to the tail node.
b. This allows for efficient insertion at both the head and the tail of the list.
c. Useful in scenarios where operations at the tail need to be optimized.
5.
Doubly Linked List with Head and Tail Pointers
a. This variant of a doubly linked list has explicit pointers to both the head
and the tail nodes.
b. Enables efficient insertion and deletion operations at both ends of the list.
2) Implementing a Binary Search Tree (BST) using a linked list involves creating
nodes that store data and pointers to their left and right children. Here’s a step-by-
step explanation of how to implement a BST using a linked list in a typical
object- oriented programming style (using a node class and a tree class):
Node Class
First, define a class for the nodes in the BST:
python
Copy code
class Tree Node:
def in it (self, key):
.key = key # Data stored in the node
.left = None # Pointer to the left child
right = None # Pointer to the right child
Assessmentz2
 Represents a node in the BST. Each node has a key (or data) and pointers (left and
right) to its left and right children.
Binary Search Tree Class
Next, define a class for the Binary Search Tree itself:
python
Copy code
class Binary Search Tree:
def int (self):
self .root = None # Initialize an empty BST
def insert(self, key):

self .root = self. _insert_ recursively(self .root, key)
def _insert _recursively(self, root, key):

# Base case: if the tree is empty, create a new node
if root is None:
return Tree Node(key)
# Otherwise, recur down the tree

if key < root .key:
root .left = self._ insert _recursively(root .left, key)
key > root .key:
root .right = self. _insert_ recursively(root .right, key)
# Return the (unchanged) node pointer

return root
def search(self, key):

return self. _search _recursively(self. root, key)
def _search _recursively(self, root, key):

# Base Cases: root is null or key is present at the root
if root is None or root. key == key:
return root
# Key is greater than root's key

if root .key < key:
return self. _search _recursively(roo t .right, key)
# Key is smaller than root's key

return self. _search_ recursively(root .left, key)
def delete(self, key):

self .root = self. _delete _recursively(self .root, key)
def _delete_ recursively(self, root, key):

# Base case: if the tree is empty
if root is None:
return root
# Recur down the tree

if key < root .k(root left key)
if key > root .key:
root .right = self. _delete _recursively(root .right, key)
else:
# Node with only one child or no child
Assessmentz2
if root .left is None:
temp = root .right
root = None
return temp
root. right is None:
temp = root. left
root = None
return temp
3) A hash function is a function that takes an input (or 'key') and produces a fixed-size
output, typically a hash value. This value is a representation of the input data in a way that is
optimized for rapid data retrieval in hash tables or hash-based data structures. Hash functions
are widely used in computer science for tasks such as data integrity checks, cryptography,
and indexing.
Properties of a Hash Function:
1. Deterministic: For the same input, a hash function should always produce the
same output.
2. Efficient: Hash functions should compute quickly, ideally in constant
time O(1)O(1)O(1).
3. Uniform Distribution: A good hash function distributes its output evenly across
its range of possible values, minimizing collisions (where two different inputs
produce the same hash value).
4. Pre-image Resistance: It should be computationally difficult to reverse-engineer
the input data from its hash value.
Example of a Hash Function:
Let's consider a simple example of a hash function that computes the sum of ASCII values of
characters in a string modulo a fixed number mmm. This is a basic example and not suitable
for cryptographic purposes, but it illustrates the concept:
python
Copy code
def simple _hash(s, m):
hash_ value = 0
for char in s:
hash _value += o r d(char) # sum of ASCII values of characters
return hash _value % m # modulo m to ensure hash _value is within
range 0 to m-1
 Input: A string s.
 Output: A hash value modulo m.
Example Usage:
Suppose we want to hash the string "apple" usingm = 5:
python
Copy code
Assessmentz2
Input _string = "apple"
Hash _value = simple

ROLL NO:23691A3160: Assessmentz2

Uploaded by

Copyright:

Available Formats

ROLL NO:23691A3160: Assessmentz2

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

ROLL NO:23691A3160: Assessmentz2

Uploaded by

Copyright:

Available Formats

Assessmentz2

First, define a class for the nodes in the BST:

Binary Search Tree Class

Next, define a class for the Binary Search Tree itself:

def insert(self, key):

def _insert _recursively(self, root, key):

# Otherwise, recur down the tree

# Return the (unchanged) node pointer

def search(self, key):

def _search _recursively(self, root, key):

# Key is greater than root's key

# Key is smaller than root's key

def delete(self, key):

def _delete_ recursively(self, root, key):

# Recur down the tree

Properties of a Hash Function:

Example of a Hash Function:

Suppose we want to hash the string "apple" usingm = 5:

You might also like