Geek is learning data structures and is familiar with linked lists, but he's curious about how to access the previous element in a linked list in the same way that we access the next element. His teacher explains doubly linked lists to him.
Given an integer array arr of size n. Construct the doubly linked list from arr and return the head of it.
Example 1:
Input:
n = 5
arr = [1,2,3,4,5]
Output:
1 2 3 4 5
Explanation: Linked list for the given array will be 1<->2<->3<->4<->5.
Example 2:
Input:
n = 1
arr = [1]
Output:
1
Explanation: Linked list for the given array will be 1.
Constraints:
1 <= n <= 10^{5}
1 <= arr[i] <= 100
Your Task:
You don't need to read input or print anything. Your task is to complete the function constructDLL() which takes arr[] as input parameters and returns the head of the Linked List.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)

Source: geeksforgeeks | Difficulty: EASY

Starter code: #User function Template for python3



'''

# Node Class

	class Node:

	    def __init__(self, data):   # data -> value stored in node

	        self.data = data

	        self.next = None

	        self.prev = None

'''

class Solution:

    def constructDLL(self, arr):

        # Code here

Solutions:
class Solution:

	def constructDLL(self, arr):
		curr = Node(arr[0])
		head = curr
		for i in range(1, len(arr)):
			temp = Node(arr[i])
			head.next = temp
			temp.prev = head
			head = temp
		return curr


class Solution:

	def constructDLL(self, arr):
		temp = Node(None)
		head = temp
		for val in arr:
			newNode = Node(val)
			head.next = newNode
			newNode.prev = head
			head = head.next
		return temp.next


class Solution:

	def constructDLL(self, arr):
		temp = curr = Node(None)
		for i in arr:
			newNode = Node(i)
			curr.next = newNode
			curr = curr.next
		return temp.next


class Solution:

	def constructDLL(self, arr):
		head = Node(arr[0])
		itr = head
		for i in range(1, len(arr)):
			cur = Node(arr[i])
			itr.next = cur
			cur.prev = itr
			itr = cur
		return head


class Solution:

	def constructDLL(self, arr):
		dummy = Node(None)
		p = dummy
		i = 0
		while i < len(arr):
			N = Node(arr[i])
			dummy.next = N
			N.prev = dummy
			dummy = dummy.next
			i += 1
		return p.next


class Solution:

	def constructDLL(self, arr):
		head = currNode = Node(None)
		for ele in arr:
			newNode = Node(ele)
			newNode.prev = currNode
			currNode.next = newNode
			currNode = currNode.next
		return head.next


class Solution:

	def constructDLL(self, arr):
		self.head = None
		self.prev = None
		self.next = None
		if len(arr) == 0:
			return None
		self.head = Node(arr[0])
		a = self.head
		for i in range(1, len(arr)):
			a.next = Node(arr[i])
			a.next.prev = a
			a = a.next
		return self.head


class Solution:

	def constructDLL(self, arr):
		t = Node(arr[0])
		final = t
		q = t
		for x in arr[1:]:
			t.next = Node(x)
			t.prev = q
			q = t
			t = t.next
		return final


class Solution:

	def constructDLL(self, arr):
		prev = None
		head = None
		for val in arr:
			node = Node(val)
			if prev is not None:
				prev.next = node
				node.prev = prev
			else:
				head = node
			prev = node
		return head


class Solution:

	def constructDLL(self, arr):
		if not arr:
			return None
		head = Node(arr[0])
		curr = head
		for i in range(1, len(arr)):
			new_node = Node(arr[i])
			curr.next = new_node
			new_node.prev = curr
			curr = curr.next
		return head


class Solution:

	def constructDLL(self, arr):
		mylist = []
		for i in range(0, len(arr)):
			temp = Node(arr[i])
			mylist.append(temp)
			if i == 0:
				head = temp
			elif i == len(arr) - 1:
				mylist[i - 1].next = temp
				temp.prev = mylist[i - 1]
				temp.next = None
			else:
				temp.prev = mylist[i - 1]
				mylist[i - 1].next = temp
		return head


