Given a doubly-linked list, a position p, and an integer x. The task is to add a new node with value x at the position just after p^{th} node in the doubly linked list.
Example 1:
Input:
LinkedList: 2<->4<->5
p = 2, x = 6 
Output: 2 4 5 6
Explanation: p = 2, and x = 6. So, 6 is
inserted after p, i.e, at position 3
(0-based indexing).
Example 2:
Input:
LinkedList: 1<->2<->3<->4
p = 0, x = 44
Output: 1 44 2 3 4
Explanation: p = 0, and x = 44 . So, 44
is inserted after p, i.e, at position 1
(0-based indexing).
Your Task:
The task is to complete the function addNode() which head reference, position and data to be inserted as the arguments, with no return type.
Expected Time Complexity : O(N)
Expected Auxilliary Space : O(1)
Constraints:
1 <= N <= 10^{4}
0 <= p < N

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Starter code:
# Your task is to complete this function
# function should add a new node after the pth position
# function shouldn't print or return any data

'''
class Node:
	def __init__(self, data):
		self.data = data
		self.next = None
		self.prev = None

'''
#Function to insert a new node at given position in doubly linked list.
def addNode(head, p, data):
    # Code here


Solutions:
def addNode(head, p, data):
	data = Node(data)
	current = head
	i = 0
	while i <= p + 1:
		i += 1
		if i == p + 1:
			data.next = current.next
			current.next = data
			data.prev = current
			if data.next is not None:
				data.next.prev = data
		current = current.next
	return head


def addNode(head, p, data):
	if head == None:
		return Node(data)
	curr = head
	while p > 0:
		curr = curr.next
		p -= 1
	new_node = Node(data)
	temp = curr.next
	curr.next = new_node
	new_node.prev = curr
	new_node.next = temp
	return head


def addNode(head, p, data):
	temp = Node(data)
	cur = head
	for i in range(p):
		cur = cur.next
	if cur.next:
		cur.next.prev = temp
		temp.next = cur.next
		temp.prev = cur
		cur.next = temp
	else:
		cur.next = temp
		temp.prev = cur
	return head


def addNode(head, p, data):
	pos = 0
	temp = Node(data)
	curr = head
	while curr != None:
		if pos == p:
			temp.next = curr.next
			if curr.next != None:
				curr.next.prev = temp
			curr.next = temp
			temp.prev = curr
			break
		pos += 1
		curr = curr.next
	return


def addNode(head, p, data):
	nn = Node(data)
	if head == None:
		return nn
	curr = head
	while p:
		curr = curr.next
		p -= 1
	nn.next = curr.next
	curr.next = nn
	nn.prev = curr
	if nn.next:
		nn.next.prev = nn


def addNode(head, p, data):
	n = Node(data)
	c = head
	for _ in range(p):
		c = c.next
	n.next = c.next
	n.prev = c
	if c.next:
		c.next.prev = n
	c.next = n


def addNode(head, p, data):
	node_to_insert = Node(data)
	dummy = Node(0)
	dummy.next = head
	curr = dummy
	for i in range(p + 1):
		curr = curr.next
	node_to_insert.next = curr.next
	if curr.next is not None:
		curr.next.prev = node_to_insert
	curr.next = node_to_insert
	node_to_insert.prev = curr
	return dummy.next


def addNode(head, p, data):
	temp = head
	i = 0
	node = Node(data)
	while i < p:
		temp = temp.next
		i += 1
	node.prev = temp
	node.next = temp.next
	if temp.next:
		temp.next.prev = node
	temp.next = node


def addNode(head, p, data):
	new = Node(data)
	if head is None:
		return
	curr = head
	for i in range(pos):
		curr = curr.next
	if curr.next is None:
		curr.next = new
		new.prev = curr
		return head
	else:
		nxt = curr.next
		curr.next = new
		nxt.prev = new
		new.next = nxt
		new.prev = curr
		return head


def addNode(head, p, data):
	newNode = Node(data)
	count = 0
	cur = head
	while cur and count != p:
		cur = cur.next
		count += 1
	newNode.next = cur.next
	cur.next = newNode
	newNode.prev = cur
	if newNode.next:
		newNode.next.prev = newNode


def addNode(head, p, data):
	t = head
	while t != None:
		if p == 0:
			node = Node(data)
			node.next = t.next
			node.prev = t
			t.next = node
			if node.next != None:
				node.next.prev = node
			break
		t = t.next
		p -= 1


