PadhaikoAll subjects

Past exam question: 2072 Ashwin (Regular), Q6

Data Structure and Algorithms · 5 marks

Open in the Padhaiko app

Topic: Linked List

Question

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.

All past exam questions for Data Structure and Algorithms