class Solution:

	def constructDLL(self, arr):
		h = Node(arr[0])
		p = h
		for i in range(1, len(arr)):
			n = Node(arr[i])
			p.next = n
			n.prev = p
			p = n
		return h


class Node:

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

class Solution:

	def constructDLL(self, arr):
		if not arr:
			return None
		head = Node(arr[0])
		tail = head
		for i in range(1, len(arr)):
			current = Node(arr[i])
			current.prev = tail
			tail.next = current
			tail = current
		return head


class Solution:

	def constructDLL(self, arr):
		self.head = None
		self.last = None
		for i in range(len(arr)):
			if self.head == None:
				self.head = Node(arr[i])
				self.last = self.head
			else:
				self.last.next = Node(arr[i])
				self.last = self.last.next
		return self.head


class Solution:

	def constructDLL(self, arr):
		dummy = Node(0)
		prev = dummy
		for ele in arr:
			temp = Node(ele)
			temp.prev = prev
			prev.next = temp
			prev = temp
		dummy.next.prev = None
		return dummy.next


class Solution:

	def constructDLL(self, arr):
		(head, last) = (None, None)
		for num in arr:
			node = Node(num)
			if not head:
				head = node
				last = node
			else:
				last.next = node
				node.prev = last
				last = last.next
		return head


class Solution:

	def __init__(self):
		self.head = None
		self.tail = None

	def constructDLL(self, arr):
		for i in arr:
			newNode = Node(i)
			if not self.head:
				self.head = newNode
				self.tail = newNode
			else:
				self.tail.next = newNode
				newNode.previous = self.tail
				self.tail = newNode
		return self.head


class Solution:

	def constructDLL(self, arr):
		head = Node(arr[0])
		t = head
		for i in arr[1:]:
			t.next = Node(i)
			t.next.prev = t
			t = t.next
		return head


class Solution(object):

	def constructDLL(self, nums):
		dummy = curr = Node(None)
		for val in nums:
			newNode = Node(val)
			curr.next = newNode
			newNode.prev = curr
			curr = curr.next
		return dummy.next


class Solution:

	def constructDLL(self, arr):
		prev = None
		head = None
		for i in range(len(arr)):
			node = Node(arr[i])
			if not prev:
				head = node
			else:
				node.prev = prev
				prev.next = node
			prev = node
		return head


class Solution:

	def constructDLL(self, arr):
		temp = None
		head = None
		for i in arr:
			newNode = Node(i)
			if head == None:
				head = newNode
			else:
				newNode.prev = temp
				newNode.prev.next = newNode
			temp = newNode
		return head


class Solution:

	def constructDLL(self, arr):
		prevs = None
		dummy = Node(0)
		head = dummy
		for i in arr:
			n = Node(i)
			n.prev = prevs
			prevs = n
			head.next = n
			head = head.next
		return dummy.next


class Solution:

	def constructDLL(self, arr):
		for i in range(len(arr)):
			if i == 0:
				node = Node(arr[i])
				head = node
			else:
				node.next = Node(arr[i])
				node.next.prev = Node(arr[i - 1])
				node = node.next
		return head


class Solution:

	def constructDLL(self, arr):
		head = Node(arr[0])
		originalhead = head
		for val in arr[1:]:
			head.next = Node(val)
			Node(val).prev = head
			head = head.next
		return originalhead


class Solution:

	def constructDLL(self, arr):
		dll_arr = []
		for i in range(len(arr)):
			node = Node(arr[i])
			dll_arr.append(node)
		for i in range(len(dll_arr)):
			if i < len(dll_arr) - 1:
				dll_arr[i].next = dll_arr[i + 1]
			if i > 0:
				dll_arr[i].prev = dll_arr[i - 1]
		return dll_arr[0]


class Solution:

	def constructDLL(self, arr):
		head = Node(arr[0])
		temp = head
		prev = None
		for i in arr:
			curr = Node(i)
			temp.next = curr
			curr.prev = temp
			temp = temp.next
		return head.next


