Singly Linked List with Python

Implement Singly Linked List with Python

What is Singly Linked List?

A singly linked list is a linear data structure in which the elements are not stored in contiguous memory locations and each element is connected only to its next element using a pointer.

Singly Linked List Implementation

Constructor

Create a Node class with the following features
a. A constructor that takes a value as an argument and initializes the value attribute of the node.
b. A next attribute, initialized to None, which will store a reference to the next node in the list.
Create a LinkedList class with the following features:
a. A constructor that takes a value as an argument, creates a new Node with that value, and initializes the head and tail attributes of the linked list to point to the new node.
b. A length attribute, initialized to 1, which represents the current number of nodes in the list.

class Node:
    def __init__(self, value):
        self.value = value
        self.next  = None


class LinkedList:
    def __init__(self, value):
        new_node = Node(value)
        self.head = new_node
        self.tail = new_node
        self.length = 1

    def print_list(self):
        temp = self.head
        while temp is not None:
            print(temp)
            temp = temp.next

    def make_empty(self):
        self.head = None
        self.tail = None
        self.length = 0

Append

Implement the append method for the LinkedList class. The append method should add a new node with a given value to the end of the linked list, updating the tail attribute and the length attribute accordingly.
Big O: O(1)
- No matter how large the linked list is, the number of operations taken to execute append remains constant
Implementation:
- Please note: the method should be inside the LinkedList class.

def append(self, value):
  # Create a new node with the given value
  new_node = Node(value)

  # Check to see if the linked list is empty
  if self.head is None:
    # Point both head and tail at the new node
    self.head = new_node
    self.tail = new_node
  else:
    # Point the next pointer of the last node at the new node
    self.tail.next = new_node
    # Point tail at the new node
    self.tail = new_node

  # Increment the length of the linked list
  self.length += 1

Pop

The pop method should remove the last node (tail) from the linked list and return the removed node. If the list is empty, the method should return None.
After the last node is removed, the second-to-last node should become the new tail of the list.
Big O: O(n)
- Iterate over the linked list until reach the tail.
- Update the tail
Implementation:
- Please note: the method should be inside the LinkedList class.

def pop(self):
  # Check if the list is empty
  if self.length == 0:
    return None
  # Initialize temp and pre to the head
  temp = self.head
  pre = self.head
  # Iterate until the last node
  while(temp.next):
    pre = temp
    temp = temp.next
  # Set the new tail to the previous node
  self.tail = pre
  # Remove link to the removed node
  self.tail.next = None
  # Decrement list length by 1
  self.length -= 1
  # Check if the list is now empty
  if self.length == 0:
    # Set head and tail to None
    self.head = None
    self.tail = None
  # Return the removed node
  return temp

Prepend

The prepend method should add a new node with a given value to the beginning of the linked list, updating the head attribute and the length attribute accordingly.
Big O: O(1)
- Constant time
- Just need to add and update the head attribute
Implementation:
- Please note: the method should be inside the LinkedList class.

def prepend(self, value):
  # Create a new Node with the given value
  new_node = Node(value)

  # Check if the linked list is empty
  if self.length == 0:
    # Set the head and tail attributes to the new node
    self.head = new_node
    self.tail = new_node
  else:
    # Set the next attribute of the new node to the current head
    new_node.next = self.head
    # Update the head attribute to the new node
    self.head = new_node

  # Increment the length attribute of the LinkedList
  self.length += 1

  # Return True to indicate a successful operation
  return True

Pop First

The pop_first method should remove the first node (the head) from the linked list, update the head attribute and the length attribute accordingly, and return the removed node.
Big O: O(1)
- Constant time
- Remove the first node (the head) from the linked list
- Update the head attribute and the length attribute
Implementation:
- Please note: the method should be inside the LinkedList class.

def pop_first(self):
  # Check if the list is empty
  if self.length == 0:
    return None

  # Save a reference to the current head node
  temp = self.head

  # Update the head to the second node in the list
  self.head = self.head.next

  # Disconnect the removed node from the list
  temp.next = None

  # Decrease the length of the list by 1
  self.length -= 1

  # Check if the list is now empty
  if self.length == 0:
    # Set the tail to None if the list is empty
    self.tail = None

  # Return the removed node
  return temp

