Linked-List Examples:

Java
Java
Python
Python
PHP
PHP
C#
C#
C++
C++
TypeScript
TypeScript
▸ Linked-List Quick Review

Linked-List in Python

#Linked List python implementation
# Node class
class Node:
   def __init__(self, value, nextNode):
       self.value = value
       self.next = nextNode

#Linked List class
class LinkedList:
   def __init__(self):
       self.root = None
       
   def isEmpty(self):
       return self.root is None
   
   # Does this linked list contain a certain value?
   def contains(self, value):
       if self.isEmpty():
           return False
       tmp = self.root
       # While the temp is valid
       while tmp is not None:
           # If the value is a match, return true.
           if tmp.value == value:
               return True
           # Otherwise, iterate.
           tmp = tmp.next
       # No matches found, so return false.
       return False
   
   def get(self, index):
       if self.isEmpty():
           raise IndexError('index out of range on LinkedList->get method')
       tmp = self.root
       # iterate from the root to the given index.
       for i in range(0, index):
           tmp = tmp.next
           # We are out of bounds, raise an exception.
           if tmp is None:
               raise IndexError('index out of range on LinkedList->get method')
       # Return the value of the current node.
       return tmp.value

   
   def getFirst(self):
       return self.root
   
   
   def getLast(self):
       if self.isEmpty():
           return None
       tmp = self.root
       # Iterate over the linked list.
       while tmp.next is not None:
           tmp = tmp.next
       # Return the value of the last node.
       return tmp.value

   # Add a specified value to the end of the linked list.
   def add(self, value):
       if self.isEmpty():
           self.root = Node(value, None)
           return
       
       tmp = self.root
       # Iterate over the list.
       while tmp.next is not None:
           tmp = tmp.next
       # Once at the last node, set it's next node to the new node.
       tmp.next = Node(value, None)
   
   def addFirst(self, value):
       # Create a new node with the root as it's next node.
       tmp = Node(value, self.root)
       # Change the reference of the root to the new node.
       self.root = tmp

   # Add a new node after a specified key.
   def addAfter(self, key, toAdd):
       if self.isEmpty():
           self.root = Node(toAdd, None)
       tmp = self.root
       # Iterate until we find a match.
       while tmp.next is not None:
           # Found a match.
           if tmp.value == key:
               newNode = Node(toAdd, tmp.next)
               tmp.next = newNode
               return
           tmp = tmp.next
       # Depends on implementation, but in this version
       # we add a new node at the end if no node was matched.
       tmp.next = Node(toAdd, None)
   
   # Add a new node before a specified key.
   def addBefore(self, key, toAdd):
       # Base cases:
       if self.isEmpty():
           self.root = Node(toAdd, None)
       tmpPrev = self.root
       tmp = self.root.next
       if tmpPrev.value == key:
           self.addFirst(toAdd)
           return
       # Main case:
       # Iterate the list.
       while tmp is not None:
           # If the lead node is a match, break...
           if tmp.value == key:
               break
           # ( Iterate )
           tmpPrev = tmp
           tmp = tmp.next
       # ... and insert the new node at the intermediate.
       tmpPrev.next = Node(toAdd, tmp)
   
   # Remove a node with the specified value from the list.
   def remove(self, value):
       if self.isEmpty():
           return
       tmp = self.root
       # Iterate the list.
       while tmp.next is not None:
           # If the next node is a match,...
           if tmp.next.value == value:
               # set the next to be the next next.
               # (gc will help us out).
               tmp.next = tmp.next.next
               return
           # Otherwise iterate.
           tmp = tmp.next
               
   # Remove the first node from the list.
   def removeFirst(self):
       if self.isEmpty():
           return
       # We just increment the root to the next node.
       self.root = self.root.next
   
   # Remove the last node from the list
   def removeLast(self):
       # Base cases:
       if self.isEmpty():
           return
       tmp = self.root
       if tmp.next is None:
           self.root = None
           return
       # Main case:
       # We need to look 2 ahead to set the 'next' node to none.
       while tmp.next.next is not None:
           tmp = tmp.next
       # Set the 'next' node to none.
       tmp.next = None

   # Get the length of the linked list.
   def length(self):
       count = 0
       tmp = self.root
       while tmp is not None:
           count+=1
           tmp = tmp.next
       return count
   
   # Get the index of a specified value, if it exists.
   def indexOf(self, value):
       if self.isEmpty():
           return -1
       count = 0
       tmp = self.root
       # Iterate the list.
       while tmp is not None:
           if tmp.value == value:
               return count
           # Increment and iterate.
           count+=1
           tmp = tmp.next
       # Value doesn't exist, return -1.
       return -1
   
   # Clear the linked list.
   def clear(self):
       self.root = None
       return

   # Format the linked list to a string.
   def __str__(self):
       res = "["
       tmp = self.root
       while tmp is not None:
           res += str(tmp.value)
           if tmp.next is not None:
               res += ", "
           tmp = tmp.next
       res += "]"
       return res

Find any bugs in the code? let us know!