Python Tutorial

Introduction Python Features Python Applications System requirements for Python Python Installation Python Examples Python Basics Python Indentation Python Variables Python Data Types Python IDE Python Keywords Python Operators Python Comments Python Pass Statement

Python Conditional Statements

Python if Statement Python elif Statement Python If-else statement Python Switch Case

Python Loops

Python for loop Python while loop Python Break Statement Python Continue Statement Python Goto Statement

Python Arrays

Python Array Python Matrix

Python Strings

Python Strings Python Regex

Python Built-in Data Structure

Python Lists Python Tuples Python Lists vs Tuples Python Dictionary Python Sets

Python Functions

Python Function Python min() function Python max() function Python User-define Functions Python Built-in Functions Python Recursion Anonymous/Lambda Function in Python python apply() Function Python lambda() Function

Python File Handling

Python File Handling Python Read CSV Python Write CSV Python Read Excel Python Write Excel Python Read Text File Python Write Text File Read JSON File in Python

Python Exception Handling

Python Exception Handling Python Errors and exceptions Python Assert

Python OOPs Concept

OOPs Concepts in Python Classes & Objects in Python Inheritance in Python Polymorphism in Python Python Encapsulation Python Constructor Python Super function Python Static Method Static Variables in Python Abstraction in Python

Python Iterators

Iterators in Python Yield Statement In Python

Python Generators

Python Generator

Python Decorators

Python Decorator

Python Functions and Methods

Python Built-in Functions Python String Methods Python List Methods Python Dictionary Methods Python Tuple Methods Python Set Methods

Python Modules

Python Modules Python Datetime Module Python Math Module Python Import Module Python Time Module Python Random Module Python Calendar Module CSV Module in Python Python Subprocess Module Python Subprocess

Python MySQL

Python MySQL Python MySQL Client Update Operation Delete Operation Database Connection Creating new Database using Python MySQL Creating Tables Performing Transactions

Python MongoDB

Python MongoDB

Python SQLite

Python SQLite

Python Data Structure Implementation

Python Stack Python Queue Python Linked List Python Hash Table Python Graph

Python Advance Topics

Speech Recognition in Python Face Recognition in Python Python Linear regression Python Rest API Python Command Line Arguments Python JSON Python Virtual Environment Type Casting in Python Python Collections Python Commands Python Data Visualization Python Debugger Python DefaultDict Python Enumerate

Python 3

Anaconda in Python 3 Anaconda python 3 installation for windows 10 List Comprehension in Python3

Misc

