Unit 2: Linked Lists - Subjective Questions

A linked list is a dynamic linear data structure composed of nodes that are connected using links or pointers. Each node in a singly linked list contains:

• Data field: Stores the element.
• Link field: Stores the address of the next node.

The list is accessed through a pointer called START or HEAD. The final node contains a null link.

Advantages over arrays:

• It can grow or shrink during execution.
• Insertions and deletions do not require shifting elements.
• It does not require a contiguous block of memory.

Limitations:

• Additional memory is required for links.
• Direct or random access is unavailable; nodes must be visited sequentially.
• Pointer manipulation makes implementation more complex.
• Poor memory locality can make traversal slower than array traversal.

In a singly linked list, nodes may occupy noncontiguous memory locations. Every node stores its data and the address of its successor. A pointer named HEAD stores the address of the first node.

For a list containing , suppose the nodes are stored at addresses , , and :

• At address : data , link
• At address : data , link
• At address : data , link
• HEAD = 1000

Thus, logical order is determined by links rather than physical memory order. The abstract node declaration is Node = {data, next}. If HEAD is NULL, the list is empty.

A linked-list node is normally created at run time from the heap. The allocation operation reserves enough memory for the node and returns its address. The node's fields are then initialized before it is linked into the list.

Typical steps are:

1. Request memory for one node.
2. Check whether the returned pointer is NULL.
3. Store the required data in the node.
4. Initialize its link field.
5. Connect it to the list.

Allocation failure must be checked because the heap may not contain a sufficiently large free block. Dereferencing a null pointer causes undefined behavior or program failure.

When a node is deleted, its memory must be returned to the heap using the language's deallocation mechanism. Failure to do so causes a memory leak. Accessing a node after deallocation creates a dangling pointer, so references to deleted nodes must be updated carefully.

Traversal visits every node once, beginning at HEAD and following next links until NULL is reached.

Algorithm:

1. Set PTR = HEAD.
2. While PTR != NULL:
   • Process PTR.data.
   • Set PTR = PTR.next.
3. Stop when PTR becomes NULL.

If the list has nodes, the loop executes times. Therefore:

• Time complexity:
• Auxiliary space: for iterative traversal

The algorithm also handles an empty list because PTR is initially NULL, so the loop is skipped. A recursive traversal uses call-stack space and may overflow the stack for a very long list.

Let NEW be an allocated node containing the new item.

Insertion at the beginning:

• Set NEW.next = HEAD.
• Set HEAD = NEW.
• Complexity: .

Insertion at the end:

• Set NEW.next = NULL.
• If the list is empty, set HEAD = NEW.
• Otherwise, traverse to the last node and set LAST.next = NEW.
• Complexity: without a tail pointer and with a maintained tail pointer.

Insertion after node LOC:

• Set NEW.next = LOC.next.
• Set LOC.next = NEW.
• Complexity: when LOC is already known; searching for LOC requires .

The order of assignments is important. Saving the old successor in NEW.next before changing LOC.next prevents the remainder of the list from becoming unreachable.

To insert NEW before the first node whose data equals KEY:

1. Allocate and initialize NEW.
2. If HEAD == NULL, report that the key is absent.
3. If HEAD.data == KEY, set NEW.next = HEAD and HEAD = NEW.
4. Otherwise, maintain PREV = HEAD and CUR = HEAD.next.
5. Advance both pointers until CUR == NULL or CUR.data == KEY.
6. If CUR == NULL, report that the key was not found and release NEW if appropriate.
7. Otherwise, set NEW.next = CUR and PREV.next = NEW.

Boundary cases:

• Empty list
• Key in the first node
• Key in the last node
• Key absent
• Duplicate keys, for which the algorithm inserts before the first occurrence

Searching takes time, while the actual link modification takes time. Auxiliary space is .

Deletion must first preserve the address of the node to be removed and then reconnect the list before releasing memory.

Delete from the beginning:

• If HEAD == NULL, report underflow.
• Set TEMP = HEAD, HEAD = HEAD.next, and release TEMP.
• Complexity: .

Delete from the end:

• Handle the empty list and one-node list separately.
• For multiple nodes, traverse with PREV and CUR until CUR.next == NULL.
• Set PREV.next = NULL and release CUR.
• Complexity: .

Delete after node LOC:

• If LOC == NULL or LOC.next == NULL, deletion is impossible.
• Set TEMP = LOC.next.
• Set LOC.next = TEMP.next.
• Release TEMP.
• Complexity: when LOC is known.

