Trusted answers to developer questions

Vamsi Dhananjay

Before we get into doubly linked lists, let’s discuss some basics.

First, let’s discuss what an array is. An **array**, is a collection of elements of the same data type that are present in adjacent memory locations. We can also say that elements in an array *are* contiguous.

A **list** a collection of elements of different data types that are *not* contiguous.

Note: The elements can be in different memory locations, but the references for these elements are stored in contiguous memory locations.

Think about an array as a collection of all the buildings on a given street or a collection of all fish in a fish tank. Whereas, a list can be thought about as a collection containing the Taj Mahal, Pacific Ocean, Bill Gates, and a football.

A **linked list** is a collection of nodes. Since linked lists can be noncontiguous, we use nodes to store the value of elements and create links between them so that they are in sequential order. Each node consists of pointers that link to the next node/next element in the list.

In *singly-linked lists*, we only use the next pointer in each node, but in doubly linked lists we also add a previous pointer that links each element to its previous element. This helps us to traverse in both directions.

Now, let’s create a doubly linked list in Python.

First, we will create a node class, then we will use it to build a doubly linked list class.

# Creating a node class class Node: def __init__(self, data): self.data = data #adding an element to the node self.next = None # Initally this node will not be linked with any other node self.prev = None # It will not be linked in either direction class DoublyLinkedList: def __init__(self): self.head = None # Initally there are no elements in the list

Doubly linked lists use the `head`

variable to refer to the first element and the `tail`

variable that refers to the last element of the list. With this in mind, we are going to implement basic linked list methods, like:

`push`

`pop`

`peek`

`insert`

# Creating a node class class Node: def __init__(self, data): self.data = data #adding an element to the node self.next = None # Initally this node will not be linked with any other node self.prev = None # It will not be linked in either direction # Creating a doubly linked list class class DoublyLinkedList: def __init__(self): self.head = None # Initally there are no elements in the list self.tail = None def push_front(self, new_data): # Adding an element before the first element new_node = Node(new_data) # creating a new node with the desired value new_node.next = self.head # newly created node's next pointer will refer to the old head if self.head != None: # Checks whether list is empty or not self.head.prev = new_node # old head's previous pointer will refer to newly created node self.head = new_node # new node becomes the new head new_node.prev = None else: # If the list is empty, make new node both head and tail self.head = new_node self.tail = new_node new_node.prev = None # There's only one element so both pointers refer to null def push_back(self, new_data): # Adding an element after the last element new_node = Node(new_data) new_node.prev = self.tail if self.tail == None: # checks whether the list is empty, if so make both head and tail as new node self.head = new_node self.tail = new_node new_node.next = None # the first element's previous pointer has to refer to null else: # If list is not empty, change pointers accordingly self.tail.next = new_node new_node.next = None self.tail = new_node # Make new node the new tail def peek_front(self): # returns first element if self.head == None: # checks whether list is empty or not print("List is empty") else: return self.head.data def peek_back(self): # returns last element if self.tail == None: # checks whether list is empty or not print("List is empty") else: return self.tail.data def pop_front(self): # removes and returns the first element if self.head == None: print("List is empty") else: temp = self.head temp.next.prev = None # remove previous pointer referring to old head self.head = temp.next # make second element the new head temp.next = None # remove next pointer referring to new head return temp.data def pop_back(self): # removes and returns the last element if self.tail == None: print("List is empty") else: temp = self.tail temp.prev.next = None # removes next pointer referring to old tail self.tail = temp.prev # make second to last element the new tail temp.prev = None # remove previous pointer referring to new tail return temp.data def insert_after(self, temp_node, new_data): # Inserting a new node after a given node if temp_node == None: print("Given node is empty") if temp_node != None: new_node = Node(new_data) new_node.next = temp_node.next temp_node.next = new_node new_node.prev = temp_node if new_node.next != None: new_node.next.prev = new_node if temp_node == self.tail: # checks whether new node is being added to the last element self.tail = new_node # makes new node the new tail def insert_before(self, temp_node, new_data): # Inserting a new node before a given node if temp_node == None: print("Given node is empty") if temp_node != None: new_node.prev = temp_node.prev temp_node.prev = new_node new_node.next = temp_node if new_node.prev != None: new_node.prev.next = new_node if temp_node == self.head: # checks whether new node is being added before the first element self.head = new_node # makes new node the new head

RELATED TAGS

python

community creator

CONTRIBUTOR

Vamsi Dhananjay

RELATED COURSES

View all Courses

Keep Exploring

Related Courses