Unit 3: Introduction to Linked Lists - Subjective Questions

Linked list: A linked list is a dynamic linear data structure made up of nodes that need not be stored in contiguous memory locations.

Each node of a singly linked list contains:

• Data field: Stores the value or information.
• Link field: Stores a reference or pointer to the next node.

The head pointer stores the address of the first node. If the list is empty, head is NULL. The link field of the final node is also NULL, indicating the end of the list.

A node can be represented conceptually as [data | next].

A singly linked list is implemented using a self-referential structure, which contains a pointer to another structure of the same type.

Example in C:

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

Steps to create the first node:

1. Declare head and initialize it to NULL.
2. Allocate memory for a new node dynamically.
3. Store the required value in its data field.
4. Set its next field to NULL.
5. Assign the address of the new node to head.

After these operations, the new node is both the first and last node of the list.

Traversal means visiting every node of the linked list, usually from the first node to the last node.

Algorithm:

1. Set a temporary pointer current = head.
2. Repeat while current != NULL:
   • Process or display current.data.
   • Move to the next node using current = current.next.
3. Stop when current becomes NULL.

Pseudocode:

TRAVERSE(head)
    current = head
    while current != NULL
        print current.data
        current = current.next

For a list containing nodes:

• Time complexity:
• Auxiliary space complexity:

The temporary pointer should be used so that the original head pointer is not changed.

To insert a node at the beginning:

1. Allocate memory for newNode.
2. Store the new value in newNode.data.
3. Set newNode.next = head.
4. Set head = newNode.

Pointer transformation:

• Before insertion: head -> A -> B -> NULL
• After inserting N: head -> N -> A -> B -> NULL

The same steps work for an empty list because the old value of head is NULL.

• Time complexity:
• No traversal is required.

To insert newNode at the end, first initialize newNode.next to NULL.

Case 1: Empty list

• If head == NULL, assign head = newNode.
• The new node becomes the first and last node.

Case 2: Non-empty list

1. Set current = head.
2. Traverse until current.next == NULL.
3. Set current.next = newNode.

Pseudocode:

INSERT_END(head, value)
    create newNode
    newNode.data = value
    newNode.next = NULL
    if head == NULL
        head = newNode
    else
        current = head
        while current.next != NULL
            current = current.next
        current.next = newNode

Without a tail pointer, the time complexity is . With a maintained tail pointer, insertion at the end can be performed in time.

Assume that positions start from .

Algorithm:

1. Create newNode and store the value in it.
2. If the position is :
   • Set newNode.next = head.
   • Set head = newNode.
3. Otherwise, move a pointer to the node at position .
4. If that predecessor does not exist, report an invalid position and release the newly allocated node.
5. Set newNode.next = previous.next.
6. Set previous.next = newNode.

For example, inserting X at position changes:

A -> B -> C -> NULL

to:

A -> B -> X -> C -> NULL

The worst-case time complexity is , while the pointer updates themselves take time.

Deletion from the beginning is performed as follows:

1. Check whether head == NULL.
2. If true, report underflow because there is no node to delete.
3. Otherwise, store the first node in a temporary pointer: temp = head.
4. Move the head pointer forward: head = head.next.
5. Release or deallocate temp.

Example:

• Before: head -> A -> B -> C -> NULL
• After: head -> B -> C -> NULL

The removed node must be released so that dynamically allocated memory does not become inaccessible and cause a memory leak.

The operation takes time.

Three cases must be considered:

1. Empty list:

• If head == NULL, deletion is impossible and an underflow condition is reported.

2. List with one node:

• Store head in a temporary pointer.
• Set head = NULL.
• Release the temporary node.

3. List with multiple nodes:

1. Traverse with current until current.next.next == NULL.
2. Store the final node in temp = current.next.
3. Set current.next = NULL.
4. Release temp.

The traversal makes the time complexity . If both tail and predecessor information are not available, a singly linked list cannot directly move backward from the last node.

The operation must handle an empty list, a match at the head, a match elsewhere, and an absent key.

Algorithm:

1. If head == NULL, report underflow.
2. If head.data == key:
   • Store head in temp.
   • Set head = head.next.
   • Release temp.
3. Otherwise, set current = head.
4. Move forward while current.next != NULL and current.next.data != key.
5. If current.next == NULL, report that the key was not found.
6. Otherwise:
   • Set temp = current.next.
   • Set current.next = temp.next.
   • Release temp.

Only the first occurrence is deleted. The worst-case time complexity is and the auxiliary space complexity is .

Underflow occurs when an operation attempts to delete or access a node from an empty linked list.

• Condition: head == NULL
• Example: Attempting to delete the first node when no node exists.
• Handling: Check whether the list is empty before deletion and display or return an appropriate error.

Overflow occurs when a new node cannot be created because memory allocation fails.

• Condition: The memory allocator returns NULL or an equivalent failure result.
• Unlike a fixed-size array, a linked list has no predetermined capacity; its practical limit is available memory.
• Handling: Verify allocation success before accessing the node and report failure if memory is unavailable.

Thus, underflow concerns removing from an empty structure, whereas overflow concerns failure to obtain memory for insertion.

A linked list is suitable when frequent insertions and deletions are needed. An array is preferable when fast indexed access and compact storage are more important.