Correct reconnection avoids lost nodes and dangling links.

The algorithm uses CUR to identify the current node and PREV to remember its predecessor.

1. If HEAD == NULL, report underflow.
2. Set CUR = HEAD and PREV = NULL.
3. Advance while CUR != NULL and CUR.data != KEY, updating PREV = CUR and CUR = CUR.next.
4. If CUR == NULL, the key is absent.
5. If PREV == NULL, the matching node is first, so set HEAD = CUR.next.
6. Otherwise, set PREV.next = CUR.next.
7. Release CUR.

The algorithm deletes only the first occurrence. Its time complexity is in the worst case and in the best case when the first node matches. It uses auxiliary space. Empty lists, first-node deletion, last-node deletion, missing keys, and duplicate values are handled explicitly.

A null-linked list uses a pointer such as HEAD to refer directly to the first data node. An empty list is represented by HEAD = NULL.

A header linked list begins with a special node called the header or sentinel. This node generally does not represent an ordinary list element.

A header node can:

• Store metadata such as node count.
• Store a pointer to the first data node.
• Provide a permanent predecessor for the first data node.
• Reduce special cases during insertion and deletion.
• Store aggregate information or identify the list.

In a grounded header list, the final link is NULL; in a circular header list, the final node points back to the header. A header requires a small amount of extra memory but often makes algorithms simpler and more uniform.

A grounded header linked list has a permanent header node followed by zero or more data nodes. Its last node contains a NULL link, so the list is grounded at the end.

A common structure is:

HEADER -> first data node -> ... -> last data node -> NULL

For traversal:

1. Set PTR = HEADER.next.
2. While PTR != NULL, process PTR.data and set PTR = PTR.next.

The header itself is not processed as ordinary data unless it intentionally stores metadata. An empty grounded header list is represented by HEADER.next = NULL; the header node still exists.

The permanent header removes the need to change an external head pointer for many operations and gives the first data node a predecessor, which simplifies insertion and deletion near the beginning.

In a grounded header list, traversal begins at HEADER.next, while the header acts as the predecessor of the first data node.

Insertion after node LOC:

• Create NEW.
• Set NEW.next = LOC.next.
• Set LOC.next = NEW.

To insert at the beginning, use LOC = HEADER; no separate update of an external HEAD pointer is required.

Deletion of a node after LOC:

• Ensure LOC.next != NULL.
• Set TEMP = LOC.next.
• Set LOC.next = TEMP.next.
• Release TEMP.

To delete the first data node, again use LOC = HEADER. The same link-changing logic therefore works at both the beginning and middle of the list. Searching may still require time, but once the predecessor is known, insertion or deletion takes time.

A circular header linked list contains a permanent header node, and the last data node points back to that header instead of containing NULL.

Its representation is:

HEADER -> first node -> ... -> last node -> HEADER

For an empty list, HEADER.next = HEADER. Traversal is performed as follows:

1. Set PTR = HEADER.next.
2. While PTR != HEADER, process the data and set PTR = PTR.next.

Advantages:

• No null link is required at the end.
• Traversal can begin at any node and continue cyclically.
• The header gives a clear stopping condition.
• Beginning and end operations can be made uniform.
• It is useful for cyclic processes such as round-robin scheduling.

The traversal condition must compare against the header; checking only for NULL would cause an infinite loop.

Both structures contain a permanent header node, but their termination links differ.

Grounded header list:

• The last node points to NULL.
• An empty list satisfies HEADER.next == NULL.
• Traversal stops when the current pointer becomes NULL.
• It naturally represents a sequence with a definite terminal marker.

Circular header list:

• The last node points to HEADER.
• An empty list satisfies HEADER.next == HEADER.
• Traversal stops when the pointer returns to HEADER.
• It supports repeated cyclic traversal and round-robin applications.

Both simplify boundary operations by providing a permanent predecessor to the first data node. Circular lists require careful termination checks to avoid infinite loops, whereas grounded lists use the familiar null-link condition.

Let HEADER be the sentinel node. The list is empty when HEADER.next == HEADER.

Insert after LOC:

• Allocate NEW and store the item.
• Set NEW.next = LOC.next.
• Set LOC.next = NEW.

Insertion at the beginning uses LOC = HEADER and takes time.

Insert at the end:

• Traverse until LAST.next == HEADER.
• Set NEW.next = HEADER.
• Set LAST.next = NEW.
• This takes without a tail pointer and with one.