class Solution:

	def constructDLL(self, arr):
		head = Node(arr[0])
		tmp = head
		for i in range(1, len(arr)):
			ins = Node(arr[i])
			tmp.next = ins
			ins.prev = tmp
			tmp = ins
		return head


class Solution:

	def constructDLL(self, arr):
		res = Node(arr[0])
		res.next = None
		temp = res
		for i in arr[1:]:
			i = Node(i)
			temp.next = i
			temp = temp.next
			temp.prev = i
		return res


class Solution:

	def constructDLL(self, arr):
		head = None
		temp = None
		for i in range(len(arr)):
			if head is None:
				head = Node(arr[i])
				temp = head
			else:
				cur = Node(arr[i])
				cur.prev = temp
				temp.next = cur
				temp = cur
		return head


class Solution:

	def constructDLL(self, arr):
		head = Node(0)
		cur = head
		for i in arr:
			n = Node(i)
			cur.next = n
			n.prev = cur
			cur = cur.next
		head = head.next
		return head


class Solution:

	def constructDLL(self, arr):
		head = Node(arr[0])
		if len(arr) == 1:
			return head
		curr = head
		for node in arr[1:]:
			newNode = Node(node)
			curr.next = newNode
			newNode.prev = curr
			curr = newNode
		return head


class Solution:

	def constructDLL(self, arr):
		t = Node(arr[0])
		a = t
		for i in range(1, len(arr)):
			s = Node(arr[i])
			t.next = s
			s.prev = t
			t = t.next
		return a


class Solution:

	def __init__(self):
		self.head = None
		self.tail = None

	def constructDLL(self, array):
		for item in array:
			newnode = Node(item)
			if self.head == None:
				self.head = newnode
				self.tail = newnode
			else:
				self.tail.next = newnode
				newnode.prev = self.tail
				self.tail = newnode
		return self.head


class Solution:

	def constructDLL(self, arr):
		h = Node(data=arr[0])
		x = h
		for i in range(1, len(arr)):
			y = Node(data=arr[i])
			x.next = y
			y.prev = x
			x = x.next
		return h


class Solution:

	def constructDLL(self, arr):
		head = Node(arr[0])
		start = head
		prev = head
		for i in range(1, len(arr)):
			num = arr[i]
			start.next = Node(num)
			start = start.next
			start.prev = prev
			prev = prev.next
		return head


class Solution:

	def constructDLL(self, arr):
		d = Node(-1)
		p = d
		i = 0
		while i < len(arr):
			d.next = Node(arr[i])
			d = d.next
			i = i + 1
		return p.next


class Solution:

	def constructDLL(self, arr):
		dummy = Node(0)
		prev = dummy
		for i in arr:
			temp = Node(i)
			prev.next = temp
			temp.prev = prev
			prev = temp
		return dummy.next


class Solution:

	def constructDLL(self, arr):
		self.head = None
		if not arr:
			return
		n = Node(arr[0])
		self.head = n
		temp = self.head
		for i in range(1, len(arr)):
			n = Node(arr[i])
			temp.next = n
			n.prev = temp
			temp = n
		return self.head


class Solution:

	def constructDLL(self, arr):
		if not arr:
			return None
		head = Node(arr[0])
		start = head
		for i in range(1, len(arr)):
			newNode = Node(arr[i])
			newNode.prev = start
			start.next = newNode
			start = newNode
		return head


class Solution:

	def constructDLL(self, arr):
		head = tail = None
		for ele in arr:
			newNode = Node(ele)
			if head == None:
				head = tail = newNode
			else:
				tail.next = newNode
				newNode.prev = tail
				tail = newNode
		return head


class Solution:

	def constructDLL(self, arr):
		self.head = None
		last = None
		for i in range(n):
			if self.head == None:
				self.head = Node(arr[0])
				last = self.head
			else:
				last.next = Node(arr[i])
				last.next.prev = last
				last = last.next
		return self.head