A tree is a non-linear, hierarchical data structure consisting of nodes connected by edges. A non-empty tree has a distinguished node called the root, and the remaining nodes form disjoint subtrees below it.

Key differences are:

• A linked list represents a linear sequence, whereas a tree represents a hierarchy.
• Except for the root, every node in a tree has one parent in the usual rooted-tree model.
• A tree node may have multiple children, while a singly linked-list node normally has only one next link.
• There is a unique path from the root to each node in a tree.
• Trees are useful for representing file systems, organization charts, expression structures, and search structures.

A tree with nodes has edges, provided it is connected and contains no cycles.

Consider a tree in which A has children B and C, while B has children D and E.

• Root: The topmost node with no parent. Here, A is the root.
• Edge: A connection between two nodes. Examples include A-B and B-D.
• Parent: A node directly above another node. B is the parent of D and E.
• Child: A node directly below another node. B and C are children of A.
• Siblings: Nodes having the same parent. B and C are siblings; D and E are also siblings.
• Leaf: A node with no children. In this example, C, D, and E are leaves.

These terms describe the immediate structural relationships among nodes in a rooted tree.

• Degree of a node: The number of children of that node. A leaf has degree .
• Degree of a tree: The maximum degree of any node in the tree.
• Depth of a node: The number of edges from the root to that node. The root has depth .
• Level of a node: Often defined as depth + 1, so the root is at level . Some texts start levels at , so the convention must be stated.
• Height of a node: The number of edges on the longest downward path from that node to a leaf. A leaf has height .
• Height of a tree: The height of its root, equal to the maximum depth of any node.

Depth measures distance from the root downward to a node, while height measures the longest distance from a node downward to a leaf.

A path is a sequence of nodes in which each consecutive pair is connected by an edge. For example, if A is connected to B and B to D, then A -> B -> D is a path.

• The path length is the number of edges in the path.
• Therefore, the path A -> B -> D has length .
• In a tree, there is exactly one simple path between any two nodes.

A subtree consists of a selected node together with all of its descendants and the edges connecting them. If B has descendants D and E, the subtree rooted at B contains B, D, and E.

Every node can be regarded as the root of a subtree. A leaf forms a subtree containing only itself.

A binary tree is a tree in which each node has at most two children, specifically identified as the left child and right child.

Important properties, assuming the root is at level , include:

• Maximum nodes at level :
• Maximum nodes in a binary tree of height :
• Maximum number of leaf nodes at height :
• For nodes, the number of edges is
• In a linked representation with two child pointers per node, a binary tree with nodes has null child links.

A general tree may have any number of children per node. A binary tree permits no more than two, and the positions of left and right children are distinct even when only one child exists.

A binary search tree (BST) is a binary tree satisfying the following ordering property for every node:

• All keys in the left subtree are smaller than the node's key.
• All keys in the right subtree are larger than the node's key.
• Each left and right subtree must also be a BST.

A consistent policy is required if duplicate keys are allowed.

Searching: Compare the key with the current node. Move left for a smaller key and right for a larger key.

Insertion: Follow the same comparisons until a null child position is found, then attach the new node there.

Deletion:

• A leaf can be removed directly.
• A node with one child is replaced by its child.
• A node with two children is commonly replaced by its inorder successor or predecessor, after which that replacement node is deleted.

These operations take time, where is the tree height. They are in a balanced BST but may degrade to in a skewed BST.

Preorder traversal follows the order:

1. Visit the root.
2. Traverse the left subtree.
3. Traverse the right subtree.

Recursive algorithm:

PREORDER(node)
    if node != NULL
        visit node
        PREORDER(node.left)
        PREORDER(node.right)

For the given tree:

• Visit A first.
• Traverse the subtree rooted at B: B, D, E.
• Traverse the subtree rooted at C: C, F.

Therefore, the preorder sequence is:

A, B, D, E, C, F

For nodes, traversal takes time. Recursive auxiliary space is , where is the tree height.

Inorder traversal follows the order:

1. Traverse the left subtree.
2. Visit the root.
3. Traverse the right subtree.

Recursive algorithm:

INORDER(node)
    if node != NULL
        INORDER(node.left)
        visit node
        INORDER(node.right)

For a tree with root A, children B and C, children D and E under B, and right child F under C, the inorder sequence is:

D, B, E, A, C, F

The special significance of inorder traversal is that it visits the keys of a binary search tree in sorted order, provided its duplicate-key policy preserves the required ordering.

Its time complexity is and its recursive auxiliary space is .

Postorder traversal visits nodes in this order:

1. Traverse the left subtree.
2. Traverse the right subtree.
3. Visit the root.

Recursive algorithm:

POSTORDER(node)
    if node != NULL
        POSTORDER(node.left)
        POSTORDER(node.right)
        visit node

For a tree with root A, children B and C, children D and E under B, and right child F under C, the postorder sequence is D, E, B, F, C, A.

Comparison and uses:

• Preorder — Root, Left, Right: Useful for copying a tree or generating prefix expressions.
• Inorder — Left, Root, Right: Produces sorted keys when applied to a BST.
• Postorder — Left, Right, Root: Useful for deleting a tree because children are processed before their parent, and for generating postfix expressions.

Each traversal visits every node once, so its time complexity is . Recursive space usage is .