def addNode(head, p, data):
	(curr, position) = (head, 0)
	while curr:
		if position == p:
			next = curr.next
			curr.next = Node(data)
			curr.next.next = next
			curr.next.prev = curr
			break
		position += 1
		curr = curr.next
	return head


def addNode(head, p, data):
	newNode = Node(data)
	counter = 0
	temp = head
	while counter < p:
		counter += 1
		temp = temp.next
	newNode.next = temp.next
	newNode.prev = temp
	temp.next = newNode
	return head


def addNode(head, p, data):
	new_node = Node(data)
	if head == None:
		return new_node
	curr = head
	for i in range(p):
		curr = curr.next
	new_node.next = curr.next
	new_node.prev = curr
	curr.next = new_node
	return head


def addNode(head, p, data):
	count = 0
	curr = head
	while count < p and curr.next is not None:
		curr = curr.next
		count += 1
	temp = Node(data)
	temp.next = curr.next
	temp.prev = curr
	if curr.next is not None:
		temp.next.prev = temp
	curr.next = temp


def addNode(head, p, data):
	node = Node(data)
	while p != 0:
		head = head.next
		p -= 1
	if head.next is None:
		head.next = node
		node.prev = head
		return
	node.next = head.next
	head.next.prev = node
	head.next = node
	node.prev = head


def addNode(head, p, data):
	cur_node = head
	prev_node = head
	for i in range(p):
		cur_node = cur_node.next
	next_node = cur_node.next
	new_node = Node(data)
	cur_node.next = new_node
	new_node.prev = cur_node
	new_node.next = next_node
	return head


def addNode(head, p, data):
	itr = head
	for i in range(p):
		itr = itr.next
	temp = Node(data)
	temp.next = itr.next
	itr.next = temp
	temp.prev = itr
	if temp.next != None:
		temp.next.prev = temp
	return head


def addNode(head, p, data):
	i = 0
	N = Node(data)
	n = head
	while i < p:
		n = n.next
		i += 1
	if n.next == None:
		N.next = n.next
		N.prev = n
		n.next = N
	else:
		N.next = n.next
		N.prev = n
		n.next = N
		N.next.prev = N


def addNode(head, p, data):
	current = head
	count = 0
	node = Node(data)
	while current:
		if count == p:
			if current.next == None:
				current.next = node
				current.next.prev = current
				return head
			else:
				node.next = current.next
				node.prev = current
				current.next.prev = node
				current.next = node
				return head
		current = current.next
		count += 1


def addNode(head, p, data):
	temp = head
	if head is None:
		return Node(data)
	for i in range(p):
		temp = temp.next
	cur = Node(data)
	cur.next = temp.next
	cur.prev = temp
	temp.next = cur
	return head


def addNode(head, p, data):
	x = Node(data)
	count = 0
	temp = head
	while count < p:
		temp = temp.next
		count += 1
	x.next = temp.next
	temp.next = x
	x.prev = temp
	return


def addNode(head, p, data):
	temp = head
	cnt = -1
	while cnt < p:
		cnt += 1
		if cnt == p:
			temp1 = Node(data)
			temp1.next = temp.next
			temp.next = temp1
			temp1.prev = temp
		else:
			temp = temp.next


def addNode(head, p, data):
	new_node = Node(data)
	curr = head
	for _ in range(p):
		curr = curr.next
	new_node.next = curr.next
	if curr.next:
		curr.next.prev = new_node
	new_node.prev = curr
	curr.next = new_node


def addNode(head, p, data):
	node = Node(data)
	if p == 0:
		node.next = head.next
		node.prev = head
		if not head.next is None:
			node.next.prev = node
		head.next = node
		return
	temp = head
	for i in range(p):
		temp = temp.next
	if not temp.next is None:
		node.next = temp.next
		node.next.prev = node
	if not temp.prev is None:
		node.prev = temp
		temp.next = node


def addNode(head, p, data):
	temp = Node(data)
	if head == None:
		return temp
	curr = head
	for i in range(p):
		curr = curr.next
	if curr.next:
		curr.next.prev = temp
		temp.next = curr.next
		temp.prev = curr
		curr.next = temp
	else:
		curr.next = temp
		temp.prev = curr
	return head