Python PPTX Python Pickle Python Seaborn Python Coroutine Python EOL Python Infinity Python math.cos and math.acos function Python Project Ideas Based On Django Reverse a String in Python Reverse a Number in Python Python Word Tokenizer Python Trigonometric Functions Python try catch exception GUI Calculator in Python Implementing geometric shapes into the game in python Installing Packages in Python Python Try Except Python Sending Email Socket Programming in Python Python CGI Programming Python Data Structures Python abstract class Python Compiler Python K-Means Clustering NSE Tools In Python Operator Module In Python Palindrome In Python Permutations in Python Pillow Python introduction and setup Python Functionalities of Pillow Module Python Argmin Python whois Python JSON Schema Python lock Return Statement In Python Reverse a sentence In Python tell() function in Python Why learn Python? Write Dictionary to CSV in Python Write a String in Python Binary Search Visualization using Pygame in Python Latest Project Ideas using Python 2022 Closest Pair of Points in Python ComboBox in Python Python vs R Best resources to learn Numpy and Pandas in python Check Letter in a String Python Python Console Python Control Statements Convert Float to Int in Python using Pandas Difference between python list and tuple Importing Numpy in Pycharm Python Key Error Python NewLine Python tokens and character set Python Strong Number any() Keyword in python Best Database in Python Check whether dir is empty or not in python Comments in the Python Programming Language Convert int to Float in Python using Pandas Decision Tree Classification in Python End Parameter in python __GETITEM__ and __SETITEM__ in Python Python Namespace Python GUI Programming List Assignment Index out of Range in Python List Iteration in Python List Index out of Range Python for Loop List Subtract in Python Python Empty Tuple Python Escape Characters Sentence to python vector Slicing of a String in Python Executing Shell Commands in Python Genetic Algorithm in python Get index of element in array in python Looping through Data Frame in Python Syntax of Map function in Python After Python What Should I Learn Python AIOHTTP Alexa Python Artificial intelligence mini projects ideas in python Artificial intelligence mini projects with source code in Python Find whether the given stringnumber is palindrome or not First Unique Character in a String Python Python Network Programming Python Interface Python Multithreading Python Interpreter Data Distribution in python Flutter with tensor flow in python Front end in python Iterate a Dictionary in Python Iterate a Dictionary in Python – Part 2 Allocate a minimum number of pages in python Assertion Errors and Attribute Errors in Python Checking whether a String Contains a Set of Characters in python Python Control Flow Statements *Args and **Kwargs in Python Bar Plot in Python Conditional Expressions in Python Function annotations() in Python How to Write a Configuration file in Python Image to Text in python import() Function in Python Import py file in Python Multiple Linear Regression using Python Nested Tuple in Python Python String Negative Indexing Reading a File Line by Line in Python Python Comment Block Base Case in Recursive function python ER diagram of the Bank Management System in python Image to NumPy Arrays in Python NOT IN operator in Python One Liner If-Else Statements in Python Sklearn in Python Python Ternary Operators Self in Python Python vs Java Python Modulo Python Packages Python Syntax Python Uses Python Bitwise Operators Python Identifiers Python Matrix Multiplication Python AND Operator Python Logical Operators Python Multiprocessing Python Unit Testing __init__ in Python Advantages of Python Is Python Case-sensitive when Dealing with Identifiers Python Boolean Python Call Function Python History Python Image Processing Python main() function Python Permutations and Combinations Difference between Input() and raw_input() functions in Python Conditional Statements in python Confusion Matrix Visualization Python Python Algorithms Python Modules List Difference between Python 2 and Python 3 Is Python Case Sensitive Method Overloading in Python Python Arithmetic Operators Assignment Operators in Python Is Python Object Oriented Programming language Division in Python Python exit commands Continue And Pass Statements In Python Colors In Python Convert String Into Int In Python Convert String To Binary In Python Convert Uppercase To Lowercase In Python Convert XML To JSON In Python Converting Set To List In Python Covariance In Python CSV Module In Python Decision Tree In Python Difference Between Yield And Return In Python Dynamic Typing In Python

How to

How to Substring a String in Python How to Iterate through a Dictionary in Python How to convert integer to float in Python How to reverse a string in Python How to take input in Python How to install Python in Windows How to install Python in Ubuntu How to install PIP in Python How to call a function in Python How to download Python How to comment multiple lines in Python How to create a file in Python How to create a list in Python How to declare array in Python How to clear screen in Python How to convert string to list in Python How to take multiple inputs in Python How to write a program in Python How to compare two strings in Python How to create a dictionary in Python How to create an array in Python How to update Python How to compare two lists in Python How to concatenate two strings in Python How to print pattern in Python How to check data type in python How to slice a list in python How to implement classifiers in Python How To Print Colored Text in Python How to develop a game in python How to print in same line in python How to create a class in python How to find square root in python How to import numy in python How to import pandas in python How to uninstall python How to upgrade PIP in python How to append a string in python How to open a file in python How to Open a file in python with Path How to run a Python file in CMD How to change the names of Columns in Python How to Concat two Dataframes in Python How to Iterate a List in Python How to learn python Online How to Make an App with Python

Sorting

Python Sort List Sort Dictionary in Python Python sort() function Python Bubble Sort

Programs

