Past exam question: 2072 Ashwin (Regular), Q6
Open in the Padhaiko appQuestion
Write an algorithm creates a single linked list.
Solution
Algorithm to Create a Singly Linked List of Nodes: Maintain head (for returning the list) and tail (to append each new node in ):
Algorithm CREATE_SLL(n):
1. Set head = NULL, tail = NULL
2. For i = 1 to n:
a) Allocate newNode = Allocate_Memory(sizeof(Node))
b) If newNode == NULL:
Print "Memory allocation failed"
Return head
c) Read value x
d) Set newNode->data = x, newNode->next = NULL
e) If head == NULL:
head = newNode
tail = newNode
Else:
tail->next = newNode
tail = newNode
3. Return head
Time complexity for nodes is .
Answer:
CREATE_SLL(n) allocates nodes sequentially, initializes head and tail on the first node, appends subsequent nodes via tail->next = newNode; tail = newNode, and terminates the last node with NULL.