Get

The get method should take an integer index as a parameter and return a pointer to the node at the specified index in the linked list.
Big O: O(n)
- Iterate through the list until the specified index is
Implementation:
- Please note: the method should be inside the LinkedList class.

def get(self, index):
    # Check if the given index is out of bounds
    if index < 0 or index >= self.length:
        return None

    # Initialize a temporary variable to the head of the list
    temp = self.head

    # Traverse the list 'index' times
    for _ in range(index):
        # Move the temporary variable to the next node in the list
        temp = temp.next

    # Return the node at the specified index
    return temp

Set

The set_value method should take an integer index and a value as parameters and update the value of the node at the specified index in the linked list.
Big O: O(n)
- set_value uses the get method, which is O(n), to iterate through the linked list
Implementation:
- Please note: the method should be inside the LinkedList class.

def set_value(self, index, value):
    # Call the 'get' method to find the node at the specified index
    temp = self.get(index)

    # Check if a valid node was found at the specified index
    if temp:
        # Update the value of the found node with the given value
        temp.value = value

        # Return True to indicate that the value was updated successfully
        return True

    # If no valid node was found, return False to indicate that
    # the value was not updated
    return False

Insert

The insert method should take an integer index and a value as parameters and insert a new node with the given value at the specified index in the linked list.
Big O: O(n)
- insert uses the get method, which is O(n), to iterate through the linked list
Implementation:
- Please note: the method should be inside the LinkedList class.

def insert(self, index, value):
    # Check if index is out of bounds
    if index < 0 or index > self.length:
        return False
    # If index is 0, prepend the value
    if index == 0:
        return self.prepend(value)
    # If index is at the end, append the value
    if index == self.length:
        return self.append(value)
    # Create a new node with the value
    new_node = Node(value)
    # Get the node just before the insertion point
    temp = self.get(index - 1)
    # Set new_node's next to temp's next
    new_node.next = temp.next
    # Update temp's next to the new_node
    temp.next = new_node
    # Increment the length of the list
    self.length += 1
    # Return True as node inserted successfully
    return True

Remove

The remove method should take an integer index as a parameter and remove the node at the specified index in the linked list, returning the removed node.
Big O: O(n)
- remove uses the get method, which is O(n), to iterate through the linked list
Implementation:
- Please note: the method should be inside the LinkedList class.

def remove(self, index):
    # Check if index is out of bounds
    if index < 0 or index >= self.length:
        return None
    # Remove and return the first node
    if index == 0:
        return self.pop_first()
    # Remove and return the last node
    if index == self.length - 1:
        return self.pop()
    # Get the previous node
    pre = self.get(index - 1)
    # Set temp to the node to be removed
    temp = pre.next
    # Update pre.next to skip the removed node
    pre.next = temp.next
    # Disconnect the removed node
    temp.next = None
    # Decrement the list length
    self.length -= 1
    # Return the removed node
    return temp

Reverse

The reverse method should reverse the order of the nodes in the linked list so that the head becomes the tail and the tail becomes the head.
Big O: O(n)
- Iterate through the linked list to swap each node
Implementation:
- Please note: the method should be inside the LinkedList class.

def reverse(self):
    # Swap the head and tail pointers
    temp = self.head
    self.head = self.tail
    self.tail = temp

    # Initialize variables for the next and previous nodes
    after = temp.next
    before = None

    # Iterate through the list to reverse the next pointers
    for _ in range(self.length):
        # Store the next node in the list
        after = temp.next

        # Update the current node's next pointer to the previous node
        temp.next = before

        # Move the previous node to the current node
        before = temp

        # Move the current node to the next node in the list
        temp = after

This is the end of Singly LinkedList Implementation

Singly Linked List with Python

Implement Singly Linked List with Python

What is Singly Linked List?

Singly Linked List Implementation

Constructor

Append

Pop

Prepend

Pop First

Get

Set

Insert

Remove

Reverse

Topics

More stories

Social media