Factorial Program in Python Prime Number Program in Python Fibonacci Series Program in Python Leap Year Program in Python Palindrome Program in Python Check Palindrome In Python Calculator Program in Python Armstrong Number Program in Python Python Program to add two numbers Anagram Program in Python Even Odd Program in Python GCD Program in Python Python Exit Program Python Program to check Leap Year Operator Overloading in Python Pointers in Python Python Not Equal Operator Raise Exception in Python Salary of Python Developers in India What is a Script in Python

Python Linked List

Linked List

Linked lists non-contiguous linear data structure which is made up of nodes and used to store value and a pointer pointing to the next node. It is linked with each other through a pointer.

Linked lists are often used over arrays because of several reasons. The length of a linked list can vary concerning the need of the user. It is dynamically sized, unlike the array. We can increase or decrease its size as we need. In a linked list, we can insert elements very easily.

Every element of a linked list is known as a node, and each node contains two parts:

Data: It contains the data value in the node.

Next: It contains the pointer pointing to the next node.

There is also a concept of a head pointer, which points to the first node. In simple words, we can say that a linked list consists of a collection of nodes.

Advantages of using a linked list

  • It is dynamically sized, which mean increasing or decreasing its size as per our need.
  • Operations like insertion and deletion are very easy in a linked list.

Disadvantages of using a linked list

  • Linked list doesn’t allow random access, so we can’t access any element randomly in a linked list. We have to traverse all elements before we reach any specific element.
  • Linked list requires extra memory as compared to an array. It requires extra memory for the pointers stored along with the data value.
  • Linked lists are not cache-friendly.

Syntax of creating a node

class Node:
      # Function to initialize the node object
      def __init__ (self, data_val):
          self.data = data_val   # assign the data
          self.next = None         # set the next value as Null

Empty Linked List

An empty linked list is a linked list where the head pointer points to None.

Syntax of creating an empty linked list

class linkedList: 
   def __init__(self): 
        self.head=None

Creating a linked list

A linked list can be created by creating an object for the node and a class to use that object. Then we pass the appropriate values to the object node and start adding the nodes. Given below is an example of creating a single linked list with four data values.

In the below code, we are creating a linked list of four nodes.

class Node:
   def __init__(self, dataval=None):
      self.dataval = dataval
      self.nextval = None


class LinkedList:
   def __init__(self):
      self.headval = None


node1 = LinkedList()
node1.headval = Node("January")
e2 = Node("Feburary")
e3 = Node("March")
e4 = Node("April")
# Link first Node to second node
node1.headval.nextval = e2


# Link second Node to third node
e2.nextval = e3
# Link third Node to fourth node
e3.nextval = e4

Explanation:

In the above code, we have created an object node and then a class to use that object node. In the node class Node. We store the value and the next pointer. In the other class LinkedList(), we will create a linked list. After that, we will call the class and store the value.

Traversing a Linked List

class Node:
   def __init__(self, dataval=None):
      self.dataval = dataval
      self.nextval = None


class LinkedList:
   def __init__(self):
      self.headval = None
 
   def listprint(self):
      printval = self.headval
      while printval is not None:
         print (printval.dataval)
         printval = printval.nextval


node1 = LinkedList()
node1.headval = Node("January")
e2 = Node("Feburary")
e3 = Node("March")
e4 = Node("April")
# Link first Node to second node
node1.headval.nextval = e2


# Link second Node to third node
e2.nextval = e3
# Link third Node to fourth node
e3.nextval = e4
node1.listprint()

Output:

January
February
March
April

Explanation:

In the above code, we have created the linked list and added the four values in four nodes. Then we will add another block of code to print the values. We have defined a function name listprint( ) and will print all the value using the while loop.

Insertion at the beginning

Inserting an element at the beginning of a linked list is very easy because in this you can just create a new node and add the next pointer to the first node. In this, we don’t have to traverse the entire linked list. Hence, we can insert a new node at the beginning of a linked list in just O(1) complexity.

Example:

class Node:
   def __init__(self, dataval=None):
      self.dataval = dataval
      self.nextval = None


