IN2002 Data Structures and Algorithms - Iterative Linked List Reversal

This assignment presents an iterative algorithm designed to reverse a singly linked list by modifying the links between nodes. The solution begins with an iterative approach, detailing the algorithm's steps using pseudocode, and includes a high-level explanation of how the algorithm functions, focusing on the core logic rather than a line-by-line breakdown. It then analyzes the algorithm's time and space complexity, providing justifications for the identified complexities. Specifically, the time complexity is determined to be O(N), explained through the algorithm's linear dependence on the number of elements. The space complexity is identified as O(N) as well. The assignment also briefly touches upon the recursive version of the algorithm, outlining the key steps involved in its implementation. The document concludes with a screenshot of the implementation.

Running head: IN2002 DATA STRUCTURES AND ALGORITHMS
IN2002 Data Structures and Algorithms
Name of the Student
Name of the University
Authors note

1IN2002 DATA STRUCTURES AND ALGORITHMS
Iterative version for reversing a singly linked list
Begin:
If (headnode != NULL)
then
pre ← headnode
headnode ← headnode.next
cur ← headnode
prev.next ← NULL
While (headnode != NULL) do
headnode← headnode.next
cur.next ← prev
prev ← cur
cur ← headnode
End while
headnode ← prev
End if
End

2IN2002 DATA STRUCTURES AND ALGORITHMS
High level explanation of the algorithm
1. Three pointers are declared and initialized, these are prev, current node as head and
finally the next as NULL.
2 start Iteration throughout the singly linked list using suitable loop .
2. Store the next node
3. Link the nodes in the following way;
next = curr->next
4. Change the next of current.
Link the previous node and reverse the list one by one.
curr->next = prev
5. Change the prev, curr node one step forward
prev = curr
curr = next
6. Iiterate the process until all the links reversed and link of head is null.
Screenshot of the implementation

3IN2002 DATA STRUCTURES AND ALGORITHMS
Time complexity of the algorithm
The developed algorithm have O (N) time complexity. As in the algorithm we are using N
times of a static amount of first loop or operations and after that a static amount similar
second loop or operation; the reverse function will be independent of the value of the "N".
Therefore, it means the complexity is of class O (2N+a) and consequently of class O(2N)=
O(N). In other words it can be said that the time complexity of the program increases in a
linear way with the increasing number of elements in the considered list of elements.
Space complexity of the Algorithm

4IN2002 DATA STRUCTURES AND ALGORITHMS
As the developed algorithm does not allocate any objects of any class; nevertheless it has
O(n) space complexity in the execution time. Whenever the reverse function is called, this
invocation requires setting up a stack frame. In this program, it includes return addresses as
well as requires stack space in order to store the parameters as well as variables. Here it can
be said, that even if variables point to null it will use the stack space.
Recursive Version of the algorithm
For the recursive version of the algorithm;
1. First divide the singly linked list in two segments in which one o is first node and
remaining is rest of the linked list.
2. For the next parts, the reverse function needs to be called and change links among the
linked list.
3. Link the reversed rest to first element of the linked list.
4. Fix the head pointer or link.