How to insert and output nodes in python singly linked list? (code example)

How to insert and output nodes in python singly linked list? The following article will help you understand what a singly linked list is and how to perform some very basic operations on a singly linked list, such as insertion and output. I hope it will be helpful to you.

What is a singly linked list?

First of all, before understanding the singly linked list, we must understand what a node is.

Node is the building block of the linked list, which consists of two parts:

1. Data part: used to contain data

2. Address part: used to point to the next Pointer to the node location.

In a singly linked list, the address portion of each node contains information about the location of the next node; this forms a series of chains or links. The first node of the linked list is tracked by the head pointer; the last node points to None.

Let’s look at the diagram below to understand this better:

Note: In the above diagram, the last element 1 points to None. Even though these nodes are drawn contiguously with each other, they may or may not actually be in contiguous memory locations.

How to insert and output nodes in a singly linked list?

1. Create a singly linked list

First, you must create a node to create a singly linked list. To do this, we create a Node class using data and nextNode properties. As mentioned before, the data attribute will contain the data and nextNode will simply point to the next node in the linked list. We set the default value for nextNode to be None. You can use getter and setter methods to do this.

Now that the Node class has been created, it is time to create the LinkedList class. This has only one attribute, head. By default this will point to "None". If the header points to "None", it means that the linked list is empty. To keep track of the number of nodes in the linked list, we can add a size attribute to the LinkedList class and default it to 0.

2. Insert node

This is the method of LinkedList class. We can insert a new node anywhere in the linked list, but to keep the coding simple and efficient, we will always add new nodes to the beginning of the linked list; in other words, the head will always point to the most recently added node.

If we add a new node to the end of the list, we need to perform extra work to find the end of the list and then add it. This is a wasteful operation. However, this can be done if you maintain another pointer, let's call it tail pointer, pointing to the last node.

Below we introduce the former method, that is, how to insert a node at the beginning of the linked list.

Suppose we need to add 7 to the linked list, we need to perform the following steps:

● Create a node object, where 7 represents data, and the next node points to the head node

● Point the head pointer to this new node

Finally, increase the size attribute by 1. If the insertion is successful, return True. This is a good habit; this way, the user knows what happened.

3. Output node

This is the method of LinkedList class. To print the data in all nodes in the linked list, we need to iterate through one node at a time and print the data portion of each node.

Implementation code:

class Node:
   def __init__(self,data,nextNode=None):
       self.data = data
       self.nextNode = nextNode
   def getData(self):
       return self.data
   def setData(self,val):
       self.data = val
   def getNextNode(self):
       return self.nextNode
   def setNextNode(self,val):
       self.nextNode = val
class LinkedList:
   def __init__(self,head = None):
       self.head = head
       self.size = 0
   def getSize(self):
       return self.size
   def addNode(self,data):
       newNode = Node(data,self.head)
       self.head = newNode
       self.size+=1
       return True
       
   def printNode(self):
       curr = self.head
       while curr:
           print(curr.data)
           curr = curr.getNextNode()
myList = LinkedList()
print("Inserting")
print(myList.addNode(5))
print(myList.addNode(15))
print(myList.addNode(25))
print("Printing")
myList.printNode()
print("Size")
print(myList.getSize())

What are the advantages and disadvantages of singly linked lists?

Advantages:

● It is a dynamic data structure in which insertion and deletion are simple. Because we don't need to move the element. Just updating the next pointer will do the job.

● Stack and queue data structures can be easily implemented using linked lists.

Disadvantages

● The next pointer occupies additional memory.

●Cannot be accessed randomly. The linked list must be traversed from the beginning to reach a specific node.

The above is the entire content of this article, I hope it will be helpful to everyone's study. For more exciting content, you can pay attention to the relevant tutorial columns of the PHP Chinese website! ! !

The above is the detailed content of How to insert and output nodes in python singly linked list? (code example). For more information, please follow other related articles on the PHP Chinese website!