def addNode(head, p, data):
	temp = head
	c = 0
	while c < p:
		temp = temp.next
		c += 1
	data = Node(data)
	if temp.next:
		temp.next.prev = data
		data.next = temp.next
		data.prev = temp
		temp.next = data
	else:
		temp.next = data
		data.prev = temp
	return head


def addNode(head, p, data):
	p1 = head
	while p:
		p -= 1
		p1 = p1.next
	nxt = p1.next
	p1.next = Node(data)
	p1.next.prev = p1
	p1.next.next = nxt
	if nxt:
		nxt.prev = p1.next


def addNode(head, p, data):
	n = Node(data)
	curr = head
	i = 0
	while i < p:
		if curr == None:
			return
		curr = curr.next
		i += 1
	n.next = curr.next
	curr.next = n
	n.prev = curr
	if n.next != None:
		n.next.prev = n
	return head


def addNode(head, p, data):
	cnt = -1
	cur = head
	n = None
	while cnt < p:
		cnt += 1
		if cnt == p:
			n = cur.next
			new = Node(data)
			cur.next = new
			new.prev = cur
			new.next = n
			if n != None:
				n.prev = new
		cur = cur.next
	return head


def addNode(head, p, data):
	newNode = Node(data)
	curr = head
	for i in range(p):
		curr = curr.next
	newNode.next = curr.next
	newNode.prev = curr
	curr.next = newNode
	return head


def addNode(head, p, data):
	a = head
	for i in range(p):
		head = head.next
	s = Node(data)
	s.next = head.next
	head.next = s
	s.prev = head
	return a


def addNode(head, location, data):
	newnode = Node(data)
	temp = head
	index = 0
	while index < location:
		temp = temp.next
		index += 1
	if temp.next == None:
		temp.next = newnode
		newnode.prev = temp
	else:
		newnode.next = temp.next
		temp.next = newnode
		newnode.next.prev = newnode
		newnode.prev = temp


def addNode(head, p, data):
	x = head
	if not x:
		return Node(data=data)
	else:
		while p > 0 and x.next:
			x = x.next
			p -= 1
		k = Node(data=data)
		k.next = x.next
		x.next = k
		k.prev = x
		if k.next:
			k.next.prev = k
		return head


def addNode(head, p, data):
	ptr = head
	while p > 0:
		ptr = ptr.next
		p -= 1
	node = Node(data)
	node.next = ptr.next
	node.prev = ptr
	ptr.next = node
	if node.next:
		node.next.prev = node
	return head


def addNode(head, p, data):
	cur = head
	for _ in range(p):
		cur = cur.next
	newNode = Node(data)
	if not cur.next:
		cur.next = newNode
		newNode.prev = cur
		return head
	nex = cur.next
	cur.next = newNode
	newNode.next = nex
	nex.prev = newNode
	newNode.prev = cur
	return head


def addNode(head, p, data):
	temp = head
	newnode = Node(data)
	index = 0
	while index < p:
		temp = temp.next
		index += 1
	newnode.next = temp.next
	temp.next = newnode
	newnode.prev = temp


def addNode(head, p, data):
	insert_pos = p + 1
	start_pos = 0
	start = head
	prev = head
	while start_pos < insert_pos - 1:
		start = start.next
		prev = prev.next
		start_pos += 1
	if start.next is None:
		start.next = Node(data)
		start = start.next
		start.prev = prev
	else:
		node = Node(data)
		start = start.next
		prev.next = node
		node.prev = prev
		node.next = start
		start.prev = node
	return head


def addNode(head, p, data):
	temp = Node(data)
	if p == 0:
		data = head.next
	while p != 0:
		head = head.next
		p -= 1
	d = head.next
	head.next = temp
	temp.prev = head
	temp.next = d


def addNode(head, p, data):
	curr = head
	for i in range(p):
		curr = curr.next
	tmp = Node(data)
	if curr.next:
		curr.next.prev = tmp
		tmp.next = curr.next
		tmp.prev = curr
		curr.next = tmp
	else:
		curr.next = tmp
		tmp.prev = curr
	return head


def addNode(head, pos, data):
	temp = Node(data)
	if pos == 0:
		if head.next is None:
			head.next = temp
			temp.prev = head
			return head
		t2 = head.next
		temp.next = t2
		t2.prev = temp
		head.next = temp
		temp.prev = head
		return head
	curr = head.next
	c = 0
	while c != pos - 1:
		c += 1
		curr = curr.next
	if curr.next is None:
		curr.next = temp
		temp.prev = curr
		return head
	t2 = curr.next
	t2.prev = temp
	curr.next = temp
	temp.prev = curr
	temp.next = t2
	return head


