Python program: add elements to first and last position of linked list

In Python, a linked list is a linear data structure that consists of a series of nodes, each node containing a value and a reference to the next node in the linked list.

In this article, we will discuss how to add elements to the first and last position of a linked list in Python.

Linked List in Python

A linked list is a reference data structure used to store a set of elements. It is similar to an array in a way, but in an array, the data is stored in contiguous memory locations, whereas in a linked list, the data is not subject to this condition. This means that the data is not stored sequentially but in a random manner in memory.

This raises one question that is, how we can access the elements in a linked list? The answer is quite intuitive in linked list one element points to another till the end of the list.

The beginning and end of the list are treated as special positions. The beginning of the list is called the head, it points to the first element, and the last element is special in that 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 see how to iterate over the elements and access the data in the linked list.

Traversing the linked list is very simple, we only need to access the next node from the beginning; we repeat this process until we find a node whose next node is NULL. As for accessing data in a node, we use the arrow operator "->".

Head->data

Now we have all the necessary understanding to start solving this problem.

Add element at the beginning

To add the data at the beginning of the linked list, we must take into consideration the head of the linked list. Whenever we add a node at the beginning of the linked list, the linked list will be modified with the newly added node being the first node / head of the list.

Algorithm

Step 1 – Create the new node

Step 2 - Add data to the newly created node

Step 3 – Update the link of the new node and make it point to current head node

Step 4 - Now set the head pointer to the newly created node

NOTE - The order of these steps is very important because if you first set the newly created node as the head node, then we will not be able to update the new node's link, which ideally should 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-\

Add element at the end

Adding elements at the end, is logically different from adding at the beginning of the list. This time we need to access the last node of the list instead of the first node, i.e., head.

Now the problem is to check if the list to which we want to add elements is an empty list or if it already has some elements.

If the list is empty then the new node will be the first node for the list, and in the other case, it will be the last node. For that we need to check whether the head node is None or not. The list is treated empty of head is None, and not empty otherwise.

Algorithm

Step 1 – Create a new node.

Step 2 - Add data to the data section of the node.

Step 3 – Make sure the next node of the newly created node points to None or Null pointer.

Step 4 - If the list is empty, use the newly created node as the head node.

Step 5 - Else traverse to the end of list, 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()

Output

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 the linked list. We focused on adding elements at the beginning and end of the list.

The above is the detailed content of Python program: add elements to first and last position of linked list. For more information, please follow other related articles on the PHP Chinese website!