Python Program to Add Elements to the First and Last Positions of a Linked List

In Python, a linked list is a linear data structure consisting of a series of nodes, each of which contains a value and a reference to the next node in the chain.

In this article, we’ll discuss how to add an element to the first and last position of a linked list in Python.

Linked Lists in Python

It’s similar to an array, but in an array, data is stored in consecutive memory locations, whereas in a linked list, data isn’t constrained to this condition. This means that data isn’t stored one after another, but rather in a random order in memory.

This raises the question of how we access elements in a linked list. The answer is straightforward: in a linked list, one element points to another until we reach the end of the list.

The beginning and end of a list are considered special locations. The beginning of a list is called the head, and it points to the first element. The last element is special because it points to NULL.

Head -> data_1 -> data_2 -> … -> data_n -> NULL

Now that we know how to access the beginning and end of a linked list, let’s look at how to iterate through the elements and access the list’s data.

Traversing a linked list is very simple. We simply start at the beginning and access the next node; we keep doing this until we find a node whose next node is NULL. To access the data within a node, we use the arrow operator, “->”.

Head->data

Now that we have all the necessary understanding, we can begin to approach this problem.

Adding Elements to the Beginning

To add data to the beginning of a linked list, we must consider the head of the list. Whenever we add a node to the beginning of a linked list, the list is modified, and the newly added node becomes the first node/head of the linked list.

Algorithm

Step 1 – Create a new node

Step 2 – Add data to the newly created node

Step 3 – Update the new node’s link to point to the current head node

Step 4 – Now make the head pointer equal to the newly created node

Note – The order of these steps is crucial, because if you make the newly created node the head node first, we won’t be able to update the new node’s link, and the new node would ideally point to the previous head node.

Example

class Node:
   def __init__(self, data):
      self.dataPart = data
      self.nextNode = None
class LinkedList:
   def __init__(self):
      self.headNode = None
   def showList(self):
      n = self.headNode
      while n is not None:
         print(n.dataPart, end='-')
         n = n.nextNode
      print('')
   def addBeginList(self, data):
      tempNode = Node(data)
      tempNode.nextNode = self.headNode
      self.headNode = tempNode
newLinkedList = LinkedList()
print("Printing the list before adding element: ")
newLinkedList.showList()
newLinkedList.addBeginList(10)
newLinkedList.addBeginList(25)
print("Printing the elements after adding at the beginning of the list")
newLinkedList.showList()

Output

Printing the list before adding any element:

Printing the elements after adding at the beginning of the list
25-10-

Adding Elements at the End

Appending an element at the end is logically different from adding it at the beginning of a list. This time, we need to access the last node of the list instead of the first, which is the head.

The problem now is to check whether the list we are adding the element to is empty or already has some elements.

If the list is empty, the new node will be the first node of the list, while in other cases, it will be the last node. To do this, we need to check whether the head node is None. If the head is None, the list is considered empty; otherwise, it is not empty.

Algorithm

Step 1 – Create a new node.

Step 2 – Add data to the node’s data section.

Step 3 – Ensure the newly created node’s next node points to a None or Null pointer.

Step 4 – If the list is empty, make the newly created node the head node.

Step 5 – Otherwise, traverse to the end of the list, i.e., the last node.

Step 6 – Set the next node of the last node to the newly created node.

Example

class Node:
   def __init__(self, data):
      self.dataPart = data
      self.nextNode = None
class LinkedList:
   def __init__(self):
      self.headNode = None
   def showList(self):
      n = self.headNode
      while n is not None:
         print(n.dataPart, end='-')
         n = n.nextNode
      print("")
   def addEndList(self, data):
      tempNode = Node(data)
      if self.headNode is None:
         self.headNode = tempNode
      else:
         n = self.headNode
         while n.nextNode is not None:
            n = n.nextNode
            n.nextNode = tempNode
newLinkedList = LinkedList()
print("Printing the list before insertion: ")
newLinkedList.showList()
newLinkedList.addEndList(25)
newLinkedList.addEndList(10)
print("Printing the list after adding elements at the end of the list : ")
newLinkedList.showList()

输出

Printing the list before insertion :

Printing the list after adding elements at the end of the list :
25-10-

Conclusion

In this article, we discussed how to use Python classes to implement a linked list and how to add elements to a linked list. We focused on adding elements to the beginning and end of a list.