Delete after LOC:

• If LOC.next == HEADER, no data node follows LOC.
• Otherwise, set TEMP = LOC.next, LOC.next = TEMP.next, and release TEMP.

Deleting the only data node automatically restores HEADER.next == HEADER. The header must never be deallocated as an ordinary node.

A two-way linked list, also called a doubly linked list, is a linked structure in which every node has links to both its predecessor and successor. A node has the form Node = {prev, data, next}.

For an ordinary linear doubly linked list:

• HEAD points to the first node.
• The first node's prev is NULL.
• TAIL may point to the last node.
• The last node's next is NULL.

Advantages:

• Supports forward and backward traversal.
• A known node can be deleted in time without searching for its predecessor.
• Insertion before a known node is direct.
• Efficient operations are possible at both ends when HEAD and TAIL are maintained.

Disadvantages:

• Each node requires an additional pointer.
• More links must be updated during modifications.
• Incorrect updates can break forward-backward consistency.

For forward traversal, begin at HEAD, process each node, and repeatedly follow next until NULL is reached. For backward traversal, begin at TAIL, process each node, and repeatedly follow prev until NULL is reached.

Both traversals take time and auxiliary space for a list of nodes.

The key consistency invariants are:

• If P.next = Q, then Q.prev = P.
• If Q.prev = P, then P.next = Q.
• HEAD.prev = NULL for a nonempty linear list.
• TAIL.next = NULL for a nonempty linear list.
• For an empty list, both HEAD and TAIL should be NULL.

Checking these invariants helps detect broken links after insertion or deletion.

Assume both HEAD and TAIL are maintained.

Insertion at the beginning:

1. Create NEW and set NEW.prev = NULL.
2. Set NEW.next = HEAD.
3. If the list is empty, set TAIL = NEW; otherwise set HEAD.prev = NEW.
4. Set HEAD = NEW.

Insertion at the end:

1. Create NEW and set NEW.next = NULL.
2. Set NEW.prev = TAIL.
3. If the list is empty, set HEAD = NEW; otherwise set TAIL.next = NEW.
4. Set TAIL = NEW.

Both operations take time when HEAD and TAIL are available. In the one-node or empty-list cases, both pointers must remain consistent. After either insertion, forward and backward links should satisfy the adjacency invariants.

Let LOC be the specified existing node.

Insert after LOC:

• Set NEW.prev = LOC.
• Set NEW.next = LOC.next.
• If LOC.next != NULL, set LOC.next.prev = NEW; otherwise set TAIL = NEW.
• Set LOC.next = NEW.

Insert before LOC:

• Set NEW.next = LOC.
• Set NEW.prev = LOC.prev.
• If LOC.prev != NULL, set LOC.prev.next = NEW; otherwise set HEAD = NEW.
• Set LOC.prev = NEW.

Each insertion takes time if LOC is already known. If the node must first be found by key, the complete operation takes . The order of updates preserves access to the old neighbors and correctly handles insertion next to HEAD or TAIL.

Let LOC point to the node being deleted. The links on both sides must be repaired.

1. If LOC == NULL, perform no deletion.
2. If LOC.prev != NULL, set LOC.prev.next = LOC.next; otherwise set HEAD = LOC.next.
3. If LOC.next != NULL, set LOC.next.prev = LOC.prev; otherwise set TAIL = LOC.prev.
4. Release LOC.

Boundary cases:

• For the first node, HEAD changes.
• For the last node, TAIL changes.
• For the only node, both HEAD and TAIL become NULL.
• For a middle node, both neighboring nodes are reconnected.

Deletion takes time when LOC is known because the predecessor is directly available through prev. If LOC must be found by key, searching raises the total complexity to .

Singly linked list:

• One link per node: next.
• Forward traversal only.
• Lowest pointer overhead among the three.
• Beginning insertion is ; deletion of a known node generally requires its predecessor.

Circular header linked list:

• One next link per data node plus a permanent header.
• The last node points to the header.
• Supports cyclic forward traversal and has no null end link.
• The sentinel simplifies beginning operations and empty-list representation.

Two-way linked list:

• Two links per node: prev and next.
• Supports traversal in both directions.
• Uses more memory and requires more pointer updates.
• Insertion before or after a known node and deletion of a known node take .

For all three structures, searching for an arbitrary key takes . The best choice depends on whether memory efficiency, cyclic processing, or bidirectional updates are most important.