Data Structures and Algorithms in Python/

...

/

Insertion

Insertion

In this lesson, we'll learn how to insert elements in a linked list at different places.

We'll cover the following...

In the previous lesson, we defined our Node and LinkedList classes. In this lesson, we’ll implement the class methods to insert elements in a linked list:

  1. append
  2. prepend
  3. insert_after_node

Append #

The append method will insert an element at the end of the linked list. Below is an illustration which depicts the append functionality:

Now let’s move on to writing some code.

Press + to interact
class Node:
  def __init__(self, data):
    self.data = data
    self.next = None
class LinkedList:
  def __init__(self):
    self.head = None
  def append(self, data):
    new_node = Node(data)

We define a new_node using our Node class on line 11. It consists of the data and the next field. We pass in data to the append method, and the data field in new_node has the entry of data that we passed to the append method.

Empty Linked List Case #

For the append method, we also need to cater for the case if the linked list is empty.

Press + to interact
class Node:
  def __init__(self, data):
    self.data = data
    self.next = None
class LinkedList:
  def __init__(self):
    self.head = None
  def append(self, data):
    new_node = Node(data)
    if self.head is None:
      self.head = new_node
      return

In the above code, we check if the linked list is empty by checking the head of the linked list. If the self.head is None on line 12, it implies that it’s an empty linked list and there’s nothing there. The head pointer doesn’t point to anything at all, and therefore there is no node in the linked list. If there is no node in the linked list, we set the head pointer to the new_node ...

Access this course and 1400+ top-rated courses and projects.