Linked Lists

A linked list is a data structure that stores items in sequence. Each node contains a value and a reference to the next node in the list. The first node is the head and the last node is the tail. The tail's next field is null.


Nodes in doubly linked lists also contain a reference to the predecessor.


Linked Lists vs. Arrays

A list is similar to an array in that it contains objects in linear order. The key differences are that inserting and deleting elements in a list has time complexity \(O(1)\). On the other hand, obtaining the kth element in a list is expensive, having \(O(n)\) time complexity.


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


def search(key, linked_list):
    """Find the Node with value=key. Return None if not found."""
    while linked_list and linked_list.key != key:
        linked_list =
    return linked_list


def reverse(head):
    """Reverse a singly linked list."""
    to_return = None
    while head:
        buffer = head
        head = = to_return
        to_return = buffer
    return to_return

Find Cycle

def has_cycle(head):
    """Use Floyd's Tortoise and Hare algorithm to check for a cycle."""
    slow = head
    fast = head
    while fast and
        slow =
        fast =
        if fast is slow:
            return True
    return False