class Solution:

	def constructDLL(self, arr):
		head = Node(0)
		start = head
		for i in range(len(arr)):
			temp = Node(arr[i])
			temp.prev = head
			head.next = temp
			head = head.next
		start.next.prev = None
		return start.next


class Solution:

	def constructDLL(self, arr):
		self.head = Node(arr[0])
		currNode = self.head
		for i in range(1, len(arr)):
			x = Node(arr[i])
			currNode.next = x
			x.prev = currNode
			currNode = currNode.next
		return self.head


class Solution:

	def constructDLL(self, arr):
		head = None
		for data in arr:
			if not head:
				head = Node(data)
				startingPoint = head
			else:
				prev = head
				head.next = Node(data)
				head = head.next
				head.pre = prev
		return startingPoint


class Solution:

	def constructDLL(self, arr):
		new = newhead = Node(arr[0])
		for i in range(1, len(arr)):
			temp = Node(arr[i])
			new.next = temp
			temp.prev = new
			new = new.next
		return newhead


class Solution:

	def constructDLL(self, arr):
		head = tail = None
		prev = None
		for x in arr[::-1]:
			node = Node(x)
			node.next = head
			node.prev = prev
			if head is not None:
				head.prev = node
			head = node
			if tail is None:
				tail = node
			prev = node
		return head


class Solution:

	def constructDLL(self, arr):
		if len(arr) == 0:
			return NULL
		head = Node(arr[0])
		temp = head
		for i in range(1, len(arr)):
			b = Node(arr[i])
			head.next = b
			b.prev = head
			head = head.next
		return temp


class Node:

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

class Solution:

	def constructDLL(self, arr):
		head = Node(None)
		curr = head
		for i in range(len(arr)):
			curr.next = Node(arr[i])
			curr.prev = curr
			curr = curr.next
		return head.next


class Solution:

	def constructDLL(self, arr):
		head = curr = Node(arr[0])
		arr.pop(0)
		for x in arr:
			post = Node(x)
			curr.next = post
			post.prev = curr
			curr = post
		return head


class Solution:

	def constructDLL(self, arr):
		head = Node(arr[0])
		ans = head
		for item in arr[1:]:
			new_node = Node(item)
			new_node.prev = head
			head.next = new_node
			head = head.next
		return ans


class Solution:

	def constructDLL(self, arr):
		head = Node(arr[0])
		previous = head
		j = 0
		for i in range(1, len(arr)):
			j += 1
			previous.next = Node(arr[i])
			previous.next.prev = previous
			if j == 1:
				head = previous
			previous = previous.next
		return head


class Solution:

	def constructDLL(self, arr):
		head = Node(arr[0])
		curr = head
		prev = curr
		for i in arr[1:]:
			node = Node(i)
			curr.next = node
			curr.prev = prev
			prev = curr.prev
			curr = curr.next
		return head


class Solution:

	def constructDLL(self, arr):
		head = None
		curr = None
		for i in arr:
			prev = curr
			curr = Node(i)
			if not head:
				head = curr
			if prev:
				prev.next = curr
			curr.prev = prev
		return head


class Solution:

	def constructDLL(self, arr):
		temp = head = None
		for d in arr:
			if temp == None:
				temp = Node(d)
				temp.prev = None
				head = temp
			else:
				x = temp
				temp = Node(d)
				x.next = temp
				temp.prev = x
		return head


class Solution:

	def constructDLL(self, arr):
		dummy = Node(0)
		head = dummy
		for i in arr:
			new_node = Node(i)
			new_node.prev = dummy
			dummy.next = new_node
			dummy = dummy.next
		return head.next


class Solution:

	def constructDLL(self, arr):
		head = None
		curr_node = head
		for ele in arr:
			new_node = Node(ele)
			if head == None:
				head = new_node
				new_node.prev = head
				curr_node = head
			else:
				curr_node.next = new_node
				new_node.prev = curr_node
				curr_node = curr_node.next
		return head