def addNode(head, p, data):
	temp = head
	while p != 0:
		temp = temp.next
		p -= 1
	n = Node(data)
	if temp.next is None:
		n.prev = temp
		temp.next = n
	else:
		n.next = temp.next
		temp.next = n
		temp.next.prev = n
		n.prev = temp


def addNode(head, p, data):
	temp = head
	count = 0
	while count < p and temp.next:
		count += 1
		temp = temp.next
	a = temp.next
	temp.next = Node(data)
	temp.next.prev = temp
	temp = temp.next
	temp.next = a
	return head


def addNode(head, p, data):
	temp = Node(data)
	if head is None:
		return temp
	else:
		curr = head
		for _ in range(pos):
			if curr is None:
				return head
			curr = curr.next
		next = curr.next
		curr.next = temp
		temp.prev = curr
		if next:
			next.prev = temp
			temp.next = next
		return head


def addNode(head, p, data):
	if not head:
		return Node(data)
	temp = head
	cur = 0
	while True:
		if cur == p:
			break
		temp = temp.next
		cur += 1
	node = Node(data)
	if temp.next is not None:
		node.next = temp.next
		temp.next.prev = node
	temp.next = node
	node.prev = temp
	return head


def addNode(head, p, data):
	c = 0
	cur = head
	while c < p:
		c += 1
		cur = cur.next
	t = Node(data)
	if cur is None:
		return t
	t.next = cur.next
	t.prev = cur
	cur.next = t
	if t.next is not None:
		t = t.next.prev


def addNode(head, p, data):
	node = Node(data)
	temp = head
	prev = None
	if p == 0:
		temp = head.next
		head.next = node
		node.prev = head
		node.next = temp
		return head
	c = 0
	while p >= c and temp:
		c += 1
		prev = temp
		temp = temp.next
	prev.next = node
	node.prev = prev
	node.next = temp
	return head


def addNode(head, p, data):
	new_node = Node(data)
	counter = 0
	temp = head
	while temp and counter < p:
		temp = temp.next
		counter += 1
	new_node.next = temp.next
	temp.next = new_node
	if new_node.next:
		new_node.next.prev = new_node
	new_node.prev = temp


def addNode(head, p, data):
	curNode = head
	for i in range(p):
		curNode = curNode.next
	newNode = Node(data)
	if curNode.next:
		curNode.next.prev = newNode
		newNode.next = curNode.next
		newNode.prev = curNode
		curNode.next = newNode
	else:
		curNode.next = newNode
		newNode.prev = curNode


def addNode(head, p, data):
	new_node = Node(data)
	curr_node = head
	for i in range(p):
		curr_node = curr_node.next
	if curr_node.next:
		curr_node.next.prev = new_node
		new_node.next = curr_node.next
		new_node.prev = curr_node
		curr_node.next = new_node
	else:
		curr_node.next = new_node
		new_node.prev = curr_node


def addNode(head, p, data):
	temp = Node(data)
	curr = head
	for ele in range(p):
		curr = curr.next
	if curr.next is None:
		curr.next = temp
		temp.prev = curr
		return head
	temp.next = curr.next
	curr.next.prev = temp
	curr.next = temp
	temp.prev = curr
	return head


def addNode(head, p, data):
	new = Node(data)
	curr = head
	for _ in range(p):
		curr = curr.next
	new.next = curr.next
	if curr.next:
		curr.next.prev = new
	new.prev = curr
	curr.next = new
	return head


def addNode(head, p, data):
	if head == None:
		return head
	count = -1
	curr = head
	while curr:
		count += 1
		curr = curr.next
	if p > count:
		return head
	node = Node(data)
	if p == count:
		curr = head
		while curr.next:
			curr = curr.next
		curr.next = node
		node.prev = curr
		return head
	if p == 0:
		node.next = head.next
		head.next = node
		return head
	curr = head
	count = 0
	while count != pos:
		count += 1
		curr = curr.next
	node.next = curr.next
	curr.next = node
	return head


def addNode(head, p, data):
	t = head
	c = 0
	while c != p:
		t = t.next
		c = c + 1
	x = Node(data)
	x.next = t.next
	x.prev = t
	t.next = x


