Write a function to get Nth node in a Linked List Program
Write a GetNth() function that takes a linked list and an integer index and returns the data value stored in the node at that index position.
Linked List:
A linked list is a sequence of data elements, which are connected together through links. Each data element contains a connection to another data element in form of a pointer. Python does not have linked lists in its standard library.
Example:
Input: 1->10->30->14, index = 2 Output: 30 The node at index 2 is 30
Algorithm:
1. Initialize count = 0
2. Loop through the link list
a. if count is equal to the passed index then return current
node
b. Increment count
c. change current to point to next of the current.
[ad type=”banner”]
Python Programming for Write a function to get Nth node in a Linked List
[pastacode lang=”python” manual=”%23%20A%20complete%20working%20Python%20program%20to%20find%20n’th%20node%0A%23%20in%20a%20linked%20list%0A%20%0A%23%20Node%20class%0Aclass%20Node%3A%0A%20%20%20%20%23%20Function%20to%20initialise%20the%20node%20object%0A%20%20%20%20def%20__init__(self%2C%20data)%3A%0A%20%20%20%20%20%20%20%20self.data%20%3D%20data%20%23%20Assign%20data%0A%20%20%20%20%20%20%20%20self.next%20%3D%20None%20%23%20Initialize%20next%20as%20null%0A%20%0A%20%0A%23%20Linked%20List%20class%20contains%20a%20Node%20object%0Aclass%20LinkedList%3A%0A%20%0A%20%20%20%20%23%20Function%20to%20initialize%20head%0A%20%20%20%20def%20__init__(self)%3A%0A%20%20%20%20%20%20%20%20self.head%20%3D%20None%0A%20%0A%20%0A%20%20%20%20%23%20This%20function%20is%20in%20LinkedList%20class.%20It%20inserts%0A%20%20%20%20%23%20a%20new%20node%20at%20the%20beginning%20of%20Linked%20List.%0A%20%20%20%20def%20push(self%2C%20new_data)%3A%0A%20%0A%20%20%20%20%20%20%20%20%23%201%20%26%202%3A%20Allocate%20the%20Node%20%26%0A%20%20%20%20%20%20%20%20%23%20%20%20%20%20Put%20in%20the%20data%0A%20%20%20%20%20%20%20%20new_node%20%3D%20Node(new_data)%0A%20%0A%20%20%20%20%20%20%20%20%23%203.%20Make%20next%20of%20new%20Node%20as%20head%0A%20%20%20%20%20%20%20%20new_node.next%20%3D%20self.head%0A%20%0A%20%20%20%20%20%20%20%20%23%204.%20Move%20the%20head%20to%20point%20to%20new%20Node%0A%20%20%20%20%20%20%20%20self.head%20%3D%20new_node%0A%20%0A%20%20%20%20%23%20Returns%20data%20at%20given%20index%20in%20linked%20list%0A%20%20%20%20def%20getNth(self%2C%20index)%3A%0A%20%20%20%20%20%20%20%20current%20%3D%20self.head%20%23%20Initialise%20temp%0A%20%20%20%20%20%20%20%20count%20%3D%200%20%23%20Index%20of%20current%20node%0A%20%0A%20%20%20%20%20%20%20%20%23%20Loop%20while%20end%20of%20linked%20list%20is%20not%20reached%0A%20%20%20%20%20%20%20%20while%20(current)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(count%20%3D%3D%20index)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20current.data%0A%20%20%20%20%20%20%20%20%20%20%20%20count%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20current%20%3D%20current.next%0A%20%0A%20%20%20%20%20%20%20%20%23%20if%20we%20get%20to%20this%20line%2C%20the%20caller%20was%20asking%0A%20%20%20%20%20%20%20%20%23%20for%20a%20non-existent%20element%20so%20we%20assert%20fail%0A%20%20%20%20%20%20%20%20assert(false)%0A%20%20%20%20%20%20%20%20return%200%3B%0A%20%0A%23%20Code%20execution%20starts%20here%0Aif%20__name__%3D%3D’__main__’%3A%0A%20%0A%20%20%20%20llist%20%3D%20LinkedList()%0A%20%0A%20%20%20%20%23%20Use%20push()%20to%20construct%20below%20list%0A%20%20%20%20%23%201-%3E12-%3E1-%3E4-%3E1%0A%20%20%20%20llist.push(1)%3B%0A%20%20%20%20llist.push(4)%3B%0A%20%20%20%20llist.push(1)%3B%0A%20%20%20%20llist.push(12)%3B%0A%20%20%20%20llist.push(1)%3B%0A%20%0A%20%20%20%20n%20%3D%203%0A%20%20%20%20print%20’Element%20at%20index%203%20is%20%3A’%2C%20llist.getNth(n)” message=”Python” highlight=”” provider=”manual”/]Output:
Element at index 3 is 4
Time Complexity: O(n)
[ad type=”banner”]