Mastering Linked Lists: Understanding, Implementing, and Manipulating in Python

Introduction to Linked Lists

Welcome to our intriguing session for today! We're diving into an essential topic in computer science and data structures: Linked Lists . These structures comprise a sequence of nodes . Each node holds some data and a reference (a link) to the next node, thus forming a chain-like structure. The concept of linked lists is leveraged in many real-world scenarios. For instance, in a music playlist where songs can be dynamically added, deleted, or reordered, linked lists serve as an excellent solution thanks to their efficient operations.

Understanding Linked Lists

A linked list is a collection of nodes, each acting as a container for its data and a pointer (link) to the next node in the list. This link greatly facilitates sequential traversal through the list. Here is a simple visualization of a node: class Node {Data Pointer to Next Node} A node consists of two parts: Data, which contains the stored value (that could be any type such as number, string, etc.), and Pointer to Next Node, which holds the link to the next node in the sequence. When a node is initially created, next is set to None because there is no subsequent node to point to. Think of it like a treasure hunt game, where each clue leads to the next one, and the chain continues until we reach the final destination.

Linked Lists vs Arrays

O(1)

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Python

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

class LinkedList:
   def __init__(self):
       self.head = None
       self.tail = None

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

class LinkedList:
   def __init__(self):
       self.head = None
       self.tail = None

Python

def insert(self, value):
    if self.head is None:
        self.head = Node(value)
        self.tail = self.head
    else:
        new_node = Node(value)
        self.tail.next = new_node
        self.tail = new_node

def insert(self, value):
    if self.head is None:
        self.head = Node(value)
        self.tail = self.head
    else:
        new_node = Node(value)
        self.tail.next = new_node
        self.tail = new_node

Python

# Defining the delete method
def delete(self, value):
    temp = self.head

# Defining the delete method
def delete(self, value):
    temp = self.head

Python

    if (temp is not None):
         if temp.value == value:
            self.head = temp.next
            temp = None
            return

    if (temp is not None):
         if temp.value == value:
            self.head = temp.next
            temp = None
            return

Python

    while (temp is not None):
        if temp.value == value:
            break
        prev = temp
        temp = temp.next

    while (temp is not None):
        if temp.value == value:
            break
        prev = temp
        temp = temp.next

Python

    if temp == None:
        return
    prev.next = temp.next
    temp = None

    if temp == None:
        return
    prev.next = temp.next
    temp = None

Python

def print(self):
    temp = self.head
    while temp is not None:
        print(temp.value, end=" => ")
        temp = temp.next

def print(self):
    temp = self.head
    while temp is not None:
        print(temp.value, end=" => ")
        temp = temp.next

Python

list = LinkedList()
list.insert(1)
list.insert(2)
list.insert(3)
list.print() # Output: 1 => 2 => 3 =>
list.delete(2)
list.print() # Output: 1 => 3 =>

list = LinkedList()
list.insert(1)
list.insert(2)
list.insert(3)
list.print() # Output: 1 => 2 => 3 =>
list.delete(2)
list.print() # Output: 1 => 3 =>

Python

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

class LinkedList:
   def __init__(self):
       self.head = None
       self.tail = None

Python

def insert(self, value):
    if self.head is None:
        self.head = Node(value)
        self.tail = self.head
    else:
        new_node = Node(value)
        self.tail.next = new_node
        self.tail = new_node

Python

# Defining the delete method
def delete(self, value):
    temp = self.head

Python

    if (temp is not None):
         if temp.value == value:
            self.head = temp.next
            temp = None
            return

Python

    while (temp is not None):
        if temp.value == value:
            break
        prev = temp
        temp = temp.next

Python

    if temp == None:
        return
    prev.next = temp.next
    temp = None

Python

def print(self):
    temp = self.head
    while temp is not None:
        print(temp.value, end=" => ")
        temp = temp.next

Python

list = LinkedList()
list.insert(1)
list.insert(2)
list.insert(3)
list.print() # Output: 1 => 2 => 3 =>
list.delete(2)
list.print() # Output: 1 => 3 =>