Singly Linked Lists in Python

A Singly Linked List is an ordered collection of data elements. It is a dynamic data structure, that is it can be of any length. It can store data of any type.

A Singly Linked List consists of two parts; the Node, and the link. The Node in turn has two sections; the data field (which holds the data), and the link field (which holds the link to the next element).
singly-linked-list

Singly Linked Lists contains links to only the next elements in the Linked Lists, thus making it traversable in only that direction.

Characteristics of a Singly Linked List

  • Ordered - Elements in a Singly Linked List are ordered
  • Mutable - Elements are mutable
  • Dynamic - The length of the Linked List is dynamic
  • Traversable - Singly Linked Lists are traversable in only one direction
  • Can store data of any type

Singly Linked List Methods

  • add() - Adds elements to the Linked List based on position
    • At the beginning - Changes the head Node
    • At the end - Changes the last Node
    • In the middle - Based on positional value
  • delete() - Deletes elements from the Linked List based on position or value
    • In the beginning - Deletes and reassigns the head Node
    • At the end - Deletes and reassigns the end Node
    • In the middle - Deletes an element based on position
    • Deletes a Node, based on the value
  • clear() - Empties the Linked List
  • empty() - Checks whether or not a Linked List is empty
  • display() - Displays the Linked List

The head variable holds the first or header element of the Linked List.

Implementing a Singly Linked List in Python

Singly Linked Lists can be implemented using Python by applying the object-oriented characteristic.