class LinkedList:
   def __init__(self):
      self.headval = None
   # Print the linked list
   def listprint(self):
      printval = self.headval
      while printval is not None:
         print (printval.dataval)
         printval = printval.nextval
   def AtBegining(self,newdata):
      NewNode = Node(newdata)


# Update the new nodes next val to existing node
      NewNode.nextval = self.headval
      self.headval = NewNode


node1 = LinkedList()
node1.headval = Node("July")
n2 = Node("August")
n3 = Node("September")


node1.headval.nextval = n2
n2.nextval = n3


node1.AtBegining("June")
node1.listprint()
 

Output:

June
July
August
Septemberer

Explanation:

In the above code, we have added another block of code for inserting the elements at the beginning of the linked list. We have used a function AtBeginning( ) to add the element at the start.

Insertion at the end

Inserting an element at the end of a single linked list can be done in a O(n) complexity. In this, we traverse the entire linked list, and then at the end, we add a new node by pointing the next value of the last node to the new node.

Example:

class Node:
   def __init__(self, dataval=None):
      self.dataval = dataval
      self.nextval = None


class LinkedList:
   def __init__(self):
      self.headval = None


# Function to add newnode
   def AtEnd(self, newdata):
      NewNode = Node(newdata)
      if self.headval is None:
         self.headval = NewNode
         return
      laste = self.headval
      while(laste.nextval):
         laste = laste.nextval
      laste.nextval=NewNode
# Print the linked list
   def listprint(self):
      printval = self.headval
      while printval is not None:
         print (printval.dataval)
         printval = printval.nextval


node1 = LinkedList()
node1.headval = Node("June")
e2 = Node("July")
e3 = Node("August")


node1.headval.nextval = e2
e2.nextval = e3


node1.AtEnd("September")


node1.listprint()

Output

June 
July
August
September

Explanation:

In the above code, firstly we have created a linked list and then we have used another function AtEnd( ) to add another element at the end.

Insertion in between two nodes

class Node:
   def __init__(self, dataval=None):
      self.dataval = dataval
      self.nextval = None


class LinkedList:
   def __init__(self):
      self.headval = None


# Function to add newnode
   def Inbetween(self,middle_node,newdata):
      if middle_node is None:
         print("The mentioned node is absent")
         return


      NewNode = Node(newdata)
      NewNode.nextval = middle_node.nextval
      middle_node.nextval = NewNode
# Print the linked list
   def listprint(self):
      printval = self.headval
      while printval is not None:
         print (printval.dataval)
         printval = printval.nextval


node1 = LinkedList()
node1.headval = Node("June")
e2 = Node("July")
e3 = Node("August")


node1.headval.nextval = e2
e2.nextval = e3


node1.Inbetween(node1.headval.nextval,"August")
node1.listprint()

Output

June 
July
August
September

Deleting a node

class Node:
class Node:
   def __init__(self, dataval=None):
      self.dataval = dataval
      self.nextval = None
class LinkedList:
   def __init__(self):
      self.headval = None
   def Atbegining(self, data_in):
      NewNode = Node(data_in)
      NewNode.next = self.head
      self.head = NewNode
# Function to remove node
   def RemoveNode(self, Removekey):
      HeadVal = self.head
         
      if (HeadVal is not None):
         if (HeadVal.data == Removekey):
            self.head = HeadVal.next
            HeadVal = None
            return
      while (HeadVal is not None):
         if HeadVal.data == Removekey:
            break
         prev = HeadVal
         HeadVal = HeadVal.next


      if (HeadVal == None):
         return


         prev.next = HeadVal.next
         HeadVal = None
# Print the linked list
   def listprint(self):
      printval = self.headval
      while printval is not None:
         print (printval.dataval)
         printval = printval.nextval


node1 = LinkedList()
node1.headval = Node("June")
n2 = Node("July")
n3 = Node("August")


node1.headval.nextval = n2
n2.nextval = n3


node1.RemoveNode("June")
node1.Listprint()

Output:

July
August



ADVERTISEMENT
ADVERTISEMENT