def addNode(head, p, data):
	temp = head
	if head == None:
		return None
	k = 0
	while k < p:
		temp = temp.next
		k += 1
	newnode = Node(data)
	newnode.next = temp.next
	temp.next = newnode
	newnode.prev = temp
	return head


def addNode(head, p, data):
	newNode = Node(data)
	curr = head
	while p > 0:
		p -= 1
		curr = curr.next
	if p > 0:
		return head
	if curr.next == None:
		curr.next = newNode
		newNode.prev = curr
		return head
	newNode.next = curr.next
	curr.next.prev = newNode
	curr.next = newNode
	newNode.prev = curr
	return head


def addNode(head, p, data):
	temp = head
	cnt = 0
	while cnt != p:
		temp = temp.next
		cnt += 1
	ex = temp.next
	temp.next = Node(data)
	temp.next.prev = temp
	temp.next.next = ex
	if ex:
		ex.prev = temp.next


def addNode(head, p, data):
	temp = head
	for i in range(p):
		temp = temp.next
	curr = Node(data)
	curr.prev = temp
	curr.next = temp.next
	temp.next = curr


def addNode(head, p, data):
	count = 0
	temp = head
	while temp != None:
		if count == p:
			temp1 = Node(data)
			temp1.next = temp.next
			temp1.prev = temp
			temp.next = temp1
			return head
		temp = temp.next
		count = count + 1


def addNode(head, p, data):
	start = head
	cnt = 0
	while start:
		if cnt == p:
			newNode = Node(data)
			newNode.next = start.next
			newNode.prev = start
			start.next = newNode
			break
		if start == None:
			break
		cnt += 1
		start = start.next
	return head


def addNode(head, p, data):
	newNode = Node(data)
	if p == 0:
		newNode.prev = head
		newNode.next = head.next
		head.next = newNode
		if newNode.next is not None:
			newNode.next.prev = newNode
		return head
	else:
		cnt = 0
		start = head
		while start.next is not None:
			if cnt == p:
				newNode.prev = start
				newNode.next = start.next
				start.next = newNode
				newNode.next.prev = newNode
				return head
			start = start.next
			cnt += 1
		if cnt == p:
			newNode.prev = start
			start.next = newNode
			return head
		else:
			print('Position out of range')
			return head


def addNode(head, p, data):
	n = Node(data)
	pos = 0
	temp = head
	if head == None:
		head = n
		return
	while pos != p:
		temp = temp.next
		pos += 1
	n.next = temp.next
	n.prev = temp
	temp.next = n


def addNode(head, p, data):
	x = 0
	t = head
	node = Node(data)
	while x < p and t is not None:
		t = t.next
		x = x + 1
	t1 = t.next
	t.next = node
	node.next = t1
	node.prev = t
	if t1 is not None:
		t1.prev = node
	return head


def addNode(head, p, data):
	tmp = head
	c = 0
	while tmp:
		if c == p:
			break
		tmp = tmp.next
		c += 1
	n = Node(data)
	n.next = tmp.next
	if tmp.next:
		tmp.next.prev = n
	tmp.next = n
	n.prev = tmp
	return head


def addNode(head, p, data):
	curr = head
	count = 0
	while p:
		p -= 1
		curr = curr.next
	temp = curr.next
	newnode = Node(data)
	curr.next = newnode
	newnode.prev = curr
	curr.next.next = temp
	if curr.next.next:
		curr.next.next.prev = newnode
	return head


def addNode(head, p, data):
	i = 0
	current_node = head
	while current_node is not None:
		if i == p:
			new_node = Node(data)
			if current_node.next is None:
				current_node.next = new_node
				new_node.prev = current_node
			else:
				new_node.next = current_node.next
				new_node.prev = current_node
				current_node.next.prev = new_node
				current_node.next = new_node
		current_node = current_node.next
		i = i + 1


def addNode(head, p, data):
	curr = head
	temp = Node(data)
	for i in range(p):
		curr = curr.next
	nxt = curr.next
	curr.next = temp
	temp.prev = curr
	temp.next = nxt
	if nxt:
		nxt.prev = temp
	return head


def addNode(head, p, data):
	for _ in range(p):
		head = head.next
	temp = head.next
	head.next = Node(data)
	head.next.prev = head
	if temp:
		head.next.next = temp
		temp.prev = head.next
	return