Singly Linked Lists can be implemented by the following steps:

  1. Defining the Node class which actually holds the data elements and the links to the next element
    class Node:
        def __init__(self, val):
            self.value = val
            self.next = None​
  2. Defining the Singly Linked List class
    class SLL:​
  3. Initializing the SLL class with the head variable
        def __init__(self):
            self.head = None​
  4. Defining the add() method
    def add(self, val):​
    1. Checking whether the Linked List is empty or not, if it is, then a single element is added
              if self.empty() is True:
                  self.head = Node(val)
                  print("Head value created")
                  return​
    2. Choosing from the three different methods available to add an element to the Linked List
      opt = int(input(
                  "Enter 1 to add a Node at the beginning\nEnter 2 to add a Node at the end\nEnter 3 to add a Node in the "
                  "middle::"))​
    3. Adding an element to the beginning of the Linked List
              if opt == 1:
                  a = Node(val)
                  a.next = self.head
                  self.head = a​
    4. Adding an element to the end of the Linked List
              elif opt == 2:
                  i = self.head
                  while i.next is not None:
                      i = i.next
                  i.next = Node(val)​
    5. Adding an element to the middle of a Linked List based on its position
              elif opt == 3:
                  pos = int(input("Enter the position ::"))
                  i = 1
                  n = self.head
                  f = n.next
                  flag = 0
                  while f is not None:
                      if i == pos:
                          flag = 1
                          break
                      f = f.next
                      n = n.next
                      i = i + 1
                  if flag == 1:
                      n.next = Node(val)
                      n.next.next = f
                  else:
                      print("Position not found")​
  5. Defining the delete() method which deletes elements from different positions of the Linked List
    def delete(self):​
    1. Checking whether or not the Linked List is empty and elements cannot be deleted from it
              if self.empty() is True:
                  print("Linked List empty")
                  return​
    2. Checking whether or not the existing element is the last element of the Linked List, and thus deleting it
              elif self.head.next is None:
                  self.head = None
                  return​
    3. Choosing the position to delete an element from the Linked List
      opt = int(input("Enter 1 to delete the beginning element\nEnter 2 to delete the last element\nEnter 3 to "
                              "delete elements in between ::"))​
    4. Deleting an element from the beginning of the Linked List
              if opt == 1:
                  self.head = self.head.next​
    5. Deleting an element from the end of the Linked List
              elif opt == 2:
                  n = self.head
                  while n.next.next is not None:
                      n = n.next
                  n.next = None​
    6. Deleting an element from the middle of the Linked List
              else:
                  op = int(input("Enter 1 to delete by position\nEnter 2 to delete by value ::"))​
      1. Based on position
                    if op == 1:
                        pos = int(input("Enter the position ::"))
                        i = 1
                        n = self.head
                        f = self.head.next
                        flag = 0
                        while f.next is not None:
                            if i == pos:
                                flag = 1
                                break
                            i = i + 1
                            n = n.next
                            f = f.next
                        if flag == 1:
                            n.next = f.next
                        else:
                            print("Position not found")
                            return​
      2. Based on value
                    else:
                        val = int(input("Enter the value you want to delete ::"))
                        n = self.head
                        f = self.head.next
                        flag = 0
                        while f.next is not None:
                            if f.value == val:
                                flag = 1
                                break
                            f = f.next
                            n = n.next
                        if flag == 1:
                            n.next = f.next
                        else:
                            print("Value not found")
                            return​
  6. Define the clear() method to remove all the elements from the Linked List
        def clear(self):
            self.head = None
            print("Linked List cleared")​
  7. Define the empty() method to find whether or not the Linked List is empty or the head variable is null
        def empty(self):
            if self.head is None:
                return True
            else:
                return False​
  8. Define the display() method which represents the Linked List in a user-comprehendible format
        def display(self):
            if self.empty() is True:
                print("Linked List empty")
                return
            print("THE LINKED LIST")
            print(self.head.value, " <== HEAD")
            n = self.head.next
            while n is not None:
                print(n.value)
                n = n.next
            print("Linked List ends")​
  9. After assembling the program, creating an instance, and defining a menu-driven program to manipulate the Singly Linked List
    class Node:
        def __init__(self, val):
            self.value = val
            self.next = None
    
    class SLL:
        def __init__(self):
            self.head = None
    
        def add(self, val):
            if self.empty() is True:
                self.head = Node(val)
                print("Head value created")
                return
            opt = int(input(
                "Enter 1 to add a Node at the beginning\nEnter 2 to add a Node at the end\nEnter 3 to add a Node in the "
                "middle::"))
            if opt == 1:
                a = Node(val)
                a.next = self.head
                self.head = a
            elif opt == 2:
                i = self.head
                while i.next is not None:
                    i = i.next
                i.next = Node(val)
            elif opt == 3:
                pos = int(input("Enter the position ::"))
                i = 1
                n = self.head
                f = n.next
                flag = 0
                while f is not None:
                    if i == pos:
                        flag = 1
                        break
                    f = f.next
                    n = n.next
                    i = i + 1
                if flag == 1:
                    n.next = Node(val)
                    n.next.next = f
                else:
                    print("Position not found")
    
        def delete(self):
            if self.empty() is True:
                print("Linked List empty")
                return
            elif self.head.next is None:
                self.head = None
                return
            opt = int(input("Enter 1 to delete the beginning element\nEnter 2 to delete the last element\nEnter 3 to "
                            "delete elements in between ::"))
            if opt == 1:
                self.head = self.head.next
            elif opt == 2:
                n = self.head
                while n.next.next is not None:
                    n = n.next
                n.next = None
            else:
                op = int(input("Enter 1 to delete by position\nEnter 2 to delete by value ::"))
                if op == 1:
                    pos = int(input("Enter the position ::"))
                    i = 1
                    n = self.head
                    f = self.head.next
                    flag = 0
                    while f.next is not None:
                        if i == pos:
                            flag = 1
                            break
                        i = i + 1
                        n = n.next
                        f = f.next
                    if flag == 1:
                        n.next = f.next
                    else:
                        print("Position not found")
                        return
                else:
                    val = int(input("Enter the value you want to delete ::"))
                    n = self.head
                    f = self.head.next
                    flag = 0
                    while f.next is not None:
                        if f.value == val:
                            flag = 1
                            break
                        f = f.next
                        n = n.next
                    if flag == 1:
                        n.next = f.next
                    else:
                        print("Value not found")
                        return
    
        def clear(self):
            self.head = None
            print("Linked List cleared")
    
        def empty(self):
            if self.head is None:
                return True
            else:
                return False
    
        def display(self):
            if self.empty() is True:
                print("Linked List empty")
                return
            print("THE LINKED LIST")
            print(self.head.value, " <== HEAD")
            n = self.head.next
            while n is not None:
                print(n.value)
                n = n.next
            print("Linked List ends")
    
    LL = SLL()
    while True:
        option = int(input("Enter 1 to add an element\nEnter 2 to delete an element\nEnter 3 to clear the Linked "
                           "List\nEnter 4 to display the Linked List\nEnter 5 to exit ::"))
        if option == 1:
            value = int(input("Enter the value you want to add ::"))
            LL.add(value)
            continue
        elif option == 2:
            LL.delete()
            continue
        elif option == 3:
            LL.clear()
            continue
        elif option == 4:
            LL.display()
            continue
        elif option == 5:
            print("Goodbye")
            break
        elif option == 6:
            print(LL.empty())
        else:
            print("Wrong option")​

    the output of this program is

    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::1
    Enter the value you want to add ::1
    Head value created
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::1
    Enter the value you want to add ::2
    Enter 1 to add a Node at the beginning
    Enter 2 to add a Node at the end
    Enter 3 to add a Node in the middle::1
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::1
    Enter the value you want to add ::3
    Enter 1 to add a Node at the beginning
    Enter 2 to add a Node at the end
    Enter 3 to add a Node in the middle::2
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::1
    Enter the value you want to add ::4
    Enter 1 to add a Node at the beginning
    Enter 2 to add a Node at the end
    Enter 3 to add a Node in the middle::3
    Enter the position ::2
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::4
    THE LINKED LIST
    2  <== HEAD
    1
    4
    3
    Linked List ends
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::2
    Enter 1 to delete the beginning element
    Enter 2 to delete the last element
    Enter 3 to delete elements in between ::1
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::2
    Enter 1 to delete the beginning element
    Enter 2 to delete the last element
    Enter 3 to delete elements in between ::2
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::4
    THE LINKED LIST
    1  <== HEAD
    4
    Linked List ends
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::1
    Enter the value you want to add ::5
    Enter 1 to add a Node at the beginning
    Enter 2 to add a Node at the end
    Enter 3 to add a Node in the middle::2
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::2
    Enter 1 to delete the beginning element
    Enter 2 to delete the last element
    Enter 3 to delete elements in between ::3
    Enter 1 to delete by position
    Enter 2 to delete by value ::1
    Enter the position ::1
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::4
    THE LINKED LIST
    1  <== HEAD
    5
    Linked List ends
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::3
    Linked List cleared
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::4
    Linked List empty
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::5
    Goodbye

singly-linked-list-before-manipulation

Advantages
  • Easy insertion and deletion
  • Efficient memory usage
  • Dynamic size
  • insertion and deletion do not require element shift
Disadvantages
  • No reverse traversal
  • Very time consuming accessing methods
  • Sorting is difficult

Applications of Singly Linked Lists

  1. Implementations of stacks and queues
  2. Uses in graph theory - implementation in adjacency lists
  3. Dynamic memory allocation
  4. Maintaining directories
  5. Arithmetic operations on long integers
  6. Sparse matrix representation
0 results
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions